package datastructures.hashtable;

import java.util.Arrays;

/**
 * Question 7.12: Design and Implement a hash table which uses chaining (linked
 * lists) to handle collisions.
 * 
 * @author Sudharsanan Muralidharan
 */
public class HashTable<K, V> {
  private HashTableNode<K, V>[] hashArray;
  private int hashSize = 32;
  private int size = 0;

  @SuppressWarnings("unchecked")
  public HashTable() {
    hashArray = (HashTableNode<K, V>[]) Arrays.copyOf(new Object[hashSize], hashSize, HashTableNode[].class);
  }
  
  public void put(K key, V value) {
    int index = hash(key);
    
    if(hashArray[index] == null) {
      hashArray[index] = new HashTableNode<K, V>(key, value);
    } else {
      HashTableNode<K, V> head = hashArray[index];
      hashArray[index] = addToLinkedList(head, key, value);
    }
  }

  public V get(K key) {
     int index = hash(key);
     return find(key, hashArray[index]);
  }
  
  private HashTableNode<K, V> addToLinkedList(HashTableNode<K, V> head, K key, V value) {
    HashTableNode<K, V> current = head;
    while(current != null) {
      if(current.key.equals(key)) {
        current.value = value;
        return head;
      }
      current = current.next;
    }
    
    HashTableNode<K, V> node = new HashTableNode<K, V>(key, value);
    node.next = head;
    return node;
  }
  
  private V find(K key, HashTableNode<K, V> head) {
    HashTableNode<K, V> current = head;
    while (current != null) {
      if (current.key.equals(key)) {
        return current.value;
      }
      
      current = current.next;
    }

    return null;
  }
  
  private int hash(K key) {
    return (key.hashCode() % hashSize);
  }
}

@@ -586,125 +586,8 @@
     
-%0A    if(hashArray%5Bindex%5D == null) %7B%0A      hashArray%5Bindex%5D = new HashTableNode%3CK, V%3E(key, value);%0A    %7D else %7B%0A      
 Hash
@@ -631,18 +631,16 @@
 x%5D;%0A    
-  
 hashArra
@@ -653,28 +653,16 @@
 x%5D = add
-ToLinkedList
 (head, k
@@ -673,22 +673,16 @@
 value);%0A
-    %7D%0A
   %7D%0A%0A  p
@@ -739,25 +739,40 @@
     
-return
+HashTableNode%3CK, V%3E node =
  find(
-key, 
 hash
@@ -783,17 +783,70 @@
 y%5Bindex%5D
-)
+, key);%0A     return (node != null) ? node.value : null
 ;%0A  %7D%0A  
@@ -883,20 +883,8 @@
  add
-ToLinkedList
 (Has
@@ -952,213 +952,99 @@
  V%3E 
-current = head;%0A    while(current != null) %7B%0A      if(current.key.equals(key)) %7B%0A        current.value = value;%0A        return head;%0A      %7D%0A      current = current.next;%0A    %7D%0A    %0A    HashTableNode%3CK, V%3E
+node = find(head, key);%0A    if(node != null) %7B%0A      node.value = value;%0A    %7D else %7B%0A     
  nod
@@ -1084,24 +1084,26 @@
 value);%0A    
+  
 node.next = 
@@ -1104,24 +1104,68 @@
 ext = head;%0A
+      head = node;%0A      size++;%0A    %7D%0A    %0A
     return n
@@ -1163,20 +1163,20 @@
  return 
-node
+head
 ;%0A  %7D%0A  
@@ -1190,22 +1190,33 @@
 ate 
-V find(K key, 
+HashTableNode%3CK, V%3E find(
 Hash
@@ -1235,16 +1235,23 @@
  V%3E head
+, K key
 ) %7B%0A    
@@ -1375,22 +1375,16 @@
  current
-.value
 ;%0A      

Refactor put and find