Summarized Hashing Fundamentals

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;  
 }  

Tips for approaching Algorithmic problems

1. Exemplify (Investigation): Understand problem by creating minimum two examples of the algorithm. Use this step to create test-inputs.
2. Algo Pattern: Identify the similar algorithms (or patterns of algorithms) that you've encountered previously. Use this step to identify best applicable data-structure. 
3. Data Structure Brainstorm: This is hit and trial method. Try fitting relevant data structure till you find the best match. There are far better techniques for choosing it as well (watch this space and I shall update it shortly).
   
4. Simplify and Generalize (Divide and Conquer): Break-down the big problem into smaller fragments. Use this step to modularize. 
5. Base case and Build: Identify base case (eg. just one element case) for algorithm behavior and start from there. 
6. Algo Features: Keep a check on sequence, decision, repetition and Asymptotic Complexity (Big O notation)

JVM Architecture