Hash Tables

Front 1

What are the two different types of hash tables?

Back 1

Chained hash table
Open address hash table

Front 2

What is a hash table?

Back 2

Its a data structure. An array.

Front 3

What is a hash function?

Back 3

A way to convert data into an integer. This number is then the location in the hash table.

Front 4

What is a key?

Back 4

The thing you convert into an integer.

Front 5

Why use an array?

Back 5

It provides fast random access.

Front 6

What is a collision?

Back 6

When some names lead to the same hash.

Front 7

Problems with hash function?

Back 7

Duplicates are inevitable,
Needs to produce an even spread of results.

Front 8

How big do the different types of tables need to be?

Back 8

Chained- same size as amount of data.
Open address- Twice the size as the amount of data.

Front 9

What is a chained hash table?

Back 9

Each location is the head of a chain,
Each location is a linked list.
Keys mapped to the same location are appended to the chain.
Retrieval means the chain must be searched and data removed.
Each location is like a bucket.

Front 10

Advantages of a chained hash table?

Back 10

Performance degrades gracefully.
Array size can be smaller than the number of data items.

Front 11

Disadvantages of a chained hash table?

Back 11

Retrieval can be slow due to the linked list needing to be traversed.
Efficiency decreased if the load factor is too high.
Efficiency decreases the more the hash function deviates from perfect hashing.
Worst case all the keys hash to the same bucket. Loses all the advantages of an array.

Front 12

What is load factor?

Back 12

number of entries/size
2 or 3 is acceptable

Front 13

What is an open addressed hash table?

Back 13

All the keys are stored in the table. Collisions resolved by probing- a process in which we search through locations to find an empty location in which to store the data.

Front 14

What are the different types of probing?

Back 14

Linear, double hashing and quadratic

Front 15

How does linear probing work?

Back 15

Look in array indexed by hash
If empty insert
If not empty try next cell along
Repeat until an empty cell is found.
use interval of 1

Front 16

Problems with linear probing

Back 16

Primary clustering
if a cluster forms then need to probe
Clustering leads to more probes
Operation slows down.

Front 17

How does quadratic probing work?

Back 17

Same as linear probing but makes increasingly large jumps through the array.
The sequence is the square of the number of tries so far attempted 1,4,9,16,25 etc

Front 18

Problems with quadratic probing

Back 18

The array must be a prime number
Overcomes primary clustering but suffers with secondary clustering
Keys with the same hash follow same probe sequence.

Front 19

How does double hashing work?

Back 19

Employs a second hashing function.
Need to ensure that probing visits every cell before visiting any cell twice.
Size of the table should be a prime or a power of 2

Front 20

What is the problem with deletion in a open address table

Back 20

If 2 keys have the same hash then probing must be used to store the second key. If the first item is deleted then unable to find the second.
Need to put a senital in to mark a location as used but empty.

Front 21

Advantages of an open addressed hash table

Back 21

Easy to implement

Front 22

Disadvantages of an open address hash table

Back 22

Doesnt cope well with lots of deletions.
Worse case is the table gets to full and then the hash is not in the table.
Full tables are bad- shouldnt be more than 80% full