Need of Hashing: Searching is typically the most frequent data operation. Linear Search on an unsorted array has O(n) while Binary Search on a sorted array has O(log n) time complexities. Hash Search further optimizes it to have a O(1) asymptotic time complexity.
Hash Function: A function that ensures uniform distribution of hash values & least collisions.
Collision: Collision happens when multiple keys hash to the same bucket.
Collision Avoidance Techniques:
- Direct Chaining/Separate Chaining: Collided elements are added to Linked list.
- Open Addressing: Involves Linear or Quadratic Probing.
- Linear Probing: [( H(x) + f(i) ) mod ArrLen] preferred in simple scenarios.
- Quadratic Probing: [( H(x) + f(i^2) ) mod ArrLen] preferred in simple scenarios.
- Closed Addressing: Involves Double Hashing.
- Double Hashing: [( H1(x) + (i * H2(x) ) ) mod ArrLen] where H2(x) = [PrimeNum – x mod PrimeNum] is for complex scenarios.
Collision Avoidance Tips:
- Use separate bucket for null key (special case).
- Avoid clustering of values one besides other.
- Choose twice array size than the values to be inserted.
- Choose Prime Number (smaller than table size) as the initial size of data-structure.
- For double-hashing, ensure that second Hash function (H2(x)) shouldn't evaluate to zero & should probe all locations.
Collision Avoidance Example: Following example is the actual
HashMap implementation code.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); // Used separate bucket for null-key.
int hash = hash(key.hashCode()); // Called Hash-function to get hash-value.
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // Stored element using above hash-value.
return null;
}
