Hashing and finding closest points Flashcards
What is a dictionary data structure?
A dictionary is a data structure that supports MakeDictionary
What is the universe U in the context of dictionaries?
The universe ( U ) is the set of all possible elements that could be part of the subset ( S ) maintained by the dictionary.
Why is hashing used for dictionaries?
Hashing allows efficient dictionary operations by mapping a large universe ( U ) into a smaller hash table using a hash function.
What is a hash function?
A hash function maps elements from the universe ( U ) to positions in a smaller array (hash table) to store and retrieve elements efficiently.
What is a collision in a hash table?
A collision occurs when two different elements ( u ) and ( v ) are mapped to the same hash table position by the hash function.
How does chaining resolve hash collisions?
In chaining
What are the operations supported by hash tables?
Hash tables support Insert (add an element), Delete (remove an element), and Lookup (check membership and retrieve data).
What makes a hash function ‘good’?
A good hash function minimizes collisions by distributing elements uniformly across the hash table.
What is the probability of a collision in uniform random hashing?
With uniform random hashing, the probability that two random elements collide is exactly ( 1/n ), where ( n ) is the size of the hash table.
What is a universal class of hash functions?
A universal class of hash functions ensures that for any two distinct elements ( u ) and ( v ), the probability that ( h(u) = h(v) ) is at most ( 1/n ).
What is the advantage of universal hash functions?
Universal hash functions ensure efficient dictionary operations by reducing the likelihood of collisions, even in the worst case.
How is a universal hash function constructed?
A universal hash function can be constructed using linear functions modulo a prime ( p ), such as ( h(x) = (\sum a_i x_i) \mod p ).
Why is a prime ( p ) used in universal hashing?
Using a prime ( p ) ensures that modular arithmetic avoids divisibility issues, providing better collision guarantees.
What is the complexity of dictionary operations using hashing?
With universal hashing, the expected complexity of Insert, Delete, and Lookup operations is ( O(1) ).
How are hash tables used in the closest-pair algorithm?
Hash tables help divide the unit square into subsquares, allowing efficient Lookup of nearby points during the closest-pair algorithm.
What is the expected time complexity of the randomized closest-pair algorithm?
The algorithm runs in ( O(n) ) time for processing points plus ( O(n) ) dictionary operations.
Why is randomness used in the closest-pair algorithm?
Randomness is used to order points and in hash functions, ensuring efficiency and reducing worst-case scenarios.
What are subsquares in the closest-pair algorithm?
Subsquares divide the unit square into regions of side length ( \delta/2 ), used to group points for efficient distance computation.
What is the significance of the subsquares’ properties?
Subsquares ensure that only nearby points need to be checked for distances less than ( \delta ), reducing unnecessary computations.
How does the closest-pair algorithm update its state when ( \delta ) changes?
When ( \delta ) decreases, a new dictionary is created with updated subsquares, and all points are reinserted.
What is the relationship between hash table collisions and dictionary performance?
Fewer collisions lead to shorter chains in hash table entries, improving the efficiency of dictionary operations.
How is a hash value computed efficiently in universal hashing?
Hash values are computed using linear functions with modular arithmetic, requiring ( O(\log N / \log n) ) operations for ( n ) elements.
Why is universal hashing effective for dynamic dictionaries?
Universal hashing minimizes collisions across arbitrary input sets, ensuring efficient operations even with adversarial input.
How does randomization in hashing improve performance?
Randomization spreads elements uniformly across the hash table, reducing the chance of clustering and long chains.
What is the expected number of Insert operations in the closest-pair algorithm?
The expected number of Insert operations is ( O(n) ), as updates to the closest pair become less frequent over time.
How do dictionary operations contribute to the overall complexity of the closest-pair algorithm?
Efficient dictionary operations ensure the total work remains ( O(n) ) in expectation, matching the algorithm’s computational efficiency.
