0
$\begingroup$

$h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$

as it defined in wikipedia

I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from the other side, is it possible to build $h^{}_{2}$ in such way to that it never happen?

$\endgroup$
  • $\begingroup$ I don't understand your question. How is $h(i,k)$ related to the rest of the question? What is $r$? What are $h_1$ and $h_2$? $\endgroup$ – Discrete lizard Jan 21 '18 at 21:57
  • $\begingroup$ I define $h(i,k)$ as here: en.wikipedia.org/wiki/Double_hashing, I saw in some implementation that $h{}_{2}$ is constant that I call it $r$. $h{}_{1}$ and $h{}_{2}$ defined as in wikipedia $\endgroup$ – ChaosPredictor Jan 21 '18 at 22:18
  • 1
    $\begingroup$ @ChaosPredictor please restate your question, giving more information about your definitions, and what exactly is the problem. When you say 2 time, do you mean 2nd time the h(i,k) is called, in order to find no collision i.e. for i = 2 (if i starts at 1)? Or do you mean second time with exactly same parameters (i and k)? $\endgroup$ – Curious_Dim Jan 22 '18 at 1:33
1
$\begingroup$

Let's demonstrate what you ask with a complete example. Let's say we have a table of size $|T| = 10$, in which we use double hashing to insert-search for an item. Initially we try to insert-search for an item using $i = 0$. This means we try at location $h_1(k)\mod 10$ let's say that is $3$. If there is collision we try at the next position that is at distance $h_2(k)$ from the current position. Or in other words we try for $i = 1$ thus at position $(h_1(k)+ h_2(k))\mod 10$ and so on. Usually $h_2(k)$ is build in such a way that gives values in the range [1, 10). So given an initial position if we move less than the 10 positions (but at least 1) there is no way to hit the same location again. You can think table $T$ as a circular buffer. That is if we index a position out of the it's length we wraparound from the beginning of the buffer. So if initial position is 3 the next 9 positions are in sequence $4,5,6,7,8,9,0,1,2$.

So $h_2(k)$ gives the minimum length we move forward to probe for an empty position. This step is always < |T|. So from step to step there is no way to hit the same location.

You may wonder now that if we miss to find an empty location to insert our k (or in case of search we don't hit k) after several tries (increments of i) then there is possibility to probe some location again after a lot of tries. That is true, but please correct me if I am wrong, that will happen if the load factor is high enough. In such a case you should use a bigger table size of try to fit in it smaller amount of items.

As far as I searched usually the $h_2(k)$ has the form $m - k \mod m$ where $m$ is the biggest prime smaller than |T| so $h_2(k)$ will always be $\neq 0$ and $< |T|$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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