2
\$\begingroup\$

I have implemented a hash map in Java, using generics. Let me know if I can improve it.

package Arrays;

import java.util.NoSuchElementException;
import java.util.Scanner;

class MapNode<K, V> {
    private K key;
    private V value;
    private MapNode<K,V> next;

    public MapNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }

    public K getKey() {
        return this.key;
    }

    public V getValue() {
        return this.value;
    }

    public MapNode<K, V> getNext() {
        return this.next;
    }

    public void setNext(MapNode<K, V> next) {
        this.next = next;
    }
}

class HashMapOps<K,V> {
    private int size;
    private MapNode<K,V>[] bucket;

    public HashMapOps(int capacity) {
        this.bucket = new MapNode[nextPrime(capacity)];
        this.size = 0;
    }

    public void put(K key, V value) {
        int hashKey = getHashCode(key);
        MapNode<K, V> cur = new MapNode<K, V>(key, value);

        if(bucket[hashKey] == null) {
            bucket[hashKey] = cur;
        } else {
            cur.setNext(bucket[hashKey]);
            bucket[hashKey] = cur;
        }
        size++;
        return;
    }

    public V get(K key) {
        int hashKey = getHashCode(key);
        if(bucket[hashKey] == null) {
            throw new NoSuchElementException();
        }

        MapNode<K, V> start = bucket[hashKey];
        MapNode<K, V> end = start;

        if(start.getKey().equals(key)) return start.getValue();

        while(end.getNext() != null && !end.getNext().getKey().equals(key)) {
            end = end.getNext();
        }

        if(end.getNext() != null && end.getNext().getKey().equals(key)) {
            return end.getNext().getValue();
        }
        throw new NoSuchElementException();
    }

    public int nextPrime(int num) {
        if(num % 2 == 0) return num + 1;

        for(; !isPrime(num); num +=2);

        return num;
    }

    public boolean isPrime(int num) {
        if(num == 2 || num == 3) return true;
        if(num == 1 || num % 2 == 0) return false;

        for(int i = 3; i * i <= num; ++i) {
            if(num % i == 0) return false;
        }
        return true;
    }

    public int getHashCode(K key) {
        int hashValue = key.hashCode();
        hashValue %= bucket.length;

        if(hashValue < 0) {
            hashValue += bucket.length;
        }
        return hashValue;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        int length = bucket.length;
        bucket = new MapNode[length];
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    public void print() {
        MapNode<K, V> cur = null;
        MapNode<K, V> next = null;
        for(int i = 0; i < bucket.length; ++i) {
            cur = bucket[i];
            next = cur;
            System.out.println("================");
            System.out.println("Bucket " + i);

            while(next != null) {
                System.out.println(next.getKey() + ", " + next.getValue());
                next = next.getNext();
            }
            System.out.println("===============================");
        }
    }
}

public class Map {
    public static void main(String[] args) {
        HashMapOps<Integer, Integer> hashMap = new HashMapOps<>(5);
        Scanner in = new Scanner(System.in);
        int  choice = 0;
        int key = 0;
        int value = 0;
        do {

            System.out.println("What would you like to do?");
            System.out.println("1. Insert a new hashmap entry?");
            System.out.println("2. Retrieve a value by its key?");
            System.out.println("3. Check if hashmap is empty?");
            System.out.println("4. Clear the hashmap?");
            System.out.println("5. Print hashmap?");
            System.out.println("6. Exit?");

            choice = in.nextInt();

            switch(choice) {
            case 1: 
                System.out.println("Enter the key followed by the value");
                key = in.nextInt();
                value = in.nextInt();
                hashMap.put(key, value);
                break;

            case 2:
                System.out.println("Enter the key you want to retrieve.");
                key = in.nextInt();
                System.out.println(hashMap.get(key));
                break;

            case 3:
                System.out.println("Is hashmap empty? := " + hashMap.isEmpty());
                break;

            case 4:
                hashMap.clear();
                System.out.println("HashMap is cleared, current size is := " + hashMap.size());
                break;

            case 5:
                hashMap.print();
                break;

            case 6:
                break;
            }

        } while(choice != 6);
        in.close();
    }
}
\$\endgroup\$
5
\$\begingroup\$

Memory leak?

Usually when you put a (key, value) in a map where key already exists, the new value overwrites the existing value. This implementation doesn't. The values just accumulate, but only the most recently put value is accessible.

Encapsulation

The MapNode class is an implementation detail that users of your map should not have to know about. It would be better to make MapNode a private static inner class of the map implementation, to keep it neatly hidden.

Also, MapNode.key should be final, as it should never change.

Data structure design

Some obvious features are missing:

  • The map has a fixed number of buckets. Even with a good hashing function, the hash map will lose all its benefits if you insert too many elements.
  • There's no way to remove elements.
  • The only way to check if the map contains an element is to call get and catch NoSuchElementException. Exception handling is very undesirable for such a basic functionality.

Some elements are surprising to see in a hash map implementation, and don't really bring good value:

  • Calculating the next prime, starting from the specified capacity. From a user's perspective, the capacity will be inexplicably and magically set to some value that is not what the user specified. This will strike most users as unexpected. It's unnecessary complexity, for no benefit.
  • HashMapOps is a strange name for a hash map. It could be just HashMap.

Technique

The bucket[hashKey] = cur; line is duplicated in both branches of the conditional:

if (bucket[hashKey] == null) {
    bucket[hashKey] = cur;
} else {
    cur.setNext(bucket[hashKey]);
    bucket[hashKey] = cur;
}

So it could be moved out after the conditional:

if (bucket[hashKey] != null) {
    cur.setNext(bucket[hashKey]);
}
bucket[hashKey] = cur;

In fact, if bucket[hashKey] is null, there's no harm in setting it in cur, so you don't really need the conditional at all, and simplify the code to just this:

cur.setNext(bucket[hashKey]);
bucket[hashKey] = cur;

The empty return statement at the end of the void put method is unnecessary, you should remove it.


The get method can be written much simpler:

public V get(K key) {
    int hashKey = getHashCode(key);
    for (MapNode<K, V> node = bucket[hashKey]; node != null; node = node.getNext()) {
        if (node.getKey().equals(key)) {
            return node.getValue();
        }
    }
    throw new NoSuchElementException();
}
\$\endgroup\$
1
\$\begingroup\$

I subscribe to most of what Janos has said, but I would add a few points.

Interfaces are your friends

Java has an interface java.util.Map<K, V> for maps. If you implement the interface, your class becomes a lot more useful. (This does also prompt the question: why are you ? Is it just for the sake of it, or do you want to improve on java.util.HashMap<K, V> in some specific metric? If the latter, it may make sense to extend java.util.AbstractMap<K, V>).


Primes

I don't entirely agree with Janos' comment on the initial size of the array, although I do agree that it should expand. The point of the capacity parameter is as a hint for the initial capacity, not as a hard limit beyond which performance may suffer. That said, what's going on with nextPrime?

    public int nextPrime(int num) {
        if(num % 2 == 0) return num + 1;

That's not necessarily a prime. Was it intended to say num = num + 1 to allow the subsequent loop to just go through odd numbers?

        for(; !isPrime(num); num +=2);

Loops with empty bodies are great for code golf, but not great for maintenance. Prefer

while (!isPrime(num)) num += 2;
    public boolean isPrime(int num) {
        if(num == 2 || num == 3) return true;
        if(num == 1 || num % 2 == 0) return false;

Ok, 2 is treated as a special case to allow you to skip through just the odd numbers.

        for(int i = 3; i * i <= num; ++i) {

But that doesn't just skip through the odd numbers. Was the update intended to be i += 2?

Also, I think there's a risk that if you create a lot of maps with a large initial capacity that this could become a bottleneck. There's no obvious reason for requiring the next prime: I suggest that an alternative would be to have an array of pre-calculated primes which are just less than a power of two, starting with 7. Then it's nice and fast to find a suitable size, and it's convenient for when you extend the code to resize the array of buckets if the chains start getting too long. As a bonus, you don't even need to calculate them yourself: the Primes Pages include primes just smaller than a power of two. The other reason for choosing just smaller rather than just larger than a power of two is that it might interact better with whatever memory allocator is being used under the hood.


Separation of responsibilities

    public void print() {
        ...
    }

Some OO purists would argue that you should ask an object to do something for you rather than to return data to you, but most Java practitioners are not such purists. I would expect to see an override of toString() rather than a print() method.

(Also, for preference, I would follow java.util.Map<K, V>'s convention for the toString() of a map).


Separate implementation from test

public class Map {
    ...

This looks like a test wrapper rather than the "main" code. It would be nice to offset it in a separate file. There's also a good case to be made for writing unit tests before you write a TUI test wrapper, and I think you would find reviews of unit tests more useful than reviews of a TUI test wrapper.

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

Your put() method always creates a new value instead of modifying the existing value if it is already there. That is why it is leading to "Memory Leak" as pointed out by @janos

\$\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.