Channi Studies

In this post, we will finally take a look into Python implementation of hash tables.  HashTable base class# Base class for a hash table that supports the insert, remove, and search # operations.class HashTable: # Returns a non-negative hash code for the specified key. def hashKey(self, key): return abs(hash(key)) # Inserts the specified key/value pair. If the key already exis..

A hash function is fast if the hash function can minimize collisions.  A perfect hash fucntion maps items to buckets with no collisions.It can be created if the number of items and all possible item keys are known beforehand.The runtime for insert, serach and remove is O(1) with it.  A good hash function should uniformly distribute items into buckets.With chaining, a good hash function results i..

Resize OperationA hash table resize opeartion increases the number of buckets, while preserving all existing items.A hash table with N buckets is commonly resized to the next prime number ≥ N * 2. A new array is allocated, and all items from the old array are re-insrted into the new array, making the resize opeartion's time complexity O(N).   Let's take a look into an example of hash table resiz..

Double Hashing is an open-addressing collision resolution technique that uses 2 different hash functions to compute bucket indices. Using hash functions h₁ and h₂, a key's index in the table is computed with the formula (h₁(key) + 𝑖 * h₂(key)) mod (tablesize) Inserting a key uses the formula, starting with 𝑖 = 0, repeatedly search hash table buckets until an empty bucket is found.Each time an ..