1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For me - no. I would like to see description of process, and examples starting from K=2 N=2. You may start with text in your native language and then find a way to translate it, if reason of terse description is your weak English. $\endgroup$ – Bulat Sep 16 '18 at 23:07
  • 1
    $\begingroup$ Where did this question come from? It's unusually specific, and you use the word "challenge" in the tilte, whcih makes it look like either a homework exercise or a competition. $\endgroup$ – David Richerby Sep 16 '18 at 23:07
  • $\begingroup$ Your pseudocode measures the probability that if you choose $x_1,\ldots,x_N \sim [K]$ at random and insert them using your funny procedure, then $x_N$ gets discarded. Is that what you meant by "an element reaches the last slot and it is occupied"? $\endgroup$ – Yuval Filmus Sep 16 '18 at 23:27
  • $\begingroup$ Yep, this is, sorry for my english. $\endgroup$ – G0N Sep 16 '18 at 23:29
  • 1
    $\begingroup$ Your pseudocode is really python. People who don't know python would find constructs such as 'range(x,y)' hard to read. Can you rewrite your code so that anybody can read it, not only people who know python? $\endgroup$ – Yuval Filmus Sep 17 '18 at 3:47
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ I have to disagree. Collisions are fine as long as they don't lead to bumping of the very last element out of the array. $\endgroup$ – Yuval Filmus Sep 17 '18 at 3:46
  • $\begingroup$ @YuvalFilmus Okay. I did not consider the fact that, keys can be redundant. $\endgroup$ – RandomPerfectHashFunction Sep 17 '18 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.