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:
xxxxxxxxxx
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.
xxxxxxxxxx
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;
}
public String toString() {
return "{" +
"key=" + key +
", hash=" + hashcode +
", valId=" + value.getId() +
'}';
}
}
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;
}
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;
}
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;
}
public String toString() {
return "User{" +
"id=" + id +
", name=" + name +
", score=" + score +
'}';
}
// equals and hashCode - used only for tests
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;
}
public int hashCode() {
int result = id;
result = 31 * result + (name != null ? name.hashCode() : 0);
result = 31 * result + score;
return result;
}
}
Output:
xxxxxxxxxx
5
User{id=1, name=A, score=10}
User{id=3, name=C, score=30}
4
true
This linked list is used internally via our simple hash map as buckets.
xxxxxxxxxx
package com.dirask;
import org.assertj.core.api.Assertions;
import org.junit.Test;
public class SimpleHashMapTests1 {
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:
xxxxxxxxxx
a -> b -> c
a -> c
a -> c -> d
a -> d
d
empty
xxxxxxxxxx
package com.dirask;
import org.assertj.core.api.Assertions;
import org.junit.Test;
public class SimpleHashMapTests2 {
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:
xxxxxxxxxx
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}
xxxxxxxxxx
package com.dirask;
import org.assertj.core.api.Assertions;
import org.junit.Test;
public class SimpleHashMapTests3 {
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:
xxxxxxxxxx
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}
xxxxxxxxxx
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 {
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:
xxxxxxxxxx
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]