Hash table Flashcards
What does a hash table consist of?
- a hash function
2. An array of size N
What 2 properties does a hash function comprise of?
- A hash code that will map a key to some integer
2. A compression function that will restrict that integer to a value between 0 and N-1
What is the goal of the hash function?
allocate a space for the keys in a seemingly random way
Which hash code is not suitable for numeric values and strings?
Memory address
How does the integer cast hash code work briefly? And what is it suitable for?
Reinterpreting the bits of the key as integers
Which hash code is suitable for strings?
polynomial accumulation
How does component sum work?
We partition the bits of the key into components of fixed length
and we sum the components ignoring overflows
Name the 2 types of compression functions and their definitions
MAD: (ax+b) mod n
Division: y mod n
What is separate chaining and how does it work? Name on disadvantage of it
it is a collision handling method, it works by making each cell in an array point to a list of values mapped to that position.
- it uses more storage space
What is open addressing?
It is a collision handling method that causes an entry to be mapped to a different cell
What is open addressing?
It is a collision handling method that causes an entry to be mapped to a different cell
What is linear probing? and name a disadvantage of it
Collision handling method where an entry is placed in the cell forward-next to the one it collided with
a longer sequence of probes are formed as collisions will continue to occur
Procedure for the remove function in linear probing
- search for the key in the table
- If found, replace value AVAILABLE
- return element or null if not found
What is the big oh of searches, insertions and removals in a hash table? When does this worst case occur?
O(n)
occurs when all of the entries collide
Give the formula for the load factor and discuss how it affects the hash table
a = n/N
n is the number of entries and
N is the size of the table
