Hash Tables

Question 1

What is a dictionary?

Answer 1

A data structure that stores data by mapping keys to values

Question 2

What are the methods that are implemented in dictionaries?

Answer 2

insert
remove
find
size
isEmpty
keys
values

Question 3

Describe some possible implications of design decisions with dictionaries

Answer 3

Insert - overwrite existing keys?

Find - fail or return null for missing key?

Question 4

What are the three possible implementations of associative arrays (dictionaries)?

Answer 4

List
Array
Binary search tree

Question 5

Describe some features of list implementation of a dictionary?

Answer 5

Linear search complexity looking for keys

Simple

Question 6

Describe some features of array implementation of a dictionary?

Answer 6

Same list of key/value pairs
Fixed size
O(n) search/add/remove

Question 7

Describe some features of binary search tree implementation of a dictionary?

Answer 7

O(log n) search, addition and removal

Need an order on keys

Question 8

What do hash tables provide?

Answer 8

Key-index mapping in a simple and uniform way

Question 9

Describe a hash table

Answer 9

Data structure that implements a dictionary, by using a hash function to compute an index into an array of buckets from which the desired value can be found

Question 10

What is a hash function?

Answer 10

Takes a key and produces an index/hash code

Question 11

Describe the two stages in a hash function

Answer 11

• Hash key to its hash code l using the hash function h(k)

- Use the hash code as an index into a bucket containing the value associated with the key

Question 12

What is a collision?

Answer 12

Two different keys will map to the same hash code

Question 13

How is the has code further reduced to try and avoid collisions?

Answer 13

Using modulo arithmetic

Question 14

Give some desirable properties of hash functions

Answer 14

Gives two far apart hash codes for values close together
Two keys are unlikely to have the same hash code
Maps the keys uniformly across the range of hash codes

Question 15

What are two common methods of compression mapping?

Answer 15

Division method (modulo arithmetic)
Multiple and Divide

Question 16

When do compression mapping methods work best?

Answer 16

When m is prime

Question 17

Describe the Multiple and Divide (MAD) method for compression mapping

Answer 17

c(l) = (al + b)mod m for some a and b

Question 18

What is a cryptographic hash function?

Answer 18

Hash function that given a hash code l, it is very hard to generate a k such that h(k) = l
Also known as non-invertible function

Question 19

What are cryptographic hash functions used for?

Answer 19

Tamper proof files

Question 20

Pros of indexed storage classes

Answer 20

Very fast O(1) random access if you have an index, otherwise O(n)

Question 21

Disadvantages of indexed storage classes

Answer 21

Generally not expandable without copying

Question 22

Pros of sequential storage classes

Answer 22

Generally fast to expand by adding head or tail

Question 23

Disadvantage of sequential storage classes

Answer 23

Everything built by traversal from end(s) so generally O(n)

Question 24

Pros of associative storage classes

Answer 24

Use almost any value as key

Can address any key randomly

Question 25

Disadvantages of associative storage classes

Answer 25

Dynamic memory management

Question 26

How does storage get allocated in memory?

Answer 26

A pool of memory (the heap) Structured as a block chain Free and used blocks

Question 27

Consequences of the setup of memory allocation

Answer 27

Dynamic storage is easy to use but expensive to manage Allocating lots of small objects can cause heap fragmentation Garbage collection is relatively expensive, so doing it a lot can cause performance problems

Question 28

What is heap fragmentation?

Answer 28

Most of the memory is allocated in a large number of chunks, leaving a good percentage of your total memory un-allocated but un-usable for lots of circumstances

Question 29

What is the key performance measure of a hash table?

Answer 29

The load factor

Question 30

What is the load factor of a hash table/

Answer 30

Probability of a collision happening

Question 31

What is open addressing?

Answer 31

Use hashing to find a candidate bucket | Have a strategy to re map colliding keys and to find them again afterwards

Question 32

What is linear probing?

Answer 32

We hash the bucket and then step along the array until we find the key we are looking for

Question 33

What is quadratic probing?

Answer 33

Rather than linearily stepping through the array, use quadratic stepping where each jump is quadratically bigger

Question 34

What is secondary hashing?

Answer 34

Use a second hash function to pick the step, if we still get a collision, revert to linear probing

Question 35

What does open addressing allow?

Answer 35

Fixed memory footprint and management of collisions

Question 36

What is separate chaining?

Answer 36

Bucket is a list of key/value pairs | Hash to find the bucket then add it to the list

Question 37

Benefits of separate chaining

Answer 37

Unlimited storage | No worries about collisions, since they are handled automatically

Question 38

What is the worst case for separate chaining?

Answer 38

O(n)

Question 39

Average case of separate chaining?

Answer 39

O(n/m)

Question 40

What is extendible hashing?

Answer 40

Treats the hash code as a bit string that's expanded piecemeal

Question 41

What happens in extendible hashing when a collision occurs?

Answer 41

Bucket is split, consuming another bit of the hash code | Repeat until the hash codes differ

Question 42

What are infinite hash codes?

Answer 42

Use the key as a seed to a pseudo-random number generator | Call the number generator repeatedly to get new bits as required, indefinitely