Hashing

Hash functions accept a key and return an output unique only to that specific key.

• Know as hashing, which is the concept that an input and an output have a one-to-one correspondence to map information.
• Hash functions return a unique address in memory for that data.

A hash function takes a key value and calculates a valid bucket index.

We want to use hashing to get constant operation time $O(1)$. That is the main goal.

However, there might be Hash Collision.

Two disadvantages of direct addressing:

• It cannot be used if the keys are not integers
• It wastes space if $M$ is unknown or $n<<M$

Hashing idea: Map (arbitrary) keys to integers in range $0,...,M-1$ and the use direct addressing.

Details:

• Assumption: We know that all keys come from some universe $U$.
• We design a hash function $h:U\to 0,1,...,M-1$
• Store dictionary in hash table, i.e. an array $T$ of size of $M$
• An item with key $k$ should ideally be stored in slot $h(k)$ i.e. at $T[h(k)]$
• Rehash takes $O(n+M)$ time.

Hash Collision

When two pieces of data in a hash table share the same hash value.

Many key that goes into a hashing function can come out, that is map to the same integer.

• Example: $h(46)=2=h(12)$ if $h(k)=k$ mod $11$

Thus, we get collisions: that is when we want to insert $(k,v)$ into the table, but $T[h(k)]$ is already occupied.

We will look at strategies to resolve collisions!

Chaining:

• Hashing with Chaining Open addressing:
• Probe Sequence
• Cuckoo Hashing

Complexity of open addressing strategies

Really only need to remember Cuckoo Hashing search $O(1)$ unsuccessful and successful $O(1)$. All of them except for hashing with chaining depends on the load factor being less than 1. So for example, if the $\alpha$ is close to 1, then the search operation (using linear probing) does not have a constant $O(1)$ average-case running time.

Hash Function Strategies

What is the desired property of a randomly chosen hash function $h:U\to 0,...,S-1$?

• $Pr(h(u)=i)=\frac{1}{S}$ for all keys $u$ and slots $i$
  • This means that it uniformly distributes the keys from the universe $U$ across all the slots in the hash table of size $S$. In other words, for any key $u$ and any slot $i$ in the hash table, the probability $Pr(h(u)=i)$ is $1/S$. The reason for this property is to achieve “uniform hashing assumption”. It means that each slot is equally likely to be chosen for any given key. This uniformity ensures that the elements are evenly spread throughout the hash table, minimizing the number of collisions. Crucial for achieving $O(1)$ average-case time complexity for hash table operations like insertion and search.

Choose BST if we want guarantee, but Hash Tables cannot guarantee, but is faster usually in the worst-case for search and delete.

---

Related

• Hash Table
• Hash Collision