Hash Tables (Module 7) Flashcards
What is a data structure that maps keys to values?
Hash table
What is a hash table also known as?
hash map
Why are hash tables different from array?
they use different types of keys and convert them using hash functions
What are the 4 applications of hash tables?
1) database indexing
2) caching
3) Symbol tables in compilers
4) networking
which hash table application retrieves records using unique keys?
database indexing
Which hash table application stores and accesses frequently-used data?
caching
Which hash table application maps variables names in memory locations?
symbol tables in compilers
Which hash table application stores routing tables and MAC addresses?
networking
How does the hashing mechanism work?
1) Hash function turns key into hash code
2) hash code is used to index into a hash table
What 2 things does a hash function’s quality influence in a hash table?
1) hash table’s speed
2) hash table’s ability to handle collisions effectively
A hash function should preferably compute a hash code in ______ time complexity.
O(1)
A hash function should distribute hash values ________ across the table
evenly
A hash function should minimize _________.
collisions
What does it mean when a hash function experiences a collision?
two inputs are mapped to the same index
For numerical keys, what is the formula for Modulo hashing?
hash(k) = k*modm
For numerical keys, what is the formula for Multiplicative hashing?
hash(k) = m * ((k * A) mod 1)
For numerical keys, what is the formula for Bitwise Operations?
hash(k) = (k $ (k»_space; r)) mod m
How do you initialize a hashing table?
1) use arrays and have each element represent hash key mapping
2) use linked list to store multiple elements that hash to the same index
