Hash Tables

Last updated Nov 8, 2022 Edit Source

The problem with direct addressing: when the number of keys known to us is large, we are unable to map each key to their own slot.

A hash function allows us to compute the slot from the key and reduce the amount of storage required to store all the keys.

The time complexity for searching an element is O(1)

A good hash function satisfies (approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the m slots, independently of where any other key has hashed to.

Divide the key by some prime number not too close to a power of 2 (bits are in powers of 2) $h(k)=k\\ mod\\ m$

I am not too sure how this works. Refer to “Introduction to algorithms”, 2009, p. 263

We can combine the hash table with a Linked Lists, placing all the elements that hash to the same slot into the same linked list:

The extra memory freed by not storing pointers provides the hash table with a larger number of slots for the same amount of memory, potentially yielding fewer collisions and faster retrieval.

We systematically examine table slots until either we find the desired element or we have ascertained that the element is not in the table.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

HASH-INSERT(T, k) 
i = 0
repeat
	j = h(k,i)
	if T[j]  NIL
		T[j] = k
		return j
	else i++
until im
error "hash table overflow"