1
\$\begingroup\$

I have taken a stab at implementing a HashMap in Java. To deal with collisions I implemented sort of a LinkedList using a dataNode. I am not very confident of my implementation hence looking for some feedback.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class MyHashMap<K, V> implements SampleMap<K, V>{

    private double loadFactor;
    private int size;
    private int capacity; // Number of elements in the HashMap
    Set<K> hashSetKeys = new HashSet<>();

    //
    private dataNode[] hashTable;

    // Constructor: Default values for instance variables
    public MyHashMap() {
        this(16, 0.75);
    }

    // Constructor: starts with an initialSize for the Map
    public MyHashMap(int initialSize) {
        this(initialSize, 0.75);
    }

    public MyHashMap(int initialSize, double loadFactor) {
        hashTable = new dataNode[initialSize];
        this.size = initialSize;
        this.loadFactor = loadFactor;
    }

    // Removes all the mapping from this map
    @Override
    public void clear() {
        if (size != 0) {
            hashTable = new dataNode[size];
            capacity = 0;
            hashSetKeys.clear();
        }
    }

    public int capacity() {
        return capacity;
    }

    // Returns true if this map contains a mapping for the specified key.
    @Override
    public boolean containsKey(K key) {
        return hashSetKeys.contains(key);
    }

    /*
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        if (this.containsKey(key)) {
            int tableIndex = (key.hashCode() & 0x7fffffff) % (size - 1);
            return get(hashTable[tableIndex], key);
        }
        else {
            // the hashtable does not contain the key
            return null;
        }
    }

    // Helper function for the get method to get the value of a specified key
    private V get(dataNode node, K key) {
        if (node == null) {
            return null;
        }
        else {
            if (node.getKey().equals(key)) {
                return (V) node.getValue();
            }
            else {
                return get(node.getNextNode(), key);
            }
        }
    }

    // Returns the number of key-value mappings in this map
    @Override
    public int size() {
        return this.size;
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key,
     * the old value is replaced.
     */
    @Override
    public void put(K key, V value) {

        if (((double) capacity / size) >= loadFactor) {
            copyAndIncreaseSize(size);
            this.put(key, value);
        }
        else {
            int tableIndex = (key.hashCode() & 0x7fffffff) % (size - 1);
            if (!hashSetKeys.contains(key)) {
                capacity += 1;
            }
            hashSetKeys.add(key);
            if (hashTable[tableIndex] == null) {
                hashTable[tableIndex] =
                    new dataNode<K, V>(key, value, key.hashCode());
            }
            else {
                dataNode<K, V> tempNode = hashTable[tableIndex];
                for (dataNode<K, V> node : tempNode) {
                    if (node.getKey().equals(key)) {
                        node.setValueData(value);
                        return;
                    }
                }
                hashTable[tableIndex] = new dataNode<K, V>(key, value,
                    key.hashCode(), hashTable[tableIndex]);
            }
        }
    }

    // Helper function to increase the size of the table
    private void copyAndIncreaseSize(int currentSize) {
        dataNode[] tempTable = hashTable; // temp table
        hashTable = new dataNode[currentSize * 2]; // new hashTable

        this.size = currentSize * 2;  // Updating the size

        // since the hashmap only allows unique keys hence iterating through
        // the keyset
        for (K key : this.keySet()) {
            int currentIndex =
                (key.hashCode() & 0x7fffffff) % (currentSize - 1);

            dataNode<K, V> tempNode = tempTable[currentIndex];

            // if there is no next node, it is only one node
            if (tempNode != null) {
                if (tempNode.getNextNode() == null) {
                    this.put(key, tempNode.getValue());
                } else {
                    for (dataNode node : tempNode) {
                        if (node.getKey().equals(key)) {
                            this.put(key, tempNode.getValue());
                        }
                    }
                }
            }
        }
    }

    /** Returns a Set view of the keys contained in this map. */
    @Override
    public Set<K> keySet() {
        return hashSetKeys;
    }

    /**
     * Removes the mapping for the specified key from this map if present.
     */
    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    /**
     * Removes the entry for the specified key only if it is currently mapped to
     * the specified value.
     */
    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<K> iterator() {
        return new HashMapIterator(hashSetKeys);
    }

    private class HashMapIterator implements Iterator<K> {
        K[] keyArray;
        int keySetSize;
        int counter = 0;

        HashMapIterator(Set hashKeySet) {
            keyArray = (K[]) hashKeySet.toArray();
            keySetSize = hashKeySet.size();
        }

        @Override
        public boolean hasNext() {
            return keySetSize > 0;
        }

        @Override
        public K next() {
            counter += 1;
            size -= 1;
            return keyArray[counter];
        }
    }
}

dataNode.java

import java.util.Iterator;

public class dataNode<K, V> implements Iterable<dataNode>{

    private int hash;
    private dataNode next;
    private K keyData;
    private V valueData;

    // Constructor for nodes which will store the data
    dataNode(K key, V value, int hash) {
        this.keyData = key;
        this.valueData = value;
        this.hash = hash;
        this.next = null;
    }

    dataNode(K key, V value, int hash, dataNode next) {
        this.keyData = key;
        this.valueData = value;
        this.hash = hash;
        this.next = next;
    }

    // Function to assign the next node
    public void nextNode(dataNode next) {
        this.next = next;
    }

    dataNode getNextNode() {
        return this.next;
    }

    K getKey() {
        return this.keyData;
    }

    V getValue() {
        return this.valueData;
    }

    void setValueData(V valueData) {
        this.valueData = valueData;
    }

    @Override
    public Iterator<dataNode> iterator() {
        return new dataNodeIterator(this);
    }

    private static class dataNodeIterator implements Iterator<dataNode> {
        private dataNode current;

        dataNodeIterator(dataNode node) {
            current = node;
        }

        public boolean hasNext() {
            return current.getNextNode() != null;
        }

        public dataNode next() {
            dataNode nextNode = current.getNextNode();
            current = nextNode;
            return nextNode;
        }
    }
}

Thanks

\$\endgroup\$
  • 2
    \$\begingroup\$ What is SampleMap? \$\endgroup\$ – Carcigenicate Aug 25 at 0:50
  • \$\begingroup\$ It is an interface that I created that defines the abstract data type. Would you like me to post the code of that too? \$\endgroup\$ – Rahul Wadhwani Aug 25 at 12:51

Your Answer

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

Browse other questions tagged or ask your own question.