0
\$\begingroup\$

I just finished implementing a HashMap in Java, with methods:

  • add(String key, Integer value)
  • get(String key)
  • remove(String key)
  • printHashMap()

Is this the correct way to implement a HashMap? I am implementing a load factor feature that automatically increases the size of the HashMap until the load factor is satisfied.

Bucket.java

public class Bucket {
    // Each Entry contains a key-value pair
    String key;
    Integer value;
    Bucket next; // Used for chaining

    public Bucket(String key, Integer value) {
        this.key = key;
        this.value = value;
    }
}

HashMap.java

/*
 * Author: Henry Zhu
 * Building a HashMap that resizes based on load factor
 */

import java.util.ArrayList;

public class HashMap {
    private ArrayList<Bucket> data;
    private double loadFactor = 0.75;
    private int initialCapacity = 16;
    private int numBuckets = 0;

    public HashMap() {
        this.data = new ArrayList<Bucket>();

        // Fill the list up to the initial capacity
        for (int i = 0; i < initialCapacity; i++) {
            this.data.add(null);
        }
    }

    public void remove(String key) {
        /*
         * get hash code of key
         * index is hash code % list's size
         * let head be the bucket @ the index
         * let previous be null
         * while the head is not null:
         *     if the head's key = key of bucket we want to delete:
         *         Case 1 (B1 -> B2 (to delete) -> B3):
         *         previous = B1, so set B1.next = B3
         *         end result: B1 -> B3
         *         Case 2 (B1 -> B2 (to delete) -> null):
         *         previous = B1, so set B1.next = null
         *         Case 3 (B1 (to delete) -> B2):
         *         previous = null, set list[index] = B2
         *         Case 4 (B1 (to delete) -> null):
         *         set list[index] = null;
         *         
         *         return
         *     else:
         *         previous becomes head
         *         head becomes head.next
         */
        int hashCode = Math.abs(key.hashCode());
        int index = hashCode % this.data.size();

        Bucket head = this.data.get(index);
        Bucket previous = null;
        while (head != null) {
            if (head.key.equals(key)) { // Evaluates Cases 1 and 2
                if (previous != null) {
                    if (head.next != null) { // Case 1
                        previous.next = head.next;
                    } else { // Case 2
                        previous.next = null;
                    }
                } else { // Evaluates Case 3 and 4
                    if (head.next != null) { // Case 3
                        this.data.set(index, head.next);
                    } else { // Case 4
                        this.data.set(index, null); 
                    }
                }

                numBuckets--;

                return;
            } else {
                previous = head;
                head = head.next;
            }
        }
    }

    public Integer get(String key) {
        /*
         * get the hash code of the key
         * index is the hash code % list's size
         * begin the search:
         *     let head = the bucket at the index
         *     while the head i snot null:
         *         if the head's key = the key we're looking for:
         *             return head.value
         *         if not?
         *             head becomes head.next
         * return -1
         */
        int hashCode = Math.abs(key.hashCode());
        int index = hashCode % this.data.size();

        Bucket head = this.data.get(index);
        while (head != null) {
            if (head.key.equals(key)) {
                return head.value;
            } else {
                head = head.next;
            }
        }

        return -1;
    }

    public void add(String key, Integer value) {
        /*
         * get hash code of the key
         * index is hash code % list's size
         * check if key already exists
         *     if key exists: update the bucket
         *     if key doesn't exist:
         *         if index is already occupied: use chaining
         *         if index isn't already occupied, place the bucket at the index
         */
        int hashCode = Math.abs(key.hashCode());
        int index = hashCode % this.data.size();

        Bucket bucket = this.data.get(index);

        boolean alreadyExists = false;

        // See if the key already exists in the HashMap
        for (int i = 0; i < this.data.size(); i++) {
            if (this.data.get(i) != null && this.data.get(i).key.equals(key)) {
                this.data.set(i, new Bucket(key, value));
                alreadyExists = true;
            }
        }

        if (!alreadyExists) {
            // If the spot is occupied, implement the chaining algorithm (uses a LinkedList)
            if (this.data.get(index) != null) {
                Bucket head = this.data.get(index);
                Bucket previous = head;

                while (head != null) {
                    previous = head;
                    head = head.next;
                }

                previous.next = new Bucket(key, value);
            }
            else {
                bucket = new Bucket(key, value);
                this.data.set(index, bucket);
            }
        }

        // Check to see if the capacity of the list needs to be increased.
        numBuckets++;

        if (new Double((1.0 * numBuckets) / this.data.size()).compareTo(loadFactor) >= 0) {
            while (new Double((1.0 * numBuckets) / this.data.size()).compareTo(loadFactor) >= 0) {
                // Increase the size of the list until the load factor is satisfied
                this.data.add(null);
            }
        }
    }

    public void printMap() {
        /*
         * Go through every element in the list
         * if element is null:
         *    print null
         * if element is a bucket:
         *    set head to equal the element
         *    while the head is not null:
         *       print the head's value
         *       if head.next is not null
         *           print "-> " 
         *       set head = head.next
         */
        for (int i = 0; i < this.data.size(); i++) {
            if (this.data.get(i) == null) {
                System.out.println("[" + i + "] = null");
            } else {
                Bucket head = this.data.get(i);

                String text = "[" + i + "] = ";

                while (head != null) {
                    text += ("(" + head.key + ", " + head.value + ")");

                    if (head.next != null) {
                        text += " -> ";
                    }

                    head = head.next;
                }

                System.out.println(text);
            }
        }
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Is this the correct way to implement a HashMap?

There are multiple ways to write them. Did you look any up?

Your cardinal sin is not writing tests to verify that the code works. And it looks like there's a serious issue here - any reasonably thorough testing should reveal it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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