How to Create Own HashMap in Java?

Question

I know about hashing algorithm and hashCode() to convert "key" into an equivalent integer (using some mathematically random expression) that is then compressed and stored into buckets.

But can someone point me to an implementation or at least data structure that should be used as baseline?

I haven't found it anywhere on the web.

Answer 1

Even though it's a really old question, I thought I should provide an easy-to-understand answer for a beginner.

Custom implementation of a HashMap simple solution:

   class HashMapCustom<K, V> {

    private Entry<K, V>[] table;   //Array of Entry.
    private int capacity = 4;  //Initial capacity of HashMap

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

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


    @SuppressWarnings("unchecked")
    public HashMapCustom() {
        table = new Entry[capacity];
    }


    /**
     * Method allows you put key-value pair in HashMapCustom.
     * If the map already contains a mapping for the key, the old value is replaced.
     * Note: method does not allows you to put null key though it allows null values.
     * Implementation allows you to put custom objects as a key as well.
     * Key Features: implementation provides you with following features:-
     * >provide complete functionality how to override equals method.
     * >provide complete functionality how to override hashCode method.
     *
     * @param newKey
     * @param data
     */
    public void put(K newKey, V data) {
        if (newKey == null)
            return;    //does not allow to store null.

        //calculate hash of key.
        int hash = hash(newKey);
        //create new entry.
        Entry<K, V> newEntry = new Entry<K, V>(newKey, data, null);

        //if table location does not contain any entry, store entry there.
        if (table[hash] == null) {
            table[hash] = newEntry;
        } else {
            Entry<K, V> previous = null;
            Entry<K, V> current = table[hash];

            while (current != null) { //we have reached last entry of bucket.
                if (current.key.equals(newKey)) {
                    if (previous == null) {  //node has to be insert on first of bucket.
                        newEntry.next = current.next;
                        table[hash] = newEntry;
                        return;
                    } else {
                        newEntry.next = current.next;
                        previous.next = newEntry;
                        return;
                    }
                }
                previous = current;
                current = current.next;
            }
            previous.next = newEntry;
        }
    }

    /**
     * Method returns value corresponding to key.
     *
     * @param key
     */
    public V get(K key) {
        int hash = hash(key);
        if (table[hash] == null) {
            return null;
        } else {
            Entry<K, V> temp = table[hash];
            while (temp != null) {
                if (temp.key.equals(key))
                    return temp.value;
                temp = temp.next; //return value corresponding to key.
            }
            return null;   //returns null if key is not found.
        }
    }


    /**
     * Method removes key-value pair from HashMapCustom.
     *
     * @param key
     */
    public boolean remove(K deleteKey) {

        int hash = hash(deleteKey);

        if (table[hash] == null) {
            return false;
        } else {
            Entry<K, V> previous = null;
            Entry<K, V> current = table[hash];

            while (current != null) { //we have reached last entry node of bucket.
                if (current.key.equals(deleteKey)) {
                    if (previous == null) {  //delete first entry node.
                        table[hash] = table[hash].next;
                        return true;
                    } else {
                        previous.next = current.next;
                        return true;
                    }
                }
                previous = current;
                current = current.next;
            }
            return false;
        }

    }


    /**
     * Method displays all key-value pairs present in HashMapCustom.,
     * insertion order is not guaranteed, for maintaining insertion order
     * refer LinkedHashMapCustom.
     *
     * @param key
     */
    public void display() {

        for (int i = 0; i < capacity; i++) {
            if (table[i] != null) {
                Entry<K, V> entry = table[i];
                while (entry != null) {
                    System.out.print("{" + entry.key + "=" + entry.value + "}" + " ");
                    entry = entry.next;
                }
            }
        }

    }

    /**
     * Method implements hashing functionality, which helps in finding the appropriate
     * bucket location to store our data.
     * This is very important method, as performance of HashMapCustom is very much
     * dependent on  this method's implementation.
     *
     * @param key
     */
    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }
}

Answer 2

If you want a fast and memory efficient implementation you are going to want to use an array to back your map. Use the hashing algorithms that you want to index into the array and store the object in that slot of the array.

There are a lot of little details that you will want to pay attention to. When to resize the array, how to detect and resolve a hash collision, etc.

I'd recommend making your class implement java.util.Map as it will give you a good idea of what methods will be necessary and useful.

Answer 3

Just use eclipse and use latest JDK. Source code of Java core packages come attached with the JDK. Open HashMap class and you are good to go. Some of the method implementations may come from AbstractMap, AbstractCollection etc. This is because of proper OO design. You can navigate to all the classes of JDK in your eclipse.

UPDATE: Why Eclipe ( or an IDE) instead of just opening the zip file? An IDE can be used to move back and forth between classes and in general is good for "reading" code. Note not all method implementations are in one file like HashMap.java and so simple text editors like notepad++, or textpad may not be enough. A full blown IDE like eclipse/IDEA can make it much easier. Atleast it worked for me :)

Answer 4

Create a class that implements the java.util.Map interface and fill in the given methods