5
\$\begingroup\$

Below is an implementation heavily based on climberig's implementation on Leetcode for LeetCode 706. Design HashMap. Just to preface, I am doing this in preparation for an exam.

The one below is dynamically sized, so it should increase the size of ListNode[] whenever the condition (keyCount > length * 0.90) has been met.

I was initially going to have that condition be (loadFactor > 0.75), but for whatever reason, the runtime seems to increase heavily (at least on LeetCode).

My main concern would be whether the hashing and collisions work accurately and spread evenly.

Any and all advice to improve the code below would be helpful.

import java.lang.Math;

class MyHashMap {

   int length = 10;
   int keyCount = 0;
   int loadFactor = keyCount / length;

   ListNode[] nodes = new ListNode[length];

   public void put(int key, int value) {
       int hashKey = hashFunction(key);

       if (nodes[hashKey] == null)
           nodes[hashKey] = new ListNode(-1, -1);

       ListNode prev = find(nodes[hashKey], key);

       if (prev.next == null) {
           keyCount++;
           prev.next = new ListNode(key, value);
       }
       else prev.next.val = value;

       rehash();
   }

   public int get(int key) {
       int hashKey = hashFunction(key);

       if (nodes[hashKey] == null)
           return -1;

       ListNode node = find(nodes[hashKey], key);

       return node.next == null ? -1 : node.next.val;
   }

   public void remove(int key) {
       int hashKey = hashFunction(key);

       if (nodes[hashKey] == null) return;

       ListNode prev = find(nodes[hashKey], key);

       // Key did not exist in the first place
       if (prev.next == null) return;

       // Removes the key by setting the previous node to the next node from the key
       prev.next = prev.next.next;
   }

   // Hash Function
   int hashFunction(int key) { return Integer.hashCode(key) % length;}


   ListNode find(ListNode bucket, int key) {

       ListNode node = bucket;
       ListNode prev = null;

       while (node != null && node.key != key) {
           prev = node;
           node = node.next;
       }
       return prev;
   }

   public void rehash() {
       if (keyCount > length * 0.90) {
           int oldLength = length;
           length = length * 2;
           ListNode[] newNodes = new ListNode[length];

           for (int i = 0; i < oldLength; i++) {

               if (nodes[i] == null) {
                   continue;
               }

               ListNode next = nodes[i].next;

               while (next != null) {
                   int key = next.key;
                   int value = next.val;

                   int hashKey = hashFunction(key);

                   if (newNodes[hashKey] == null)
                       newNodes[hashKey] = new ListNode(-1, -1);

                   ListNode prev = find(newNodes[hashKey], key);

                   if (prev.next == null) {
                       prev.next = new ListNode(key, value);
                   }
                   else {
                       prev.next.val = value;
                   }

                   next = next.next;
               }

           }

           nodes = newNodes;
       }


       printHash();
       System.out.println("---------------");
   }

   public void printHash() {
       for (int i = 0; i < length; i++) {
           if (nodes[i] == null) {
               System.out.println("Bucket Not Found");
               continue;
           }

           ListNode next = nodes[i].next;

           while (next != null) {
               System.out.print("Bucket Found | Key - " + next.key + " Value - " + next.val + " | ");
               next = next.next;
           }

           System.out.println();

       }
   }

   // ListNode to handle collisions
   class ListNode {
       int key, val;
       ListNode next;

       ListNode(int key, int val) {
           this.key = key;
           this.val = val;
       }
   }

   public static void main(String[] args) {
       MyHashMap ht = new MyHashMap();
       for (int i = 0; i < 100; i++) {
           int randomNumber = (int) (Math.random() * 100);
           ht.put(randomNumber, i);
       }
       ht.printHash();
   }
}

\$\endgroup\$
0
\$\begingroup\$

The behavior seems without design flaws.

However:

  • Using a dummy node in front of the linked list does not really save code. Inserting in front (LIFO, last-in-first-out) can be used for the code without dummy head.
  • Rehashing does not need to do a find in the newNodes.

(I hope you can do a diff.)

class MyHashMap {

    int length = 10;
    int keyCount = 0;
    int loadFactor = keyCount / length;

    ListNode[] nodes = new ListNode[length];

    public void put(int key, int value) {
        int hashKey = hashFunction(key);

        ListNode node = find(nodes[hashKey], key);

        if (node == null) {
            keyCount++;
            nodes[hashKey] = new ListNode(key, value, nodes[hashKey]);
        }
        else node.val = value;

        rehash();
    }

    public int get(int key) {
        int hashKey = hashFunction(key);

        //if (nodes[hashKey] == null)
        //    return -1;

        ListNode node = find(nodes[hashKey], key);

        return node == null ? -1 : node.val;
    }

    public void remove(int key) {
        int hashKey = hashFunction(key);

        nodes[hashKey] = removeFromBucket(nodes[hashKey], key);
//        if (nodes[hashKey] == null) return;
//
//        ListNode prev = find(nodes[hashKey], key);
//
//        // Key did not exist in the first place
//        if (prev.next == null) return;
//
//        // Removes the key by setting the previous node to the next node from the key
//        prev.next = prev.next.next;
    }

    // Hash Function
    int hashFunction(int key) { return Integer.hashCode(key) % length;}


    ListNode removeFromBucket(ListNode bucket, int key) {
        ListNode prev = null;
        ListNode node = bucket;
        while (node != null && node.key != key) {
            prev = node;
            node = node.next;
        }
        if (node == null) {
            return bucket; // Not found
        }
        if (prev != null) {
            prev.next = node.next;
            return bucket; // Found after head
        }
        // Found at head
        return node.next;
    }

    ListNode find(ListNode bucket, int key) {
        ListNode node = bucket;
        while (node != null && node.key != key) {
            node = node.next;
        }
        return node;
    }

    public void rehash() {
        if (keyCount > length * 0.90) {
            int oldLength = length;
            length *= 2;
            ListNode[] newNodes = new ListNode[length];

            for (int i = 0; i < oldLength; i++) {

                if (nodes[i] == null) {
                    continue;
                }

                ListNode node = nodes[i];

                while (node != null) {
                    int key = node.key;
                    int value = node.val;

                    int hashKey = hashFunction(key);

                    newNodes[hashKey] = new ListNode(key, value, newNodes[hashKey]);
                    node = node.next;
                }
            }
            nodes = newNodes;
        }


        printHash();
        System.out.println("---------------");
    }

    public void printHash() {
        for (int i = 0; i < length; i++) {
            if (nodes[i] == null) {
                System.out.println("Bucket Not Found");
                continue;
            }

            ListNode next = nodes[i];
            
            while (next != null) {
                System.out.print("Bucket Found | Key - " + next.key
                    + " Value - " + next.val + " | ");
                next = next.next;
            }

            System.out.println();

        }
    }

    // ListNode to handle collisions
    class ListNode {
        int key, val;
        ListNode next;

        ListNode(int key, int val, ListNode next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        MyHashMap ht = new MyHashMap();
        for (int i = 0; i < 100; i++) {
            int randomNumber = (int) (Math.random() * 100);
            ht.put(randomNumber, i);
        }
        ht.printHash();
    }
}

There is an issue with a new length having an integral multiple on rehashing:

      hash keys:
keys  length=10  length=2*10
  7       7          7
 17       7         17
 27       7          7
 37       7         17

I find this intellectually irritating, but find no drawbacks.

The solution would be something like:

            length = 2*length + 3;
            length = 3*length/2;
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.