Hashing Techniques Quiz

In Cuckoo Hashing, what happens when a key is pushed out of its current location?

Which operation in Cuckoo Hashing has an expected O(1) time complexity?

What strategy is used to maintain a dynamic set of buckets in Extendible Hashing?

What triggers other relocations in cascade in Cuckoo Hashing?

Which type of hashing scheme is known for being typically 20-30% slower than linear probing?

What action leads to the hash table being rebuilt with new hash functions in Cuckoo Hashing?

Which technique is used to solve collisions in Java 8 HashMap?

What is the hash function used in Java 8 HashMap for calculating hash values?

In Java 10 HashMap, when does the resizing of the table occur?

What happens in Linear Probing if the bucket for insertion is already occupied?

How are deletions handled in Linear Probing?

What strategy does Java 8 HashMap use when a bin gets overpopulated?

What is the main difference between Quadratic Probing and Linear Probing?

What condition must be satisfied for Linear Probing to guarantee O(1) expected time complexity?

In Python 2.7 dictionaries, how is collision resolved when using probing?

What is the purpose of resizing the hash table in Python 2.7 dictionaries?

Why does Python 2.7 use the low order bits of the key's hash for the initial index?

What makes Quadratic Probing slower than Linear Probing in practice?

Cuckoo Hashing

When a key is pushed out of its current location, it triggers other relocations in a cascade.
The search operation has an expected O(1) time complexity.
If an element is pushed out of its current location, the hash table is rebuilt with new hash functions.

Extendible Hashing

A dynamic set of buckets is maintained using a strategy where buckets can be split or merged based on the load factor.

Hashing Schemes

Cuckoo Hashing is a type of hashing scheme that is typically 20-30% slower than linear probing.

Java 8 HashMap

Collisions are solved using a technique called chaining, where a linked list is used to store colliding elements.
The hash function used to calculate hash values is the built-in hashCode() method.
When a bin gets overpopulated, Java 8 HashMap uses a strategy called treeification, where the bin is converted into a balanced tree.

Java 10 HashMap

The resizing of the table occurs when the load factor exceeds a certain threshold.

Linear Probing

If the bucket for insertion is already occupied, the algorithm probes subsequent buckets until an empty bucket is found.
Deletions are handled by marking the bucket as deleted, but not actually removing the element.
The main difference between Quadratic Probing and Linear Probing is the probing sequence used to find an empty bucket.
For Linear Probing to guarantee O(1) expected time complexity, the load factor must be less than 0.5.

Python 2.7 Dictionaries

Collisions are resolved using linear probing.
The purpose of resizing the hash table is to maintain a good load factor and prevent collisions.
The low order bits of the key's hash are used for the initial index to minimize collisions.
Quadratic Probing is slower than Linear Probing in practice because it has a higher chance of clustering, leading to more collisions.

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.