Hash Maps

public class HashMapNode { 
    HashMapNode left; 
    HashMapNode right; 
    String key; 
    int hash; 
    int value; 
 
    /** 
     * Constructor 
     * @param key   Key of data point 
     * @param hash  Hash of data point 
     * @param value Value of data point 
     */ 
    public HashMapNode(String key, int hash, int value) { 
        this.key = key; 
        this.hash = hash; 
        this.value = value; 
    } 
 
    /** 
     * Adds new node to binary tree 
     * @param n New node 
     * @return  Old Value if Key and Hash already exist, otherwise -1 
     */ 
    public int add(HashMapNode n) { 
        if (n.hash == this.hash && n.key == this.key) { 
            int oldValue = this.value; 
            this.value = n.value; 
            return oldValue; 
        } 
        else if (n.hash <= this.hash) { 
            if (this.left == null) { 
                this.left = n; 
                return -1; 
            } 
            else { 
                this.left.add(n); 
            } 
        } 
        else { 
            if (this.right == null) { 
                this.right = n; 
                return -1; 
            } 
            else { 
                this.right.add(n); 
            } 
        } 
        return -1; 
    } 
 
    /** 
     * Finds data point based on Key and Hash 
     * @param key   Key of data point 
     * @param hash  Hash computed from Key 
     * @return      Node corresponding to Key and Hash, or null if not found 
     */ 
    public HashMapNode find(String key, int hash) { 
        if (this.hash == hash && this.key == key) { 
            return this; 
        } 
        if (hash <= this.hash) { 
            if (this.left == null) { 
                return null; 
            } 
            return this.left.find(key, hash); 
        } 
        if (this.right == null) { 
            return null; 
        } 
        return this.right.find(key, hash); 
    } 
 
    /** 
     * Deletes node from binary tree 
     * @param parent    Current parent of visited node 
     * @param key       Key of data point 
     * @param hash      Hash computed from Key 
     * @return          Parent of candidate node to be deleted, or null if not found 
     */ 
    public HashMapNode delete(HashMapNode parent, String key, int hash) { 
        if (this.hash == hash && this.key == key) { 
            return parent; 
        } 
        if (hash <= this.hash) { 
            if (this.left == null) { 
                return null; 
            } 
            return this.left.delete(this, key, hash); 
        } 
        if (this.right == null) { 
            return null; 
        } 
        return this.right.delete(this, key, hash); 
    } 
 
    /** 
     * Prints entire binary tree 
     */ 
    public void printTree(int depth) { 
        String prefix = "      "; 
        for (int i = 0; i < depth; i++) { 
            prefix += "---"; 
        } 
 
        System.out.println(prefix + "K: " + key + ", H: " + hash + ", V: " + value); 
        if (this.left != null) { 
            this.left.printTree(depth + 1); 
        } 
        if (this.right != null) { 
            this.right.printTree(depth + 1); 
        } 
    } 
}

public class HashMap { 
    HashMapNode[] buckets; 
    int numberOfBuckets; 
 
    /** 
     * Constructor 
     * @param numberOfBuckets   Number of buckets 
     */ 
    public HashMap(int numberOfBuckets) { 
        System.out.println("Initializing HashMap with " + numberOfBuckets + " buckets...\n"); 
        this.buckets = new HashMapNode[numberOfBuckets]; 
        this.numberOfBuckets = numberOfBuckets; 
    } 
 
    /** 
     * Hash function that adds sum of characters' ASCII values 
     * @param input Key of data point 
     * @return      Hash computed from Key 
     */ 
    private static int hashFunction(String input) { 
        int output = 0; 
        for (int i = 0; i < input.length(); i++) { 
            output += (int)input.charAt(i); 
        } 
        return output; 
    } 
 
    /** 
     * Adds new data point to HashMap 
     * @param key   Key of data point 
     * @param value Value of data point 
     * @return      Old value if Key and Value already exist, otherwise new Value 
     */ 
    public int put(String key, int value) { 
        int hash = hashFunction(key); 
        int bucketIndex = hash % numberOfBuckets; 
 
        System.out.println("Adding K: " + key + ", H: " + hash + ", V: " + value + "..."); 
 
        if (buckets[bucketIndex] == null) { 
            buckets[bucketIndex] = new HashMapNode(key, hash, value); 
            return -1; 
        } 
        else { 
            return buckets[bucketIndex].add(new HashMapNode(key, hash, value)); 
        } 
    } 
 
    /** 
     * Retrieves Value corresponding to Key 
     * @param key   Key of data point 
     * @return      Value of data point, or -1 if Key does not exist 
     */ 
    public int get(String key) { 
        int hash = hashFunction(key); 
        int bucketIndex = hash % numberOfBuckets; 
        if (buckets[bucketIndex] == null) { 
            int result = -1; 
            System.out.println("Value for K: " + key + " is " + result); 
            return result; 
        } 
        HashMapNode n = buckets[bucketIndex].find(key, hash); 
        if (n == null) { 
            int result = -1; 
            System.out.println("Value for K: " + key + " is " + result); 
            return result; 
        } 
        int result = n.value; 
        System.out.println("Value for K: " + key + " is " + result); 
        return result; 
    } 
 
    /** 
     * Removes data point from HashMap 
     * @param key   Key of data point 
     * @return      Removed Value, or -1 if Key does not exist 
     */ 
    public int remove(String key) { 
        int hash = hashFunction(key); 
        int bucketIndex = hash % numberOfBuckets; 
 
        if (buckets[bucketIndex] == null) { 
            System.out.println("No value is associated with K: " + key); 
            return -1; 
        } 
        else { 
            HashMapNode previous = buckets[bucketIndex].delete(new HashMapNode("", -1, -1), key, hash); 
            if (previous == null) { 
                System.out.println("No value is associated with K: " + key); 
                return -1; 
            } 
 
            if (previous.hash == -1) { 
                int result = buckets[bucketIndex].value; 
                buckets[bucketIndex] = null; 
                System.out.println("Removing K: " + key + " with V: + " + result + "..."); 
                return result; 
            } 
            else { 
                if (previous.left.hash == hash && previous.left.key == key) { 
                    HashMapNode n = previous.left; 
                    int result = n.value; 
 
                    if (n.left != null) { 
                        previous.left = n.left; 
                    } 
                    else { 
                        previous.left = n.right; 
                    } 
 
                    System.out.println("Removing K: " + key + " with V: + " + result + "..."); 
                    return result; 
                } 
                else { 
                    HashMapNode n = previous.right; 
                    int result = n.value; 
 
                    if (n.left != null) { 
                        previous.left = n.left; 
                    } 
                    else { 
                        previous.left = n.right; 
                    } 
 
                    System.out.println("Removing K: " + key + " with V: + " + result + "..."); 
                    return result; 
                } 
            } 
        } 
    } 
 
    /** 
     * Prints entire HashMap 
     */ 
    public void printHashMap() { 
        System.out.println("Current HashMap:\n"); 
 
        for (int i = 0; i < numberOfBuckets; i++) { 
            System.out.println("   Bucket " + i + ":"); 
 
            HashMapNode n = buckets[i]; 
            if (n == null) { 
                System.out.println("      Empty"); 
            } 
            else { 
                n.printTree(0); 
            } 
 
            System.out.println(); 
        } 
    } 
}

public class ImplementHashMap { 
    public static void main(String[] args) { 
        HashMap map = new HashMap(5); 
 
        map.put("James", 53); 
        map.put("Mary", 9); 
        map.put("John", 47); 
        map.put("Patricia", 10); 
        map.put("Robert", 17); 
        map.put("Jennifer", 34); 
        map.put("Michael", 71); 
        map.put("Linda", 36); 
        map.put("William", 12); 
        map.put("Elizabeth", 64); 
        map.put("David", 43); 
        map.put("Barbara", 74); 
        map.put("Barbara", 75); 
        map.put("Richard", 8); 
        map.put("Susan", 88); 
        map.put("Joseph", 31); 
        map.put("Jessica", 92); 
        map.put("Thomas", 21); 
        map.put("Sarah", 90); 
        map.put("Charles", 69); 
        map.put("Margaret", 58); 
 
        System.out.println(); 
 
        map.printHashMap(); 
 
        map.get("David"); 
        map.get("Barbara"); 
        map.get("Christopher"); 
 
        System.out.println(); 
 
        map.remove("David"); 
        map.remove("Susan"); 
 
        System.out.println(); 
 
        map.printHashMap(); 
 
        map.get("David"); 
        map.get("Barbara"); 
        map.get("Christopher"); 
    } 
}

Initializing HashMap with 5 buckets...

Adding K: James, H: 496, V: 53...
Adding K: Mary, H: 409, V: 9...
Adding K: John, H: 399, V: 47...
Adding K: Patricia, H: 813, V: 10...
Adding K: Robert, H: 622, V: 17...
Adding K: Jennifer, H: 817, V: 34...
Adding K: Michael, H: 691, V: 71...
Adding K: Linda, H: 488, V: 36...
Adding K: William, H: 719, V: 12...
Adding K: Elizabeth, H: 920, V: 64...
Adding K: David, H: 488, V: 43...
Adding K: Barbara, H: 683, V: 74...
Adding K: Barbara, H: 683, V: 75...
Adding K: Richard, H: 701, V: 8...
Adding K: Susan, H: 522, V: 88...
Adding K: Joseph, H: 617, V: 31...
Adding K: Jessica, H: 706, V: 92...
Adding K: Thomas, H: 620, V: 21...
Adding K: Sarah, H: 495, V: 90...
Adding K: Charles, H: 706, V: 69...
Adding K: Margaret, H: 819, V: 58...

Current HashMap:

   Bucket 0:
      K: Elizabeth, H: 920, V: 64
      ---K: Thomas, H: 620, V: 21
      ------K: Sarah, H: 495, V: 90

   Bucket 1:
      K: James, H: 496, V: 53
      ---K: Michael, H: 691, V: 71
      ------K: Richard, H: 701, V: 8
      ---------K: Jessica, H: 706, V: 92
      ------------K: Charles, H: 706, V: 69

   Bucket 2:
      K: Robert, H: 622, V: 17
      ---K: Susan, H: 522, V: 88
      ------K: Joseph, H: 617, V: 31
      ---K: Jennifer, H: 817, V: 34

   Bucket 3:
      K: Patricia, H: 813, V: 10
      ---K: Linda, H: 488, V: 36
      ------K: David, H: 488, V: 43
      ------K: Barbara, H: 683, V: 75

   Bucket 4:
      K: Mary, H: 409, V: 9
      ---K: John, H: 399, V: 47
      ---K: William, H: 719, V: 12
      ------K: Margaret, H: 819, V: 58

Value for K: David is 43
Value for K: Barbara is 75
Value for K: Christopher is -1

Removing K: David with V: + 43...
Removing K: Susan with V: + 88...

Current HashMap:

   Bucket 0:
      K: Elizabeth, H: 920, V: 64
      ---K: Thomas, H: 620, V: 21
      ------K: Sarah, H: 495, V: 90

   Bucket 1:
      K: James, H: 496, V: 53
      ---K: Michael, H: 691, V: 71
      ------K: Richard, H: 701, V: 8
      ---------K: Jessica, H: 706, V: 92
      ------------K: Charles, H: 706, V: 69

   Bucket 2:
      K: Robert, H: 622, V: 17
      ---K: Joseph, H: 617, V: 31
      ---K: Jennifer, H: 817, V: 34

   Bucket 3:
      K: Patricia, H: 813, V: 10
      ---K: Linda, H: 488, V: 36
      ------K: Barbara, H: 683, V: 75

   Bucket 4:
      K: Mary, H: 409, V: 9
      ---K: John, H: 399, V: 47
      ---K: William, H: 719, V: 12
      ------K: Margaret, H: 819, V: 58

Value for K: David is -1
Value for K: Barbara is 75
Value for K: Christopher is -1