Hash Tables

Question 1

What is the name of the function a Hash Table uses to create its indexes?

Answer 1

A Hash Function.

Question 2

Define a Hash Function.

Answer 2

A Hash Function will take all of the keys for a given map and strategically map them to certain index locations in an array so that they can eventually be retrieved easily.

Question 3

What is the BigO of finding the index of a key?

Answer 3

O(1). Near instantaneous.

O(n) if there are hash collisions

Question 4

What is the backing Data Structure of a HashTable?

Answer 4

An array. The keys map to indexes in an array.

Question 5

What happens when our hash function comes up with the same index value for two separate keys? For example both the key “Steven” and the key “Steve” both compute to the index 9.

Answer 5

A “Hash Collision” occurs.

Question 6

Why do we use a hash function to come up with a numerical index?

Answer 6

To allow the use of an Array to store our data.
To minimise the size of the array. Our hash function squashes our keys down to a minimised index range so that we can have arrays sized relatively small compared to the range of our key values. E.g. key is 9 Billion, we could hash it to within a range of 1,000.

Question 7

What are the possible ways to handle a “Hash Collision”?

Answer 7

‘Collision Resolution Policy’

1. Open Addressing
2. Closed Addressing “Chaining”
3. Robin Hood Hashing

Question 8

What is Open Addressing?

Answer 8

Put the key in some other index location separate from the one returned to us by the hash function. Usually the next OPEN (or free/available/nil) index.

Open addressing uses no extra space - every element is stored in the hash table. If it gets overfull, we can reallocate space and rehash.

When a collision occurs in open addressing, we can…
• probe nearby for a free position (leads to clustering, quadratic probing).
• go to a “random” position by using a second-level hash function.
• try a position given by a second, third, . . . hash function (this plus LCFS gives cuckoo hashing).

Question 9

What are the downsides of Open Addressing?

Answer 9

1. Makes it harder to interact with the data in the map later on.
2. Leads to issues when another key hashes to the (previously nil) used up index.

Question 10

What is Closed Addressing? (Chaining)

Answer 10

Uses Linked Lists to chain together keys which hash to the same index value.

Chaining uses an “overflow” list for each element in the hash table
• Elements that hash to the same slot are placed in a list. The slot contains a pointer to the head of this list.
• Insertion can then be done in constant time.
• A drawback is the additional space overhead.
• The distribution of sizes of lists turns out to be very uneven.

Question 11

What are the downsides of Closed Addressing?

Answer 11

To get to the key we want we have to traverse the LinkedList stored in the ‘Collision Index’. This slows down the access time from O(1) to O(n). n being the size of LinkedList, i.e. the number of collisions for that particular index.

Question 12

Why is it difficult to do BigO calculations on HashTables?

Answer 12

Because we always assume the worst-case scenario. For a Hash Table this means every single key hashes to the same index value, which means (using Closed Addressing) we essentially end up with a single Linked List which contains all our elements. In this scenario all BigO calculations are that of the Linked List… O(n).

Question 13

Why do we want a reliable Hash Function?

Answer 13

To minimise Hash Collisions.

Question 14

Knowing that the worst-case scenario for Hash Tables is terrible, what are the BigO results for the average-case scenario for a Hash Table?

Answer 14

They are all O(1)!
To ACCESS, SEARCH for, INSERT, or DELETE a key/value pair from out dictionary, all we need to do. is run that key though the has function and it’ll tell us what index in the hash table to go to in order to perform that operation.

*they can be O(n) in the instance of hash collisions

Question 15

What is a hash table?

Answer 15

a data structure which organizes data using hash functions in order to support quick insertion and search.

Question 16

What are some desirable properties of a hash function?

Answer 16

• It should be computable quickly (constant time).
• if keys are drawn uniformly at random, then the hashed values should be uniformly distributed.
• keys that are “close” should have their hash values “spread out”.

Question 17

What is the simple uniform hashing model?

Answer 17

Each of the n keys is equally likely to hash into any of the m slots.
So we are considering a “balls in bins” model
If n is much smaller than m, collisions will be few and most slots will be empty.
If n is much larger than m, collisions will be many and no slots will be empty.
The most interesting behavior is when m and n are of comparable size

Question 18

What is load factor, λ?

Answer 18

n/m | keys/slots

Question 19

Provided load factor is kept bounded what is the runtime on average for basic operations?

Answer 19

constant time O(1)

Question 20

Uniform hashing average insertion cost?

Answer 20

Θ(1/(1 − λ)) as m → ∞

Question 21

Uniform hashing unsuccessful search cost?

Answer 21

Θ(1/(1 − λ))

Question 22

Deletion in hash tables

Answer 22

If we use chaining, deletion just involves deleting an element from the relevant linked list. However, we must still find it in order to delete it

open addressing, deletion can be trickier. One method is to mark elements as deleted, but not delete them. However this can cause space wastage

If we simply delete an item, then we may no longer be able to find other items that had previously collided with it

Question 23

Effect of hashing on runtime of binary search and search trees?

Answer 23

O(1) dictionary operations instead of the O(lg n) needed for binary search (static tables) and/or balanced search trees (dynamic tables)

Question 24

What happens the larger the load factor gets?

Answer 24

larger λ is the more chance of collisions.

Question 25

What are the main desired properties for a good hashing scheme?

Answer 25

• The hash locations of the keys S are spread out to minimize collisions (for lookup, insert, deletes,…).
• Use a relatively small table size m = O(n) that doesn’t affect performance.
• The function h is fast to compute (polynomial in the size of a key x ∈ S, but constant time with respect to n).