Hash Table

see data structure

a map implemented using a hash function

aka hash map

time computational complexity:

note time computational complexity is O ->1 only if the hash function is uniform

definition the load factor of a hash table is the ratio of the number of elements in the hash table to the number of slots in the hash table

definition the maximum load factor aa of a hash table load factor allowed before the hash table is resized

Operations (Separate Chaining)

let a list of n buckets (such as a list, a tree, a set, etc.) be used to store keys and values

procedure computing the hash of a key

given a key k and a hash function H,

1. return "mod" n (H k)

procedure inserting into a hash table

given a key k and a value v,

1. compute the hash h of k
2. insert (or update) k, v into the bucket at index h in the list
3. resize the hash table

procedure removing from a hash table

given a key k,

1. compute the hash h of k
2. remove k, v from the bucket at index h in the list
3. resize the hash table

procedure looking up a value in a hash table

given a key k,

1. compute the hash h of k
2. look up k in the bucket at index h in the list
3. resize the hash table

Operations (Open Addressing)

see math notation

let a list of n elements be used to store keys and values

let a probing function P be used to find the next element to probe. typically, P has a probing › cycle length of n.

definition a tombstone is a unique marker used to indicate that a key has been removed from a hash table.

procedure computing the hash of a key

given a key k and a hash function H,

1. return "mod" n (H k)

procedure computing ith value in a probing sequence

given a probing sequence index i and a key k:

1. return "mod" n (H k : P i k)

procedure inserting into a hash table

given a key k and a value v,

1. compute the hash h of k
2. if index h of the list is empty or is a tombstone, insert (or update) k, v into index h of the list. otherwise, set h to the next value in its probing sequence and repeat this step
3. resize the hash table

procedure removing from a hash table

given a key k,

1. compute the hash h of k
2. if index h of the list contains k, remove k, v from index h of the list by replacing it with a tombstone. otherwise, set h to the next value in its probing sequence and repeat this step
3. resize the hash table

procedure looking up a value in a hash table

given a key k,

1. compute the hash h of k
2. if index h of the list contains k, return the value associated with k. if index h of the list is empty, the element is not present in the hash table, break. otherwise, set h to the next value in its probing sequence and repeat this step
3. resize the hash table

note if tomstones are encountered during the search, key k can be moved to the first tombstone encountered for faster future lookups. this technique is called lazy deletion or lazy relocation