EN
Java - custom implementation of hash map, own string with equals and hash code (HashMap)
12 points
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:
xxxxxxxxxx1
public boolean customEquals(SimpleString str)2
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.
xxxxxxxxxx1
package com.dirask;2
3
import java.util.Arrays;4
5
public class SimpleHashMap {6
7
// simple usage example:8
public static void main(String[] args) {9
SimpleHashMap map = new SimpleHashMap(3);10
11
map.put(new SimpleString("a"), new User(1, "A", 10));12
map.put(new SimpleString("b"), new User(2, "B", 20));13
map.put(new SimpleString("c"), new User(3, "C", 30));14
map.put(new SimpleString("d"), new User(4, "D", 40));15
map.put(new SimpleString("e"), new User(5, "E", 50));16
17
System.out.println(map.size()); // 518
19
User userA = map.get(new SimpleString("a"));20
System.out.println(userA); // User{id=1, name=A, score=10}21
22
User userC = map.get(new SimpleString("c"));23
System.out.println(userC); // User{id=3, name=C, score=30}24
25
map.remove(new SimpleString("c"));26
System.out.println(map.size()); // 427
28
boolean containsKey = map.containsKey(new SimpleString("d"));29
System.out.println(containsKey); // true30
}31
32
private int size;33
private int tableSize;34
private SimpleLinkedList<Entry>[] table;35
36
public SimpleHashMap(int tabSize) {37
tableSize = tabSize;38
size = 0;39
table = new SimpleLinkedList[tableSize];40
for (int i = 0; i < tableSize; i++) {41
table[i] = new SimpleLinkedList<>();42
}43
}44
45
public void put(SimpleString key, User value) {46
User old = get(key);47
if (old != null) {48
old.overrideUser(value); // override value49
} else {50
int hash = getHashCode(key);51
Entry entry = new Entry(key, value, hash);52
table[hash].addLast(entry);53
size++;54
}55
}56
57
public User get(SimpleString key) {58
int hashCode = getHashCode(key);59
SimpleLinkedList<Entry> list = table[hashCode];60
if (list.size > 0) {61
ListNode<Entry> curr = list.first;62
while (curr != null) {63
if (curr.item.key.customEquals(key)) {64
return curr.item.value;65
}66
curr = curr.next;67
}68
}69
return null;70
}71
72
// logic similar to get method73
public User remove(SimpleString key) {74
int hashCode = getHashCode(key);75
SimpleLinkedList<Entry> list = table[hashCode];76
77
if (list.size > 0) {78
ListNode<Entry> curr = list.first;79
while (curr != null) {80
if (curr.item.key.customEquals(key)) {81
User value = curr.item.value;82
list.unlink(curr);83
size--;84
return value;85
}86
curr = curr.next;87
}88
}89
return null;90
}91
92
public boolean containsKey(SimpleString key) {93
return get(key) != null;94
}95
96
public int size() {97
return size;98
}99
100
private int getHashCode(SimpleString key) {101
int hashCode = key.customHashCode();102
if (hashCode < 0) {103
hashCode *= -1;104
}105
return hashCode % tableSize;106
}107
108
private class Entry {109
SimpleString key;110
User value;111
int hashcode;112
113
public Entry(SimpleString key, User value, int hashcode) {114
this.key = key;115
this.value = value;116
this.hashcode = hashcode;117
}118
119
120
public String toString() {121
return "{" +122
"key=" + key +123
", hash=" + hashcode +124
", valId=" + value.getId() +125
'}';126
}127
}128
129
130
public String toString() {131
int[] distribution = new int[table.length];132
133
for (int i = 0; i < table.length; i++) {134
System.out.print("level " + i + ": ");135
136
SimpleLinkedList<Entry> list = table[i];137
System.out.println(list.toString());138
distribution[i] = list.size;139
}140
141
System.out.println("distribution: " + Arrays.toString(distribution));142
143
return "SimpleHashMap{" +144
"size=" + size +145
", tableSize=" + tableSize +146
'}';147
}148
149
public void printBucketDistribution() {150
int[] distribution = new int[table.length];151
152
for (int i = 0; i < table.length; i++) {153
SimpleLinkedList<Entry> list = table[i];154
distribution[i] = list.size;155
}156
157
String msg = "Bucket distribution: ";158
System.out.println(msg);159
System.out.println(Arrays.toString(distribution));160
}161
}162
163
class ListNode<E> {164
ListNode<E> prev;165
E item;166
ListNode<E> next;167
168
public ListNode(ListNode<E> prev, E item, ListNode<E> next) {169
this.prev = prev;170
this.item = item;171
this.next = next;172
}173
174
public String printForward() {175
if (next != null) {176
String call = next.printForward();177
String result = item + " -> " + call;178
return result;179
} else {180
return String.valueOf(item);181
}182
}183
}184
185
class SimpleLinkedList<E> {186
ListNode<E> first;187
ListNode<E> last;188
int size;189
190
public SimpleLinkedList() {191
192
}193
194
public int size() {195
return size;196
}197
198
public ListNode<E> addLast(E e) {199
ListNode<E> tmp = last;200
ListNode<E> newNode = new ListNode<>(tmp, e, null);201
last = newNode;202
if (tmp == null) {203
first = newNode;204
} else {205
tmp.next = newNode;206
}207
size++;208
return newNode;209
}210
211
public E unlink(ListNode<E> unlink) {212
E item = unlink.item;213
ListNode<E> prev = unlink.prev;214
ListNode<E> next = unlink.next;215
216
if (prev == null) {217
first = next;218
} else {219
prev.next = next;220
unlink.prev = null;221
}222
223
if (next == null) {224
last = prev;225
} else {226
next.prev = prev;227
unlink.next = null;228
}229
230
unlink.item = null;231
size--;232
return item;233
}234
235
236
public String toString() {237
if (first != null) {238
return "" + first.printForward();239
}240
return "empty";241
}242
}243
244
class SimpleString {245
private final char[] array;246
247
public SimpleString(char[] array) {248
this.array = array;249
}250
251
public SimpleString(String array) {252
this.array = array.toCharArray();253
}254
255
public char[] getArray() {256
return array;257
}258
259
public boolean customEquals(SimpleString str) {260
char[] a1 = array;261
char[] a2 = str.getArray();262
263
if (a1 == a2)264
return true;265
if (a1 == null || a2 == null)266
return false;267
268
int length = a1.length;269
if (a2.length != length)270
return false;271
272
for (int i = 0; i < length; i++)273
if (a1[i] != a2[i])274
return false;275
276
return true;277
}278
279
public int customHashCode() {280
int hashCode = 1;281
for (char c : array) {282
hashCode = 31 * hashCode + c;283
//hashCode = (int) (193817219281L * hashCode + c);284
}285
return hashCode;286
}287
288
289
public String toString() {290
return new String(array);291
}292
}293
294
class User {295
private int id;296
private String name;297
private int score;298
299
public User(int id, String name, int score) {300
this.id = id;301
this.name = name;302
this.score = score;303
}304
305
public int getId() {306
return id;307
}308
309
public String getName() {310
return name;311
}312
313
public int getScore() {314
return score;315
}316
317
public void overrideUser(User user) {318
this.id = user.id;319
this.name = user.name;320
this.score = user.score;321
}322
323
324
public String toString() {325
return "User{" +326
"id=" + id +327
", name=" + name +328
", score=" + score +329
'}';330
}331
332
// equals and hashCode - used only for tests333
334
public boolean equals(Object o) {335
if (this == o) return true;336
if (o == null || getClass() != o.getClass()) return false;337
338
User user = (User) o;339
340
if (id != user.id) return false;341
if (score != user.score) return false;342
return name != null ? name.equals(user.name) : user.name == null;343
}344
345
346
public int hashCode() {347
int result = id;348
result = 31 * result + (name != null ? name.hashCode() : 0);349
result = 31 * result + score;350
return result;351
}352
}Output:
xxxxxxxxxx1
52
User{id=1, name=A, score=10}3
User{id=3, name=C, score=30}4
45
trueThis linked list is used internally via our simple hash map as buckets.
xxxxxxxxxx1
package com.dirask;2
3
import org.assertj.core.api.Assertions;4
import org.junit.Test;5
6
public class SimpleHashMapTests1 {7
8
9
public void runLinkedList() {10
SimpleLinkedList<SimpleString> list = new SimpleLinkedList<>();11
ListNode<SimpleString> aNode = list.addLast(new SimpleString("a"));12
ListNode<SimpleString> bNode = list.addLast(new SimpleString("b"));13
ListNode<SimpleString> cNode = list.addLast(new SimpleString("c"));14
15
System.out.println(list.toString());16
Assertions.assertThat(list.toString().equals("a -> b -> c")).isTrue();17
18
list.unlink(bNode);19
System.out.println(list.toString());20
Assertions.assertThat(list.toString().equals("a -> c")).isTrue();21
22
ListNode<SimpleString> dNode = list.addLast(new SimpleString("d"));23
System.out.println(list.toString());24
Assertions.assertThat(list.toString().equals("a -> c -> d")).isTrue();25
26
list.unlink(cNode);27
System.out.println(list.toString());28
Assertions.assertThat(list.toString().equals("a -> d")).isTrue();29
30
list.unlink(aNode);31
System.out.println(list.toString());32
Assertions.assertThat(list.toString().equals("d")).isTrue();33
34
list.unlink(dNode);35
System.out.println(list.toString());36
Assertions.assertThat(list.toString().equals("empty")).isTrue();37
}38
}Output:
xxxxxxxxxx1
a -> b -> c2
a -> c3
a -> c -> d4
a -> d5
d6
emptyxxxxxxxxxx1
package com.dirask;2
3
import org.assertj.core.api.Assertions;4
import org.junit.Test;5
6
7
public class SimpleHashMapTests2 {8
9
10
public void simpleHashMapTest() {11
SimpleHashMap map = new SimpleHashMap(3);12
13
map.put(new SimpleString("a"), new User(1, "A", 10));14
map.put(new SimpleString("b"), new User(2, "B", 20));15
map.put(new SimpleString("c"), new User(3, "C", 30));16
map.put(new SimpleString("d"), new User(4, "D", 40));17
map.put(new SimpleString("e"), new User(5, "E", 50));18
19
System.out.println(map.toString());20
Assertions.assertThat(map.size() == 5).isTrue();21
22
Assertions.assertThat(map.get(new SimpleString("c"))23
.equals(new User(3, "C", 30))).isTrue();24
Assertions.assertThat(map.get(new SimpleString("a"))25
.equals(new User(1, "A", 10))).isTrue();26
27
Assertions.assertThat(map.remove(new SimpleString("c"))28
.equals(new User(3, "C", 30))).isTrue();29
30
Assertions.assertThat(map.size() == 4).isTrue();31
32
Assertions.assertThat(map.remove(new SimpleString("e"))33
.equals(new User(5, "E", 50))).isTrue();34
35
Assertions.assertThat(map.size() == 3).isTrue();36
37
Assertions.assertThat(map.containsKey(new SimpleString("a"))).isTrue();38
Assertions.assertThat(map.containsKey(new SimpleString("b"))).isTrue();39
Assertions.assertThat(map.containsKey(new SimpleString("d"))).isTrue();40
41
System.out.println(map.toString());42
}43
}Output:
xxxxxxxxxx1
level 0: {key=b, hash=0, valId=2} -> {key=e, hash=0, valId=5}2
level 1: {key=c, hash=1, valId=3}3
level 2: {key=a, hash=2, valId=1} -> {key=d, hash=2, valId=4}4
distribution: [2, 1, 2]5
SimpleHashMap{size=5, tableSize=3}6
level 0: {key=b, hash=0, valId=2}7
level 1: empty8
level 2: {key=a, hash=2, valId=1} -> {key=d, hash=2, valId=4}9
distribution: [1, 0, 2]10
SimpleHashMap{size=3, tableSize=3}xxxxxxxxxx1
package com.dirask;2
3
import org.assertj.core.api.Assertions;4
import org.junit.Test;5
6
public class SimpleHashMapTests3 {7
8
9
public void simpleHashMapTest() {10
SimpleHashMap map = new SimpleHashMap(10);11
12
// put13
for (int i = 0; i < 26; i++) {14
// ascii: 97 - a, 98 - b, ...15
String asciiKey = String.valueOf((char) ('a' + i));16
// ascii: 65 - A, 66 - B, ...17
String ascii = "" + (char) ('A' + i);18
map.put(new SimpleString(asciiKey), new User(i, ascii, 10 + i));19
}20
21
Assertions.assertThat(map.size()).isEqualTo(26);22
System.out.println(map.toString());23
24
// get, contains25
for (int i = 0; i < 26; i++) {26
String asciiKey = String.valueOf((char) ('a' + i));27
String ascii = "" + (char) ('A' + i);28
29
User user = map.get(new SimpleString(asciiKey));30
31
Assertions.assertThat(user32
.equals(new User(i, ascii, 10 + i))).isTrue();33
34
boolean containsKey = map.containsKey(new SimpleString(asciiKey));35
Assertions.assertThat(containsKey).isTrue();36
}37
38
// remove39
for (int i = 0; i < 26; i++) {40
String asciiKey = String.valueOf((char) ('a' + i));41
String ascii = "" + (char) ('A' + i);42
43
User user = map.remove(new SimpleString(asciiKey));44
45
Assertions.assertThat(user46
.equals(new User(i, ascii, 10 + i))).isTrue();47
48
int expectedSize = 26 - i - 1;49
Assertions.assertThat(map.size()).isEqualTo(expectedSize);50
}51
52
Assertions.assertThat(map.size()).isEqualTo(0);53
}54
}Output:
xxxxxxxxxx1
level 0: {key=c, hash=0, valId=2} -> {key=m, hash=0, valId=12} -> {key=w, hash=0, valId=22}2
level 1: {key=d, hash=1, valId=3} -> {key=n, hash=1, valId=13} -> {key=x, hash=1, valId=23}3
level 2: {key=e, hash=2, valId=4} -> {key=o, hash=2, valId=14} -> {key=y, hash=2, valId=24}4
level 3: {key=f, hash=3, valId=5} -> {key=p, hash=3, valId=15} -> {key=z, hash=3, valId=25}5
level 4: {key=g, hash=4, valId=6} -> {key=q, hash=4, valId=16}6
level 5: {key=h, hash=5, valId=7} -> {key=r, hash=5, valId=17}7
level 6: {key=i, hash=6, valId=8} -> {key=s, hash=6, valId=18}8
level 7: {key=j, hash=7, valId=9} -> {key=t, hash=7, valId=19}9
level 8: {key=a, hash=8, valId=0} -> {key=k, hash=8, valId=10} -> {key=u, hash=8, valId=20}10
level 9: {key=b, hash=9, valId=1} -> {key=l, hash=9, valId=11} -> {key=v, hash=9, valId=21}11
distribution: [3, 3, 3, 3, 2, 2, 2, 2, 3, 3]12
SimpleHashMap{size=26, tableSize=10}xxxxxxxxxx1
package com.dirask;2
3
import org.assertj.core.api.Assertions;4
import org.junit.Test;5
6
import java.util.HashSet;7
import java.util.Set;8
import java.util.concurrent.ThreadLocalRandom;9
10
public class SimpleHashMapTests4 {11
12
13
public void simpleHashMapTest() {14
SimpleHashMap map = new SimpleHashMap(10);15
16
Set<String> inserts = new HashSet<>();17
18
for (int i = 0; i < 2600; i++) {19
String random = randomString(3);20
map.put(new SimpleString(random), new User(i, random, 10 + i));21
22
inserts.add(random);23
}24
25
System.out.println("size: " + map.size());26
System.out.println((2600 - map.size()) + " keys were duplicated " +27
"and we override the value for this key");28
29
for (String key : inserts) {30
boolean containsKey = map.containsKey(new SimpleString(key));31
Assertions.assertThat(containsKey).isTrue();32
}33
34
map.printBucketDistribution();35
}36
37
private static String randomString(int len) {38
String alphabet =39
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" +40
"abcdefghijklmnopqrstuvwxyz" +41
"0123456789";42
43
StringBuilder builder = new StringBuilder();44
45
for (int i = 0; i < len; i++) {46
int randIdx = ThreadLocalRandom.current().nextInt(alphabet.length());47
char randChar = alphabet.charAt(randIdx);48
builder.append(randChar);49
}50
51
return builder.toString();52
}53
}Output:
xxxxxxxxxx1
size: 25822
18 keys were duplicated and we override the value for this key3
Bucket distribution:4
[246, 288, 263, 227, 260, 258, 253, 232, 269, 286]