Skip to content

Commit f1ecbf8

Browse files
KAispreadKAispread
committed
HashMap 직접 구현
1 parent 820134e commit f1ecbf8

1 file changed

Lines changed: 233 additions & 0 deletions

File tree

‎src/data_structure/HashMap.java‎

Lines changed: 233 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,233 @@
1+
package data_structure;
2+
3+
import java.util.Arrays;
4+
5+
public class HashMap<K, V> {
6+
7+
private static final int CAPACITY = 10;
8+
private static final float LOAD_FACTOR = 0.75f;
9+
10+
private Node<K, V>[] hashBucket;
11+
private int currentCapacity;
12+
private int currentSize;
13+
14+
public HashMap() {
15+
this.hashBucket = new Node[CAPACITY];
16+
this.currentSize = 0;
17+
this.currentCapacity = CAPACITY;
18+
}
19+
20+
public void put(K key, V value) {
21+
Node<K, V> node = Node.of(key, value);
22+
int index = getIndex(key);
23+
24+
addNodeToBucket(index, node);
25+
}
26+
27+
public void delete(K key) {
28+
int index = getIndex(key);
29+
30+
Node<K, V> node = findNodeFromKey(index, key);
31+
32+
if (node != null) {
33+
Node<K, V> nextNode = node.getNextNode();
34+
Node<K, V> prevNode = node.getPrevNode();
35+
36+
if (prevNode != null) {
37+
prevNode.setNextNode(nextNode);
38+
}
39+
if (nextNode != null) {
40+
nextNode.setPrevNode(prevNode);
41+
}
42+
43+
if (hashBucket[index] == node) {
44+
hashBucket[index] = nextNode;
45+
46+
if (nextNode == null) {
47+
currentSize--;
48+
}
49+
}
50+
}
51+
}
52+
53+
public V get(K key) {
54+
int index = getIndex(key);
55+
Node<K, V> node = findNodeFromKey(index, key);
56+
57+
if (node == null) {
58+
return null;
59+
}
60+
61+
return node.getValue();
62+
}
63+
64+
private Node<K, V> findNodeFromKey(int index, K key) {
65+
Node<K, V> node = hashBucket[index];
66+
if (node == null) {
67+
return node;
68+
}
69+
while (node != null && !node.getKey().equals(key)) {
70+
node = node.getNextNode();
71+
}
72+
return node;
73+
}
74+
75+
private void addNodeToBucket(int index, Node<K, V> node) {
76+
if (hashBucket[index] == null) {
77+
hashBucket[index] = node;
78+
currentSize++;
79+
80+
double loadFactor = (double) currentSize / currentCapacity;
81+
if (loadFactor > LOAD_FACTOR) {
82+
rearrangeHashBucket(currentCapacity * 2);
83+
}
84+
return;
85+
}
86+
87+
Node<K, V> currentNode = hashBucket[index];
88+
if (currentNode.getKey().equals(node.getKey())) {
89+
currentNode.updateValue(node.getValue());
90+
return;
91+
}
92+
93+
while (currentNode.hasNext()) {
94+
currentNode = currentNode.getNextNode();
95+
96+
if (currentNode.getKey().equals(node.getKey())) {
97+
currentNode.updateValue(node.getValue());
98+
return;
99+
}
100+
}
101+
102+
currentNode.setNextNode(node);
103+
node.setPrevNode(currentNode);
104+
}
105+
106+
private void rearrangeHashBucket(int capacity) {
107+
System.out.println("rearranged hashBucket to : " + capacity);
108+
Node<K, V>[] beforeHashBucket = Arrays.copyOf(hashBucket, hashBucket.length);
109+
110+
this.hashBucket = new Node[capacity];
111+
this.currentCapacity = capacity;
112+
this.currentSize = 0;
113+
114+
for (Node<K, V> beforeNode : beforeHashBucket) {
115+
if (beforeNode == null) {
116+
continue;
117+
}
118+
119+
Node<K, V> current = beforeNode;
120+
do {
121+
K key = current.getKey();
122+
int index = getIndex(key);
123+
124+
addNodeToBucket(index, beforeNode);
125+
} while ((current = current.getNextNode()) != null);
126+
}
127+
}
128+
129+
private int getIndex(K key) {
130+
return key.hashCode() % currentCapacity;
131+
}
132+
133+
/*
134+
* for test
135+
* */
136+
public void print() {
137+
System.out.println("---- info ----");
138+
System.out.println("bucket length : " + hashBucket.length);
139+
System.out.println("capacity : " + currentCapacity);
140+
System.out.println("size : " + currentSize);
141+
System.out.println();
142+
143+
System.out.println("---- data ----");
144+
for (int i = 0; i < hashBucket.length; i++) {
145+
Node<K, V> kvNode = hashBucket[i];
146+
while (kvNode != null) {
147+
System.out.println("index = %s / Key = %s / Value = %s".formatted(i, kvNode.getKey(), kvNode.getValue()));
148+
kvNode = kvNode.getNextNode();
149+
}
150+
}
151+
}
152+
153+
static class Node<K, V> {
154+
155+
private Node<K, V> nextNode;
156+
private Node<K, V> prevNode;
157+
158+
private K key;
159+
private V value;
160+
161+
public Node(K key, V value) {
162+
this.key = key;
163+
this.value = value;
164+
}
165+
166+
public static <K, V> Node<K, V> of(K key, V value) {
167+
return new Node<>(key, value);
168+
}
169+
170+
public void updateValue(V value) {
171+
this.value = value;
172+
}
173+
174+
public void setNextNode(Node<K, V> nextNode) {
175+
this.nextNode = nextNode;
176+
}
177+
178+
public void setPrevNode(Node<K, V> prevNode) {
179+
this.prevNode = prevNode;
180+
}
181+
182+
public boolean hasNext() {
183+
return nextNode != null;
184+
}
185+
186+
public Node<K, V> getNextNode() {
187+
return nextNode;
188+
}
189+
190+
public Node<K, V> getPrevNode() {
191+
return prevNode;
192+
}
193+
194+
public K getKey() {
195+
return key;
196+
}
197+
198+
public V getValue() {
199+
return value;
200+
}
201+
}
202+
203+
public static void main(String[] args) {
204+
HashMap<String, Integer> stringHashMap = new HashMap<>();
205+
206+
stringHashMap.put("a", 1);
207+
stringHashMap.put("b", 2);
208+
stringHashMap.put("c", 3);
209+
stringHashMap.put("d", 4);
210+
stringHashMap.put("e", 5);
211+
212+
stringHashMap.put("f", 6);
213+
stringHashMap.put("g", 7);
214+
stringHashMap.put("h", 8);
215+
stringHashMap.put("i", 9);
216+
stringHashMap.put("j", 10);
217+
stringHashMap.put("k", 11);
218+
219+
stringHashMap.put("a", 11);
220+
stringHashMap.put("k", 101);
221+
222+
stringHashMap.delete("k");
223+
stringHashMap.delete("a");
224+
stringHashMap.delete("c");
225+
226+
stringHashMap.print();
227+
228+
System.out.println();
229+
System.out.println(stringHashMap.get("j"));
230+
System.out.println(stringHashMap.get("k"));
231+
System.out.println(stringHashMap.get("d"));
232+
}
233+
}

0 commit comments

Comments
 (0)