Java - custom implementation of hash map, own string with equals and hash code (HashMap)

In this hash map implementation we have SimpleString as key. SimpleString class was implemented only for purpose to explain how does hash map works internally.

SimpleString has own equals and hash code methods:

public boolean customEquals(SimpleString str)
public int customHashCode()

Those 2 methods were implemented to have user much better understanding of the entire concept of equals and hash code contract.

Hash Map is very important data structure in computer science. It depends on the programming language how do we call this data structure, very common synonyms are: hash map, hash table, dictionary, key value store, associative array.

Hash Map can be implemented in many different ways but the main functionality it should provide is very similar.

Simple hash map implementation

package com.dirask;

import java.util.Arrays;

public class SimpleHashMap {

    // simple usage example:
    public static void main(String[] args) {
        SimpleHashMap map = new SimpleHashMap(3);

        map.put(new SimpleString("a"), new User(1, "A", 10));
        map.put(new SimpleString("b"), new User(2, "B", 20));
        map.put(new SimpleString("c"), new User(3, "C", 30));
        map.put(new SimpleString("d"), new User(4, "D", 40));
        map.put(new SimpleString("e"), new User(5, "E", 50));

        System.out.println(map.size()); // 5

        User userA = map.get(new SimpleString("a"));
        System.out.println(userA); // User{id=1, name=A, score=10}

        User userC = map.get(new SimpleString("c"));
        System.out.println(userC); // User{id=3, name=C, score=30}

        map.remove(new SimpleString("c"));
        System.out.println(map.size()); // 4

        boolean containsKey = map.containsKey(new SimpleString("d"));
        System.out.println(containsKey); // true
    }

    private int size;
    private int tableSize;
    private SimpleLinkedList<Entry>[] table;

    public SimpleHashMap(int tabSize) {
        tableSize = tabSize;
        size = 0;
        table = new SimpleLinkedList[tableSize];
        for (int i = 0; i < tableSize; i++) {
            table[i] = new SimpleLinkedList<>();
        }
    }

    public void put(SimpleString key, User value) {
        User old = get(key);
        if (old != null) {
            old.overrideUser(value); // override value
        } else {
            int hash = getHashCode(key);
            Entry entry = new Entry(key, value, hash);
            table[hash].addLast(entry);
            size++;
        }
    }

    public User get(SimpleString key) {
        int hashCode = getHashCode(key);
        SimpleLinkedList<Entry> list = table[hashCode];
        if (list.size > 0) {
            ListNode<Entry> curr = list.first;
            while (curr != null) {
                if (curr.item.key.customEquals(key)) {
                    return curr.item.value;
                }
                curr = curr.next;
            }
        }
        return null;
    }

    // logic similar to get method
    public User remove(SimpleString key) {
        int hashCode = getHashCode(key);
        SimpleLinkedList<Entry> list = table[hashCode];

        if (list.size > 0) {
            ListNode<Entry> curr = list.first;
            while (curr != null) {
                if (curr.item.key.customEquals(key)) {
                    User value = curr.item.value;
                    list.unlink(curr);
                    size--;
                    return value;
                }
                curr = curr.next;
            }
        }
        return null;
    }

    public boolean containsKey(SimpleString key) {
        return get(key) != null;
    }

    public int size() {
        return size;
    }

    private int getHashCode(SimpleString key) {
        int hashCode = key.customHashCode();
        if (hashCode < 0) {
            hashCode *= -1;
        }
        return hashCode % tableSize;
    }

    private class Entry {
        SimpleString key;
        User value;
        int hashcode;

        public Entry(SimpleString key, User value, int hashcode) {
            this.key = key;
            this.value = value;
            this.hashcode = hashcode;
        }

        @Override
        public String toString() {
            return "{" +
                    "key=" + key +
                    ", hash=" + hashcode +
                    ", valId=" + value.getId() +
                    '}';
        }
    }

    @Override
    public String toString() {
        int[] distribution = new int[table.length];

        for (int i = 0; i < table.length; i++) {
            System.out.print("level " + i + ": ");

            SimpleLinkedList<Entry> list = table[i];
            System.out.println(list.toString());
            distribution[i] = list.size;
        }

        System.out.println("distribution: " + Arrays.toString(distribution));

        return "SimpleHashMap{" +
                "size=" + size +
                ", tableSize=" + tableSize +
                '}';
    }

    public void printBucketDistribution() {
        int[] distribution = new int[table.length];

        for (int i = 0; i < table.length; i++) {
            SimpleLinkedList<Entry> list = table[i];
            distribution[i] = list.size;
        }

        String msg = "Bucket distribution: ";
        System.out.println(msg);
        System.out.println(Arrays.toString(distribution));
    }
}

class ListNode<E> {
    ListNode<E> prev;
    E item;
    ListNode<E> next;

    public ListNode(ListNode<E> prev, E item, ListNode<E> next) {
        this.prev = prev;
        this.item = item;
        this.next = next;
    }

    public String printForward() {
        if (next != null) {
            String call = next.printForward();
            String result = item + " -> " + call;
            return result;
        } else {
            return String.valueOf(item);
        }
    }
}

class SimpleLinkedList<E> {
    ListNode<E> first;
    ListNode<E> last;
    int size;

    public SimpleLinkedList() {

    }

    public int size() {
        return size;
    }

    public ListNode<E> addLast(E e) {
        ListNode<E> tmp = last;
        ListNode<E> newNode = new ListNode<>(tmp, e, null);
        last = newNode;
        if (tmp == null) {
            first = newNode;
        } else {
            tmp.next = newNode;
        }
        size++;
        return newNode;
    }

    public E unlink(ListNode<E> unlink) {
        E item = unlink.item;
        ListNode<E> prev = unlink.prev;
        ListNode<E> next = unlink.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            unlink.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            unlink.next = null;
        }

        unlink.item = null;
        size--;
        return item;
    }

    @Override
    public String toString() {
        if (first != null) {
            return "" + first.printForward();
        }
        return "empty";
    }
}

class SimpleString {
    private final char[] array;

    public SimpleString(char[] array) {
        this.array = array;
    }

    public SimpleString(String array) {
        this.array = array.toCharArray();
    }

    public char[] getArray() {
        return array;
    }

    public boolean customEquals(SimpleString str) {
        char[] a1 = array;
        char[] a2 = str.getArray();

        if (a1 == a2)
            return true;
        if (a1 == null || a2 == null)
            return false;

        int length = a1.length;
        if (a2.length != length)
            return false;

        for (int i = 0; i < length; i++)
            if (a1[i] != a2[i])
                return false;

        return true;
    }

    public int customHashCode() {
        int hashCode = 1;
        for (char c : array) {
            hashCode = 31 * hashCode + c;
            //hashCode = (int) (193817219281L * hashCode + c);
        }
        return hashCode;
    }

    @Override
    public String toString() {
        return new String(array);
    }
}

class User {
    private int id;
    private String name;
    private int score;

    public User(int id, String name, int score) {
        this.id = id;
        this.name = name;
        this.score = score;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }

    public void overrideUser(User user) {
        this.id = user.id;
        this.name = user.name;
        this.score = user.score;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name=" + name +
                ", score=" + score +
                '}';
    }

    // equals and hashCode - used only for tests
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        User user = (User) o;

        if (id != user.id) return false;
        if (score != user.score) return false;
        return name != null ? name.equals(user.name) : user.name == null;
    }

    @Override
    public int hashCode() {
        int result = id;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        result = 31 * result + score;
        return result;
    }
}

Output:

5
User{id=1, name=A, score=10}
User{id=3, name=C, score=30}
4
true

Test 1 - testing linked list used to store buckets

This linked list is used internally via our simple hash map as buckets.

package com.dirask;

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class SimpleHashMapTests1 {

    @Test
    public void runLinkedList() {
        SimpleLinkedList<SimpleString> list = new SimpleLinkedList<>();
        ListNode<SimpleString> aNode = list.addLast(new SimpleString("a"));
        ListNode<SimpleString> bNode = list.addLast(new SimpleString("b"));
        ListNode<SimpleString> cNode = list.addLast(new SimpleString("c"));

        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("a -> b -> c")).isTrue();

        list.unlink(bNode);
        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("a -> c")).isTrue();

        ListNode<SimpleString> dNode = list.addLast(new SimpleString("d"));
        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("a -> c -> d")).isTrue();

        list.unlink(cNode);
        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("a -> d")).isTrue();

        list.unlink(aNode);
        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("d")).isTrue();

        list.unlink(dNode);
        System.out.println(list.toString());
        Assertions.assertThat(list.toString().equals("empty")).isTrue();
    }
}

Output:

a -> b -> c
a -> c
a -> c -> d
a -> d
d
empty

Test 2 - put, get, remove, containsKey methods

package com.dirask;

import org.assertj.core.api.Assertions;
import org.junit.Test;


public class SimpleHashMapTests2 {

    @Test
    public void simpleHashMapTest() {
        SimpleHashMap map = new SimpleHashMap(3);

        map.put(new SimpleString("a"), new User(1, "A", 10));
        map.put(new SimpleString("b"), new User(2, "B", 20));
        map.put(new SimpleString("c"), new User(3, "C", 30));
        map.put(new SimpleString("d"), new User(4, "D", 40));
        map.put(new SimpleString("e"), new User(5, "E", 50));

        System.out.println(map.toString());
        Assertions.assertThat(map.size() == 5).isTrue();

        Assertions.assertThat(map.get(new SimpleString("c"))
                .equals(new User(3, "C", 30))).isTrue();
        Assertions.assertThat(map.get(new SimpleString("a"))
                .equals(new User(1, "A", 10))).isTrue();

        Assertions.assertThat(map.remove(new SimpleString("c"))
                .equals(new User(3, "C", 30))).isTrue();

        Assertions.assertThat(map.size() == 4).isTrue();

        Assertions.assertThat(map.remove(new SimpleString("e"))
                .equals(new User(5, "E", 50))).isTrue();

        Assertions.assertThat(map.size() == 3).isTrue();

        Assertions.assertThat(map.containsKey(new SimpleString("a"))).isTrue();
        Assertions.assertThat(map.containsKey(new SimpleString("b"))).isTrue();
        Assertions.assertThat(map.containsKey(new SimpleString("d"))).isTrue();

        System.out.println(map.toString());
    }
}

Output:

level 0: {key=b, hash=0, valId=2} -> {key=e, hash=0, valId=5}
level 1: {key=c, hash=1, valId=3}
level 2: {key=a, hash=2, valId=1} -> {key=d, hash=2, valId=4}
distribution: [2, 1, 2]
SimpleHashMap{size=5, tableSize=3}
level 0: {key=b, hash=0, valId=2}
level 1: empty
level 2: {key=a, hash=2, valId=1} -> {key=d, hash=2, valId=4}
distribution: [1, 0, 2]
SimpleHashMap{size=3, tableSize=3}

Test 3 - put, get, remove, containsKey methods - more data

package com.dirask;

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class SimpleHashMapTests3 {

    @Test
    public void simpleHashMapTest() {
        SimpleHashMap map = new SimpleHashMap(10);

        // put
        for (int i = 0; i < 26; i++) {
            // ascii: 97 - a, 98 - b, ...
            String asciiKey = String.valueOf((char) ('a' + i));
            // ascii: 65 - A, 66 - B, ...
            String ascii = "" + (char) ('A' + i);
            map.put(new SimpleString(asciiKey), new User(i, ascii, 10 + i));
        }

        Assertions.assertThat(map.size()).isEqualTo(26);
        System.out.println(map.toString());

        // get, contains
        for (int i = 0; i < 26; i++) {
            String asciiKey = String.valueOf((char) ('a' + i));
            String ascii = "" + (char) ('A' + i);

            User user = map.get(new SimpleString(asciiKey));

            Assertions.assertThat(user
                    .equals(new User(i, ascii, 10 + i))).isTrue();

            boolean containsKey = map.containsKey(new SimpleString(asciiKey));
            Assertions.assertThat(containsKey).isTrue();
        }

        // remove
        for (int i = 0; i < 26; i++) {
            String asciiKey = String.valueOf((char) ('a' + i));
            String ascii = "" + (char) ('A' + i);

            User user = map.remove(new SimpleString(asciiKey));

            Assertions.assertThat(user
                    .equals(new User(i, ascii, 10 + i))).isTrue();

            int expectedSize = 26 - i - 1;
            Assertions.assertThat(map.size()).isEqualTo(expectedSize);
        }

        Assertions.assertThat(map.size()).isEqualTo(0);
    }
}

Output:

level 0: {key=c, hash=0, valId=2} -> {key=m, hash=0, valId=12} -> {key=w, hash=0, valId=22}
level 1: {key=d, hash=1, valId=3} -> {key=n, hash=1, valId=13} -> {key=x, hash=1, valId=23}
level 2: {key=e, hash=2, valId=4} -> {key=o, hash=2, valId=14} -> {key=y, hash=2, valId=24}
level 3: {key=f, hash=3, valId=5} -> {key=p, hash=3, valId=15} -> {key=z, hash=3, valId=25}
level 4: {key=g, hash=4, valId=6} -> {key=q, hash=4, valId=16}
level 5: {key=h, hash=5, valId=7} -> {key=r, hash=5, valId=17}
level 6: {key=i, hash=6, valId=8} -> {key=s, hash=6, valId=18}
level 7: {key=j, hash=7, valId=9} -> {key=t, hash=7, valId=19}
level 8: {key=a, hash=8, valId=0} -> {key=k, hash=8, valId=10} -> {key=u, hash=8, valId=20}
level 9: {key=b, hash=9, valId=1} -> {key=l, hash=9, valId=11} -> {key=v, hash=9, valId=21}
distribution: [3, 3, 3, 3, 2, 2, 2, 2, 3, 3]
SimpleHashMap{size=26, tableSize=10}

Test 4 - 2600 inserts to hash map of size 10

package com.dirask;

import org.assertj.core.api.Assertions;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class SimpleHashMapTests4 {

    @Test
    public void simpleHashMapTest() {
        SimpleHashMap map = new SimpleHashMap(10);

        Set<String> inserts = new HashSet<>();

        for (int i = 0; i < 2600; i++) {
            String random = randomString(3);
            map.put(new SimpleString(random), new User(i, random, 10 + i));

            inserts.add(random);
        }

        System.out.println("size: " + map.size());
        System.out.println((2600 - map.size()) + " keys were duplicated " +
                "and we override the value for this key");

        for (String key : inserts) {
            boolean containsKey = map.containsKey(new SimpleString(key));
            Assertions.assertThat(containsKey).isTrue();
        }

        map.printBucketDistribution();
    }

    private static String randomString(int len) {
        String alphabet =
                "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
                "abcdefghijklmnopqrstuvwxyz" +
                "0123456789";

        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < len; i++) {
            int randIdx = ThreadLocalRandom.current().nextInt(alphabet.length());
            char randChar = alphabet.charAt(randIdx);
            builder.append(randChar);
        }

        return builder.toString();
    }
}

Output:

size: 2582
18 keys were duplicated and we override the value for this key
Bucket distribution:
[246, 288, 263, 227, 260, 258, 253, 232, 269, 286]

References

• Hash table - wiki
• Hash Tables - GNU documentation
• Overview of Hash Tables PDF - Into to Algorithms CS 6006 MIT
• Hashing with chaining PDF - by Erik Demaine - MIT
• Hashing with Chaining - youtube video - by Erik Demaine - MIT