Hashing with Chaining

https://www.geeksforgeeks.org/separate-chaining-collision-handling-technique-in-hashing/

Simplest way to resolve collisions: Each slot stores a bucket containing 0 or more KVPs.

• A bucket could be implemented by any dictionary realization(even another hash table)

• The simplest approach is to use unsorted Linked Lists for buckets. This is called collision resolution by chaining

• $Search(k)$: Look for key in the list at $T[h(k)]$ apply MTF

• $Insert(k,v)$: Add (k, v) to the front of the list at $T[h(k)]$

• $Delete(k)$: Perform a search, then delete from the linked list

\alpha

Hashing with Chaining does not care about the $\alpha$ that is the ratio of $fractnM$, since each slot contains a list and we just add in the front of the list in each of the slot if it is already occupied. Don’t need to rehash so there is no insertion failure.

Example in lecture notes CS240 - Data Structure and Data Management.

Run-times:

• insert takes time $\Theta (1)$, expected cost for hashing with chaining for lookup, insert and delete (according to piazza).
• search and delete have run-time $\Theta$(1+ size of bucket $T[h(h)]$) → what is this? The worst-case runtime? (Waiting on piazza response.)
  • $\Theta (1+\alpha )$ is the average-case runtime. Since the average bucket size is $n/M$.

The average bucket-size is $\frac{n}{M}=\alpha$ ($\alpha$ is called the load factor).

In separate chaining, search and delete have average-case cost $O(\frac{M+n}{M})$, where $n$ is the number of keys and $m$ is the number of buckets. Which is $\Theta (1+\alpha )$. Only under the uniform hashing assumption!!!

Note

Does not mean the average-case cost of search and delete is $\Theta (1+\alpha )$ !

(If all keys hash to the same slot, the bucket size is still $\alpha$, but operations will take $\Theta (n)$)

Does that mean under the uniform hashing assumption that the expected running time of search and delete is $\Theta (1+\alpha )$???? Yes, because $1+\alpha$ is in the order of a constant (since $\alpha \le 1$) so you’ll never have search or delete be faster than constant runtime. It is plus 1 because $\alpha =\frac{n}{M}$ is always less than or equal to $1$; further, if $M>>n$, then $\alpha \in o(1)$. But the average case of search is obviously not $o(1)$, so we add $1$ to ensure that we’re correctly representing the idea of an average-case constant runtime.

$P()=1/M$, and there are $n-1$ such keys to have a $1/M$ possibility to collide with that slot.

Why is rehashing costs $\Theta (M+n)$????? Is it because to initialize hash table is $\Theta (M)$ and copying every item over to the new hash table is $\Theta (n)$, since all operations now have expected runtime of $O(1)$ or $\Theta (1)$? and when we combine together we get $O(M+n)$??

Summary: If we maintain $\alpha \in \Theta (1)$, then (under the uniform hashing assumption) the expected cost for hashing with chaining is $O(1)$, for lookup, insert and delete and the space is $\Theta (n)$.

If $n<<M$ then $\Theta (M)$ is not $\Theta (n)$.

Questions

What is the worst-case number of comparisons we make when we search for the same key $k$ twice in a row in a hash table that uses chaining with a linked list and the MTF Heuristic?

• My reasoning is that in the worst case, we find the slot in the table in $O(1)$ time, and we have to travel and compare the whole linked list since it’s at the end. That would cost $O(n)$. For the first search, then MTF, we search again, it’s already at the front of the list. So $n+1$.

Do we require a load factor $\alpha <1$?

• No, not in separate chaining. Since, the collision technique uses linked lists to handle multiple elements that hash to the same index. As a result, the hash table can handle a load factor greater than 1, that is the ration of the number of elements stored in to the size of the table.