Skip to content

Commit ffd0250

Browse files
divya-raichuradivya-raichura
authored
Add generic hashmaps (TheAlgorithms#3195)
1 parent 1a9937c commit ffd0250

File tree

4 files changed

+335
-0
lines changed

4 files changed

+335
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArray.java

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
import java.util.LinkedList;
4+
5+
// implementation of generic hashmaps using array of Linked Lists
6+
7+
public class GenericHashMapUsingArray<K, V> {
8+
private int size; // n (total number of key-value pairs)
9+
private LinkedList<Node>[] buckets; // N = buckets.length
10+
private float lf = 0.75f;
11+
12+
public GenericHashMapUsingArray() {
13+
initBuckets(16);
14+
size = 0;
15+
}
16+
// load factor = 0.75 means if we need to add 100 items and we have added
17+
// 75, then adding 76th item it will double the size, copy all elements
18+
// & then add 76th item.
19+
20+
private void initBuckets(int N) {
21+
buckets = new LinkedList[N];
22+
for (int i = 0; i < buckets.length; i++) {
23+
buckets[i] = new LinkedList<>();
24+
}
25+
}
26+
27+
public void put(K key, V value) {
28+
int bucketIndex = hashFunction(key);
29+
LinkedList<Node> nodes = buckets[bucketIndex];
30+
for (Node node : nodes) { // if key present => update
31+
if (node.key.equals(key)) {
32+
node.value = value;
33+
return;
34+
}
35+
}
36+
37+
// key is not present => insert
38+
nodes.add(new Node(key, value));
39+
size++;
40+
41+
if ((float) size / buckets.length > lf) {
42+
reHash();
43+
}
44+
}
45+
46+
// tells which bucket to go to
47+
private int hashFunction(K key) {
48+
int hc = key.hashCode();
49+
return Math.abs(hc) % buckets.length;
50+
}
51+
52+
private void reHash() {
53+
System.out.println("Rehashing!");
54+
LinkedList<Node>[] old = buckets;
55+
initBuckets(old.length * 2);
56+
this.size = 0;
57+
58+
for (LinkedList<Node> nodes : old) {
59+
for (Node node : nodes) {
60+
put(node.key, node.value);
61+
}
62+
}
63+
}
64+
65+
public void remove(K key) {
66+
int bucketIndex = hashFunction(key);
67+
LinkedList<Node> nodes = buckets[bucketIndex];
68+
69+
Node target = null;
70+
for (Node node : nodes) {
71+
if (node.key.equals(key)) {
72+
target = node;
73+
break;
74+
}
75+
}
76+
nodes.remove(target);
77+
size--;
78+
}
79+
80+
public int size() {
81+
return this.size;
82+
}
83+
84+
public V get(K key) {
85+
int bucketIndex = hashFunction(key);
86+
LinkedList<Node> nodes = buckets[bucketIndex];
87+
for (Node node : nodes) {
88+
if (node.key.equals(key)) {
89+
return node.value;
90+
}
91+
}
92+
return null;
93+
}
94+
95+
@Override
96+
public String toString() {
97+
StringBuilder builder = new StringBuilder();
98+
99+
builder.append("{");
100+
for (LinkedList<Node> nodes : buckets) {
101+
for (Node node : nodes) {
102+
builder.append(node.key);
103+
builder.append(" : ");
104+
builder.append(node.value);
105+
builder.append(", ");
106+
}
107+
}
108+
builder.append("}");
109+
return builder.toString();
110+
}
111+
112+
public boolean containsKey(K key) {
113+
return get(key) != null;
114+
}
115+
116+
public class Node {
117+
K key;
118+
V value;
119+
120+
public Node(K key, V value) {
121+
this.key = key;
122+
this.value = value;
123+
}
124+
}
125+
}

‎src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayList.java

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
6+
public class GenericHashMapUsingArrayList<K, V> {
7+
ArrayList<LinkedList<Node>> buckets;
8+
private float lf = 0.5f;
9+
private int size;
10+
11+
public GenericHashMapUsingArrayList() {
12+
buckets = new ArrayList<>();
13+
for (int i = 0; i < 10; i++) {
14+
buckets.add(new LinkedList<>());
15+
}
16+
size = 0;
17+
}
18+
19+
public void put(K key, V value) {
20+
int hash = Math.abs(key.hashCode() % buckets.size());
21+
LinkedList<Node> nodes = buckets.get(hash);
22+
23+
for (Node node : nodes) {
24+
if (node.key.equals(key)) {
25+
node.val = value;
26+
return;
27+
}
28+
}
29+
30+
nodes.add(new Node(key, value));
31+
size++;
32+
33+
if ((float) size / buckets.size() > lf) {
34+
reHash();
35+
}
36+
}
37+
38+
private void reHash() {
39+
ArrayList<LinkedList<Node>> old = buckets;
40+
buckets = new ArrayList<>();
41+
size = 0;
42+
for (int i = 0; i < old.size() * 2; i++) {
43+
buckets.add(new LinkedList<>());
44+
}
45+
for (LinkedList<Node> nodes : buckets) {
46+
for (Node node : nodes) {
47+
put(node.key, node.val);
48+
}
49+
}
50+
}
51+
52+
public V get(K key) {
53+
int hash = Math.abs(key.hashCode() % buckets.size());
54+
LinkedList<Node> nodes = buckets.get(hash);
55+
for (Node node : nodes) {
56+
if (node.key.equals(key)) {
57+
return node.val;
58+
}
59+
}
60+
return null;
61+
}
62+
63+
public void remove(K key) {
64+
int hash = Math.abs(key.hashCode() % buckets.size());
65+
LinkedList<Node> nodes = buckets.get(hash);
66+
67+
Node target = null;
68+
for (Node node : nodes) {
69+
if (node.key.equals(key)) {
70+
target = node;
71+
break;
72+
}
73+
}
74+
nodes.remove(target);
75+
size--;
76+
}
77+
78+
public boolean containsKey(K key) {
79+
return get(key) != null;
80+
}
81+
82+
public int size() {
83+
return this.size;
84+
}
85+
86+
@Override
87+
public String toString() {
88+
StringBuilder builder = new StringBuilder();
89+
builder.append("{");
90+
for (LinkedList<Node> nodes : buckets) {
91+
for (Node node : nodes) {
92+
builder.append(node.key);
93+
builder.append(" : ");
94+
builder.append(node.val);
95+
builder.append(", ");
96+
}
97+
}
98+
builder.append("}");
99+
return builder.toString();
100+
}
101+
102+
private class Node {
103+
K key;
104+
V val;
105+
106+
public Node(K key, V val) {
107+
this.key = key;
108+
this.val = val;
109+
}
110+
}
111+
112+
}

‎src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayListTest.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.junit.jupiter.api.Assertions.*;
6+
7+
class GenericHashMapUsingArrayListTest {
8+
@Test
9+
void testGenericHashmapWhichUsesArrayAndBothKeyAndValueAreStrings() {
10+
GenericHashMapUsingArrayList<String, String> map = new GenericHashMapUsingArrayList<>();
11+
map.put("USA", "Washington DC");
12+
map.put("Nepal", "Kathmandu");
13+
map.put("India", "New Delhi");
14+
map.put("Australia", "Sydney");
15+
assertNotNull(map);
16+
assertEquals(4, map.size());
17+
assertEquals("Kathmandu", map.get("Nepal"));
18+
assertEquals("Sydney", map.get("Australia"));
19+
}
20+
21+
@Test
22+
void testGenericHashmapWhichUsesArrayAndKeyIsStringValueIsInteger() {
23+
GenericHashMapUsingArrayList<String, Integer> map = new GenericHashMapUsingArrayList<>();
24+
map.put("USA", 87);
25+
map.put("Nepal", 25);
26+
map.put("India", 101);
27+
map.put("Australia", 99);
28+
assertNotNull(map);
29+
assertEquals(4, map.size());
30+
assertEquals(25, map.get("Nepal"));
31+
assertEquals(99, map.get("Australia"));
32+
map.remove("Nepal");
33+
assertFalse(map.containsKey("Nepal"));
34+
}
35+
36+
@Test
37+
void testGenericHashmapWhichUsesArrayAndKeyIsIntegerValueIsString() {
38+
GenericHashMapUsingArrayList<Integer, String> map = new GenericHashMapUsingArrayList<>();
39+
map.put(101, "Washington DC");
40+
map.put(34, "Kathmandu");
41+
map.put(46, "New Delhi");
42+
map.put(89, "Sydney");
43+
assertNotNull(map);
44+
assertEquals(4, map.size());
45+
assertEquals("Sydney", map.get(89));
46+
assertEquals("Washington DC", map.get(101));
47+
assertTrue(map.containsKey(46));
48+
}
49+
}

‎src/test/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayTest.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.junit.jupiter.api.Assertions.*;
6+
7+
class GenericHashMapUsingArrayTest {
8+
@Test
9+
void testGenericHashmapWhichUsesArrayAndBothKeyAndValueAreStrings() {
10+
GenericHashMapUsingArray<String, String> map = new GenericHashMapUsingArray<>();
11+
map.put("USA", "Washington DC");
12+
map.put("Nepal", "Kathmandu");
13+
map.put("India", "New Delhi");
14+
map.put("Australia", "Sydney");
15+
assertNotNull(map);
16+
assertEquals(4, map.size());
17+
assertEquals("Kathmandu", map.get("Nepal"));
18+
assertEquals("Sydney", map.get("Australia"));
19+
}
20+
21+
@Test
22+
void testGenericHashmapWhichUsesArrayAndKeyIsStringValueIsInteger() {
23+
GenericHashMapUsingArray<String, Integer> map = new GenericHashMapUsingArray<>();
24+
map.put("USA", 87);
25+
map.put("Nepal", 25);
26+
map.put("India", 101);
27+
map.put("Australia", 99);
28+
assertNotNull(map);
29+
assertEquals(4, map.size());
30+
assertEquals(25, map.get("Nepal"));
31+
assertEquals(99, map.get("Australia"));
32+
map.remove("Nepal");
33+
assertFalse(map.containsKey("Nepal"));
34+
}
35+
36+
@Test
37+
void testGenericHashmapWhichUsesArrayAndKeyIsIntegerValueIsString() {
38+
GenericHashMapUsingArray<Integer, String> map = new GenericHashMapUsingArray<>();
39+
map.put(101, "Washington DC");
40+
map.put(34, "Kathmandu");
41+
map.put(46, "New Delhi");
42+
map.put(89, "Sydney");
43+
assertNotNull(map);
44+
assertEquals(4, map.size());
45+
assertEquals("Sydney", map.get(89));
46+
assertEquals("Washington DC", map.get(101));
47+
assertTrue(map.containsKey(46));
48+
}
49+
}

0 commit comments

Comments
 (0)