18 Questions
In Cuckoo Hashing, what happens when a key is pushed out of its current location?
The key is inserted into its alternative location
Which operation in Cuckoo Hashing has an expected O(1) time complexity?
Insert
What strategy is used to maintain a dynamic set of buckets in Extendible Hashing?
Trie organization
What triggers other relocations in cascade in Cuckoo Hashing?
Pushing a key into its alternative location
Which type of hashing scheme is known for being typically 20-30% slower than linear probing?
Cuckoo Hashing
What action leads to the hash table being rebuilt with new hash functions in Cuckoo Hashing?
Creating a cycle due to relocations
Which technique is used to solve collisions in Java 8 HashMap?
Chaining
What is the hash function used in Java 8 HashMap for calculating hash values?
static final int hash(Object key) { ... }
In Java 10 HashMap, when does the resizing of the table occur?
When load factor exceeded
What happens in Linear Probing if the bucket for insertion is already occupied?
Insertion in the next available bucket
How are deletions handled in Linear Probing?
Shift next cells in cascade if needed
What strategy does Java 8 HashMap use when a bin gets overpopulated?
Switch its content to a Tree
What is the main difference between Quadratic Probing and Linear Probing?
Quadratic Probing modifies the initial index based on a quadratic formula, while Linear Probing increments the index linearly.
What condition must be satisfied for Linear Probing to guarantee O(1) expected time complexity?
Ensuring the load factor is not too high
In Python 2.7 dictionaries, how is collision resolved when using probing?
Utilizing a pseudo-random probing sequence
What is the purpose of resizing the hash table in Python 2.7 dictionaries?
To maintain a specific load factor
Why does Python 2.7 use the low order bits of the key's hash for the initial index?
For fast computation with good locality
What makes Quadratic Probing slower than Linear Probing in practice?
The quadratic increase in probe positions
Test your knowledge on hashing techniques including Quadratic Probing and Linear Probing. Learn about the differences and guarantees of these methods from B. Groz '19.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
