Resizing a map implementation in java

I am writing my own hashmap. I am able to define put/get methods. When I am trying to resize the array, I am getting null values:

 public void resize() {
        if (100 * size >= 75 * capacity) {
            int oldcap = capacity;
            capacity = capacity * 2;
            Entry[] resizedBuckets = new Entry[capacity];

            for (int i = 0; i < oldcap; i++) {
                resizedBuckets[i] = this.buckets[i];
            }

            this.buckets = resizedBuckets;
        }
    }

My whole code is as below:

package lib;

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;

    Entry(K key, V value, Entry next) {
        this.key = key;
        this.value = value;
    }

}


public class MyMap<K, V> {
    Entry[] buckets;
    int size = 0;
    static int capacity = 2;

    MyMap(int capacity) {
        this.buckets = new Entry[capacity];
    }

    public MyMap() {
        this(capacity);
    }

    public void resize() {
        if (100 * size >= 75 * capacity) {
            int oldcap = capacity;
            capacity = capacity * 2;
            Entry[] resizedBuckets = new Entry[capacity];

            for (int i = 0; i < oldcap; i++) {
                resizedBuckets[i] = this.buckets[i];
            }

            this.buckets = resizedBuckets;
        }
    }

    public void put(K key, V value) {
        int bucket = key.hashCode() % capacity;

        //i have bucket it
        Entry newEntry = new Entry<K, V>(key, value, null);

        if (this.buckets[bucket] == null) {
            this.buckets[bucket] = newEntry;
            size++;
        } else {
            Entry currentNode = this.buckets[bucket];
            Entry prevNode = null;
            while (currentNode.next != null && currentNode.key != key) {
                prevNode = currentNode;
                currentNode = currentNode.next;
            }

            if (currentNode.key == key) {
                if (prevNode == null) {
                    newEntry.next = currentNode.next;
                    this.buckets[bucket] = newEntry;
                } else {
                    newEntry.next = currentNode.next;
                    prevNode.next = newEntry;
                }
            } else {
                currentNode.next = newEntry;
                size++;
            }
        }
        resize();
    }

    public V get(K key) {
        int bucket = key.hashCode() % capacity;
        Entry currentBucket = this.buckets[bucket];
        while (currentBucket != null) {
            if (currentBucket.key == key)
                return (V) currentBucket.value;
            currentBucket = currentBucket.next;
        }
        return null;
    }
}

class MyMain {
    public static void main(String[] args) {
        MyMap<String, Integer> myMap = new MyMap<>();
        myMap.put("name", 1);
        myMap.put("2name", 2);
        myMap.put("3name", 2);
        myMap.put("4name", 3);
        myMap.put("5name", 2);
        myMap.put("6name", 2);
        myMap.put("3name", 3);

        System.out.println(myMap);

        System.out.println(myMap.get("name"));
        System.out.println(myMap.get("2name"));
        System.out.println(myMap.get("3name"));


    }
}

I am getting following output:

[email protected]
null
null
3

I should be getting:

1 2 3

What’s the reason? I think the issue is with resize method, but I am unable to figure it out.

Answer

As mentioned in the comments your bucket index changed as capacity was increased during the resize operation. And thus int bucket = key.hashCode() % capacity; inside put and get returns a different bucket index than before.

I haven’t tested it, but I think, if you do

resizedBuckets[this.buckets[i].getKey().hashCode() % capacity] = this.buckets[i];

inside the resize method, this might already work.

As @Voo pointed out, the above change only works as long as you don’t have any hash collisions before resizing. For a complete solution you will need to recalculate the index for every key!

Leave a Reply

Your email address will not be published. Required fields are marked *