******************************* Hash Table without Linked Lists ******************************* In the previous topic, we saw how to create a hash table using the **separate chaining**, meaning using linked lists to store elements that have the same hash. The only issue is the running time of adding and searching in the linked list. Idea ==== * The linked lists are used in case of collision. * To remove the linked list, we need to deal with the collision differently. Consider the following: * You have an element :math:`x`. * You hash the element :math:`h = hash(x)` * You check if the cell :math:`h` is occupied or not. * If it is, you have a collision, then you check :math:`h + 1`. * You continue until one cell is empty. It is called **Probing Hash Tables**. More formally, we check a cell :math:`h_i(x)` defined as: .. math:: h_i(x) = (hash(x) + f(i)) \mod TableSize where :math:`f` is the collision resolution function and :math:`f(0) = 0`. Of course, we can use different collision resolution function. .. important:: The size of the table must be larger than with separate chaining tables. Linear Probing ============== In linear probing, :math:`f` is a linear function: .. math:: f(i) = i It's very simple to understand, so we will take an example to illustrate it. .. admonition:: Example :class: example * Consider the hash function :math:`hash(x) = x`. * Consider a table of size 10. * Now we want to insert the following element :math:`\{89, 18, 49, 58, 69\}`. * For each element we calculate :math:`h_i(x) = (x + f(i))\mod 10)`. * We obtain the following result: .. figure:: ./img/hash_table_linear_prob.* :align: center As long as the table is large enough we can always find an empty cell. However, the running time can be quite large. .. admonition:: Activity :class: activity * Why can the running time grow very quickly with linear probing? This problem is accentuated with the **primary clustering** effect. It occurs when block of occupied cells start forming. It is possible to calculate the average number of probes required using a linear probing strategy and a random probing strategy. * Linear probing (insertion): :math:`\frac{1}{2}(1+ \frac{1}{(1-\gamma)^2})`. * Random probing (insertion): :math:`\frac{1}{\gamma}\ln \frac{1}{1-\gamma}` We can see that the number of prob before finding a cell to insert a new element grows quickly with the load factors: .. figure:: ./img/linear_vs_random.* :align: center | Quadratic Probing ================= Linear probing is not optimal due to the **primary clustering**. Quadratic probing eliminates this issue. Obviously, the collision function is quadratic, usually :math:`f(i) = i^2` is used. .. admonition:: Activity :class: activity * Take the previous example and the new collision function and show what is the state of the table after each insertion. * Are we avoiding the primary clustering issue? With quadratic probing there is no guarantee of finding an empty cell once the table gets more than half full! This is because the at most half of the table can be used as alternative locations. It leads us to the following. .. admonition:: Theorem :class: important If quadratic probing is used, and the table size is prime, then a new element can always be inserted if the table is at least half empty. .. admonition:: Proof :class: note * Let :math:`TableSize` be an odd prime greater than 3. * We show that: * :math:`\lceil TableSize/2\rceil` alternative locations are all distinct. * Two of these locations are :math:`h(x)+i^2 \mod TableSize` and :math:`h(x)+j^2 \mod TableSize`, where :math:`0\leq i, j\leq \lfloor TableSize/2 \rfloor`. * (Proof by contradiction): * Suppose that the locations are the same but :math:`i\neq j`, then: .. math:: \begin{align} h(x)+i^2 &= h(x) + j^2\\ i^2 &= j^2\\ i^2 - j^2 &= 0\\ (i-j)(i+j) &= 0 \end{align} * Since :math:`TableSize` is prime, either :math:`(i-j)` or :math:`(i+j)` is equal 0. * Since :math:`i` and :math:`j` are distinct, the first option is impossible. * Since :math:`0\leq i, j\leq \lfloor TableSize/2 \rfloor`, the second option is impossible. * If at most :math:`\lfloor TableSize / 2 \rfloor` positions are taken, then an empty spot can always be found. Implementation -------------- The implementation is in the most part straightforward with the exception of the deletion. If we remove an element that caused a collision, finding the elements that collided will fail. We will consider each cell to have three states: * Active * Empty * Deleted .. code-block:: java private final Entry DELETED = new Entry<>(null, null); So we define the interface of the class as: .. admonition:: HashTable with probing :class: dropdown .. literalinclude:: ./HashTableOpen.java :language: java :linenos: :lines: 3-18, 20-27, 36-44, 46-56, 75-84, 95-114, 129-136, 150-153 get *** The function contains require one other functions: * :code:`find`: find the cell of the element (deal with the collision, etc.) The functions `get` is very easy to implement: .. literalinclude:: ./HashTableOpen.java :language: java :linenos: :lines: 20-36 For :code:`find` we need to proceed by steps: * Initialize the offset aka :math:`f(1)`. * Calculate the current position by calculating the hash of the element * While the position is not empty and it is not the element we're looking for: * we had the offset to the hash. * we increment the offset, using the quadratic collision function :math:`f(i) = f(i-1) + 2*i -1`. * If the current position is greater than the size subtract the size. .. admonition:: Activity :class: activity * Implement the function :code:`find`. .. literalinclude:: ./HashTableOpenQuad.java :language: java :linenos: :lines: 3-6, 23-25 put *** To insert we do the following: * Find the position of the new element. * Put the element at the position * If the number of element (inserted and deleted) is greater than the size of the table, rehash. .. admonition:: Activity :class: activity * Implement the function :code:`put`. remove ****** Very similiar to insert: * Find the position of the element to delete. * Put the element state to :code:`DELETE`. * return the old value. Double Hashing ============== The last collision resolution function is **double hashing**. The idea is simple, we apply a second hashing function inside the hashing function. A popular function is : .. math:: f(i) = i\times \text{hash}_2(x) Note, that we apply the second hash function inside the probe function. The second hash function needs to be selected carefully. * We need to ensure that all cells can be probed. * It requires that :math:`TableSize` is prime. After that a simple function as: .. math:: \text{hash}_2 = R - (x \mod R) works well, if :math:`R` is a prime number smaller than :math:`TableSize`. .. important:: If double hashing is implemented correctly, then the expected number of probes is almost the same as for a random collision function. Rehashing ========= If the table gets too full, the running time for the operations will increase. A solution is * to build another table that is around twice the size (prime number) * scan the original hash table * compute the new hash value for each (nondeleted) element and insert it in the new table. .. admonition:: Example :class: example * Consider the following table. * The hash function is :math:`h(x) = x \mod 7`. * It is more than half full. * So we need to rehash the table. .. figure:: ./img/rehash_1.png :align: center * We created a new table around twice the size (closest prime number). * Every value of the previous table have been inserted using the new hash function :math:`h(x) = x \mod 17`. .. figure:: ./img/rehash_2.png :align: center