# Can Double Hashing return the same value 2 times?

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

• 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$? – Discrete lizard Jan 21 '18 at 21:57
• 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 – ChaosPredictor Jan 21 '18 at 22:18
• @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)? – Curious_Dim Jan 22 '18 at 1:33

## 1 Answer

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