challenge: Closing hash, linear probing, probe length 1

Question

The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element, it discards it directly (that is, it does not try to place it in positions 0, 1, 2 ... as it would be correct)

In a hash table using closed hash, linear probing, probe length 1.

What is the probability that with this test we discover that the implementation n has a bug, if N = 27 and K = 42?

Example K=2, N=2: The only case is if both hashes are 1. In this case, the first element in array [ 1 ] is first saved. Then, the next element does not have space in array [ 1 ] and since it is the last position of the array, will discard it

I made a script to bruteforce all combinations and find the probability for the firsts N / K

The pseudocode is:

function bruteforce(array):
  hashtable=
        {0="" , 1="" , ..., ..., k-1=""}
  for element in array:
      canStoreThisCombination=False
      for j in range (element,len(hashtable)):
          if (empty(hashtable[j])):
              hashtable[j]="used"
              canStoreThisCombination=True
              break
  if not canStoreThisCombination:
      tot=tot+1


for each combination of N elements:
  bruteforce(actualCombination)


print tot/(k^n)

and got the following results:

table

Combinations for K=3

Combinations for K=4

Combinations for K=5

I'm looking for probability as an irreducible fraction

Answer 1

This problem was formulated and solved in 1962 by Donald Knuth; apparently, it was his first exercise in algorithmic analysis. It's often referred to as the "parking problem".

Knuth's analysis is beautifully simple. (Note: Knuth, and I think most computer scientists, used $n$ as the size of the hash table, and $k$ as the number of items inserted. So do I, even though the question is expressed differently.)

Let's start with the set $A$ of hash values of $k$ items, consisting of all sequences $\langle a_1, \ldots, a_k \rangle$, where $0 \le a_i < n$. Clearly there are $n^k$ possible sequences.

Now, suppose we have a bug-free hash table of size $n+1$, and look the set $B$ of all possible hash sequences for $k$ items, $\langle b_1, \ldots, b_k \rangle$ with $0 \le b_i < n+1$. There are $(n+1)^k$ such sequences.

Of those sequences, we select the subset $B'$ for which the last table entry ($n$) is empty at the end of the insertion. Since once a slot is occupied, it remains occupied at the end, we know that for every sequence in $B'$, every $b_i < n$. Therefore, every sequence in $B'$ is also in $A$.

Moreover, we know that in the course of the insertion, no probe passes through position $n$. In other words, every sequence in this subset of $B$ is a sequence in $A$ in which there is no wrap-around, which are precisely the sequences in $A$ which do not trigger the bug.

So it will only remains to count these sequences. But that's trivial, because all of the slots in the (bug-free) hash table are identical. So the probability that a particular slot will be unoccupied after inserting $k$ items is $1 - {k \over {n+1}}$, with the result that there are $(n+1-k)(n+1)^{k-1}$ such sequences.

Thus, the probability that a random sequence of $k$ insertions into the buggy hash table will trigger the bug is $1 - {(n+1-k)(n+1)^{k-1}\over n^k}$.

By the way, the output of the program you paste-binned is not correct. For example, it lists $4, 4, 4$ twice in the list for three insertions into a table of size 5.

Answer 2

You are basically trying to map $\{0,N-1\} \rightarrow \{0,K-1\} \space , \space N\le K$ with no collisions. You are calling collisions a bug. So basically you want to calculate the probability of finding atleast 1 collision.

Total number of ways to map with no collisions
= (No of ways to arrange N numbers in K places leaving other unoccupied places as 0) * (No of ways to permute the N values in those arranged places)
$$ = ^KP_N * N! = \frac{K!*N!}{(K-N)!}$$ Total number of ways to map with 1 collision (Two keys to one value) $$ = \frac{K!*N!}{(K-N)!} * \frac{1}{2!}$$ Total number of ways to map with 2 collision (Three keys to one value) $$ = \frac{K!*N!}{(K-N)!} * \frac{1}{3!}$$ and so on gives us the total number of ways to map with or without collisions $$ = \frac{K!*N!}{(K-N)!} * (1 + \frac{1}{2!} + \frac{1}{3!} ... + \frac{1}{(N-1)!}$$ $$ \approx \frac{K!*N!}{(K-N)!} * e $$ for large enough N. Hence the probability of getting a collision/finding your bug $$ = 1 - \frac{1}{e}$$