Indexed Retrieval + Hashing

How does index mapping work?

Example

• Lets say we have a collection of people’s names, where:

  • Keys are the alphabetic keys, e.g. “A” records, “B” records etc.

  • index[0] holds first “A” record, index[1] holds first “B” record, etc.

• If there are no names for a specific letter, then: index[n] = -1;

How effiicient is retrieving index with linear search?

• Worst case: all keys start with same letter (O(N))

• Best case: first key found (O(1))

How efficient is retrieving index with binary search?

• Worst case: everything in 1 section, binary search whole array (O(log₂N))

• Best case: key found immediately (O(1))

What is a hash table?

• Elements stored in “buckets” (e.g. index of array)

• Every hash table element has a unique key

• Hash function takes key of an element to generate hash code

• Hash code says what bucket the element belongs to so we can go directly to that hash table element (assuming no collisions)

How can we design a good hash function?

• Minimise collisions by using a wide range of index values

  • We can do this by using multiplication as well as addition

• Uniform hashing: each key is equally likely to map to an array location

• Or, we use bit shifting

What happens if chains grow too long?

• Hash tabel becomes less efficient

• Avoid this by hash table allocating an array double size of current array

• Then, put <k, v> in current array into larger array