Hashing Flashcards
What is the basic definition of hashing?
Hashing involves using a function to map data to a specific position in a table, providing quick access and efficient storage. It is often used for quick lookup operations and resolving key-value pairs.
Describe the problem definition for hashing.
a map is a set of (key, value) pairs where each key maps to at most one value. Hashing involves storing and retrieving data in a way that allows efficient insertion, deletion, and search operations.
What are some real-world examples of hashing applications?
Compilers for maintaining symbol tables.
Password authentication, where keys are usernames and values are hashed passwords.
Data consistency checks to verify file integrity.
Dictionary operations in various applications.
Why is hashing widely used in data structures?
Hashing is widely used because it provides efficient insertion, search, and deletion operations, typically with an average time complexity of O(1). It is also a flexible technique, adapting to various applications where dynamic sets and fast lookup are required.
What is a direct-address table, and what is its limitation?
A direct-address table maps data directly to a specific slot, providing constant-time operations for insertion, search, and deletion. However, it can be inefficient if the universe of keys is much larger than the number of stored elements, leading to wasted space.
What is a hash map, and how does it differ from a direct-address table?
A hash map uses a hash function to determine the position of a key in a table, allowing for more efficient storage than direct-address tables. It uses a smaller array size and calculates the position from a hash function, reducing the potential for wasted space.
What is the key challenge with hash tables, and how can it be resolved?
The key challenge with hash tables is collision, where two keys map to the same slot. This can be resolved using various collision resolution techniques like chaining, open addressing, linear probing, quadratic probing, or double hashing.
What makes a good hash function?
Satisfy simple uniform hashing, where each key has an equal chance of mapping to any slot.
Ensure that similar keys hash to different values.
Be computed quickly, typically in O(1) time.
Avoid patterns or dependencies in the key universe.
What is the chaining method for resolving hash collisions?
The chaining method resolves collisions by placing all elements that hash to the same slot into a linked list. This approach allows multiple elements to share the same slot without causing collisions, but can lead to variable search times depending on list lengths.
What is the load factor, and why is it important in hash tables?
The load factor α is the ratio of the number of elements in the hash table to the total number of slots (α = n/m). It is important because it determines the average-case time complexity for operations like search, with lower load factors generally indicating better performance.
What is open addressing, and what are its main types?
Open addressing is a collision resolution method where no storage is provided for multiple keys in the same slot. If a collision occurs, the algorithm probes different slots using a probe sequence. The main types of open addressing are linear probing, quadratic probing, and double hashing.
What are the characteristics and challenges of double hashing in open addressing?
Double hashing uses two hash functions to calculate the probe sequence, reducing the risk of clustering. However, it requires the second hash function to be relatively prime to the table size to ensure a complete probe sequence permutation. This approach can alleviate clustering problems but requires careful implementation.
What is the expected number of probes for successful and unsuccessful searches in open addressing?
In open addressing:
The expected number of probes for unsuccessful searches is at most 1/(1 − α).
The expected number of probes for successful searches is at most (1/α) * log(1/(1 − α)).
What is the main challenge with open addressing when deleting elements?
The main challenge with open addressing when deleting elements is that it disrupts the probe sequence. This can lead to failed searches even when the element is present in the hash table. Special handling is required to maintain the correct probe sequence after deletions.
