Hashing Techniques Quiz

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.