Hashing Flashcards
What is the general idea of a hash table?
To hash/map an unordered list of entries to a specific position in an array
How does a hash table improve the time of the insert, delete and lookup methods?
Gives them a O(1) worst case complexity. It will always be O(1) if there are no collisions
What is the main disadvantage of a hash table?
that some positions will be null so spaces will arise which makes the methods more complex
What is the table size abbreviated as?
TS which is the number of buckets
What is the hash function?
The operations done to the key to yield it’s respective index value
When does a collision arise
When the hash function gives the same index as another key
How can the problem of collisions be solved?
Have each array point to another data structure(embedded DS)
How do the embedded DS effect the total time complexity?
balanced tree: O(logN)
list: O(N)
What tradeoff exists when choosing a TS?
Amount of space and the number of collisions
What methods can a hash function implement to spread out keys?
multiply some or all values by a constant
What is the problem with multiplying keys by a constant?
array overflow
What is the problem with adding properties together to get the index?
permutations
How is hashing done?
by performing operation(s) on the key to get an index value
What is each element being hashed called?
A bucket. The index corresponding to it is the bucket index
When does the number of items not correspond with the number of buckets?
When collisions occur
What is the most important attribute when choosing a key?
uniqueness
What is the most important attribute when choosing a hash function?
To get an even spread across the buckets/indeices a..b in other words no collisions
What is the most important attribute when choosing a TS?
Preferably a table size just above the number of items i.e get the load function as close to one as possible
What common operation is done on the bucket?
modulo
If the TS is 50 then what is the modulo hash function?
H(key) = key % 50
What does a perfect hash function accomplish?
avoids all collisions
What is wrong with the modulus hash function h(k) = k % 1000, and a table size 20000?
Collisions are likely since the function only hashes to the first 1000 indices
What does mid square hash function do?
- )key^2
2. )modulus of middle n digits by the table size
What is the load factor
The number of entries/TS
What is a trivial hash function and when is it appropriate?
When the actual keys are used as the index value. This is usually done when the data is small enough
How can hash functions be implemented in java?
overriding the equals/hash code
What does the common hash method known as extraction do?
separate the digits of the key
What does the common hash method known as weighting do?
Multiplies extracted digits by a constant
What does the common hash method known as folding do?
combines the extracted/weighted digits into one value
