Hashing Analyses

Hashing Analysis

Closed Hashing Analysis

1. Compute the average number of collisions encountered when inserting a key into a hash table, H, of size N containing m keys.
We will analyze the case where we have an unlimited number of very good hash functions, h₁, h₂, ...
We first use h₁ to attempt to insert k into H.
If there is a collision then we use h₂ to attempt to insert k into H, ...
Conceivably, there could be an indeterminate number of collisions using this method. A common method that is used to avoid this problem is to use h₂ for double hashing to create a probe sequence that will specify offsets from the slot that caused the original collision so that every location in the array is probed without repetition. The performance of double hashing is generally not quite as good (although more practical) than the multiple hash function technique we are analyzing here and is more difficult to analyze. So, for clarity of presentation, we will analyze the multiple hash function approach.

Let d = m/N represent the load factor (density) of H.
The probability of a key, k, being inserted with no collisions is 1-d which is the percentage of opens slots in the table.
The probability of a key, k, being inserted with exactly one collision is (1-d)*d since d is the probability of a collision on the first probe and 1-d is the probability of no collision on the second probe.
...
The probability of a key, k, being inserted with exactly r collisions is (1-d)*d^r since the probability of r consecutive collisions is d^r and 1-d is the probability of suceeding on the r+1^st probe.

If EC = number of expected collisions when inserting key k then
EC = 1*(1-d)*d + 2*(1-d)*d² + ... = (1-d)*∑(i*dⁱ) (1 <= i <= infinity)

A closed form expression for the sum may be obtained using the following technique.

S = 1*d + 2*d² + ... + i*dⁱ + ...
d*S = 1*d² + 2*d³ + ... + + (i-1)*dⁱ + i*dⁱ⁺¹ + ...
Matching terms in the S series with terms in the d*S series that have the same power of d and subtracting we obtain the following.

S - d*S = d + d² + d³ + ... dⁱ + ...
The sum on the right is an infinite geometric series equal to d/(1-d)
Factoring we obtain S*(1-d) = d/(1-d) and
S = d/(1-d)² and so
EC = (1-d)*d/(1-d)² = d/(1-d)

2. Compute the expected number of probes requred to insert a key into a hash table, H, of size N containing m keys.

After a key insertion has experienced c collisions a final, collision-free probe is required to place the key. Therefore the expected number of probes, EP, equals the expected number of collisions plus one.
I.e., EP = EC + 1 = 1 + d/(1-d) = 1/(1-d).

3. Compute the average number of lookups required to find a key in hash table, H, of size N when H contains m keys.
For the purpose of this analysis we will assume that all keys were inserted before any lookups were requested and no keys are inserted after lookups have begun.
If key k were inserted on the first probe then it is located where hash function h₁ placed it and the number of lookups required to find k is 1.
If key k were inserted after i-1 collisions then it is located where hash function h_i placed it and the number of lookups required to find k is i.
Therefore the expected number of lookups, EL, required to find a key, k, is equal to the number of probes required to insert the key so the results above solve this problem.
I.e., EL = 1/(1-d)

4. If we have only a small number of hash functions, say j, available we may wish to compute the expected number of probes required when the number of collisions is j or fewer.
If EP(j) represents this quantity then
EP(j) = 1 + 1*(1-d)*d + 2*(1-d)*d² + ... + j*(1-d)*d^j = 1 + (1-d)*∑(i*dⁱ) (1 <= i <= j)

The same method employed above will solve this summation.
S = 1*d + 2*d² + ... + j*d^j
d*S = 1*d² + 2*d³ + ... + (j-1)*d^j + j*d^j+1
Again, matching terms in the S series with terms in the d*S series that have the same power of d and subtracting we obtain the following.

S - d*S = d + d² + d³ + ... + d^j - j*d^j+1
The sum on the right without the last term is a finite geometric series equal to (d-d^j+1)/(1-d)
Factoring we obtain S*(1-d) = (d-d^j+1)/(1-d) - j*d^j+1 and
S = (d-d^j+1)/(1-d)² - j*d^j+1/(1-d) and so
EP(j) = 1 + (1-d)*S = 1 + (d-d^j+1)/(1-d) - j*d^j+1 = (1 - d^j+1)/(1-d) - j*d^j+1

Obviously, if we are limited to j collisions then some keys may not find an open slot in the hash table. We may then use another form of closed hashing collision resolution such as linear probing or we may store these keys outside of the hash table. Storing keys outside the hash table is called open hashing and is addressed in the next section.

Open Hashing Analysis

Compute the average number of keys in a hash table, H, after we attempt to insert m keys into the hash table. Recall that in open hashing keys involved in attempted insertions that result in collisions are stored external to the hash table.

We shall assume that h is an excellent hashing function. I.e., h distributes the keys uniformly (as a random number generator would do).

Let HT be a hash table of size N

Let K_i be the expected number of items in HT after i attempted insertions.

The expected number of elements in the hash table after m-1 attempted insertions using hash function h is K_m-1. Therefore the expected number of open slots at this time is N-K_m-1.
The probability of inserting the m^th key (i.e. no collision on the insertion of the m^th key) is, then, (N-K_m-1)/N.
Therefore K_m = K_m-1 + (N-K_m-1)/N

Algebraic manipulation gives K_m = 1 + ((N-1)/N)*K_m-1

Hence, K_m = ∑((N-1)/N)ⁱ where i ranges from 0 to m-1.

Applying the formula for the sum of a finite geometric series we have
K_m = N*(1 - ((N-1)/N)^m) = N - N*((N-1)/N)^m

Let C_m equal the expected number of collisions after m attempted insertions into HT using h.
Since K_m + C_m = m we have

C_m = m - (N - ( N*((N-1)/N)^m) = m - N + N*((N-1)/N)^m

C_m = m - N - N×(

N-1
-----
N

)

= m - N + N*(N-1)/N^m

An example.
Consider the file ShortList.txt which is a text file containing English language words. ShortList.txt contains 36721 unique words.

If we hash these words into a hash table containing 73342 slots then N = 73342 and m=36721. Note that N = 2*m.
After attempting to insert all of the words into the table we should expect the table to contain approximately
N*(1 - ((N-1)/N)^m-1) = 28888 words. This implies that the remaining 7833 words are expected to be involved in collisions and stored outside of the hash table.

Top of this page Top of page

Home page