Complexity and Load Factor
HashMap의 Insert 작업은 Key-Value가 나눠져서 진행된다.
먼저, Hash Function을 통해서 Key를 양의 정수 형태로 변환한다. 여기서 시간은 Key의 원본 데이터의 사이즈에 따라 달라지게 되는데 사실상 무시할 수 있는 수준이라 시간 복잡도는 O(1)이 된다.
두번째로, Key를 통해 index를 선정했다면 Linked List에 Value를 붙여야 하는데 최악의 경우 모든 노드가 하나의 인덱스에 들어있다면 n번의 탐색을 해야한다. (Linked List는 인덱스를 가지지 않으므로 마지막 위치를 알기위해선 끝까지 탐색을 해야한다.) 이 경우에 O(n)까지 시간 복잡도가 높아지게 된다.
하지만 대부분의 Hash Function은 Hash Map에 적절하게 노드가 분배되도록 설계되었기 때문에 O(n)까지 가는 경우는 없고 대부분 O(1)에 수렴한다.
load factor는 전체 노드의 개수를 Capacity로 나눈 값으로 구할 수 있다.
load factor = 전체 노드 개수/Capacity
전체 노드 개수가 6개이고 Capacity가 3이라면 각 Bucket에는 2개의 노드가 존재하게된다.(load factor가 2)
load factor를 낮게 유지하는게 Hashing 성능의 핵심이다.
Rehashing
이름 그대로 Hashing을 다시 하는것이다.
load factor가 설정한 임계치 값 보다 커지게 되었을 때(자바 기준 0.75) Capacity를 2배로 늘리게되는데 이때 기존에 존재하는 Node를 재분배하는 작업을 하게되는데 이를 Rehashing이라 한다.
Rehashing을 하는 이유는? 성능때문이다. 노드를 적절하게 분배함으로써 시간 복잡도를 O(1)이 되도록한다.
Sample Source Code
1
2import java.util.ArrayList;
3
4public class RehashingSampleMap<K,V> {
5
6 // HashMap에서 사용할 Node의 구조를 정의한다
7 class Node<K, V> {
8
9 K key;
10 V value;
11 Node<K, V> next;
12
13 public Node(K key, V value) {
14 this.key = key;
15 this.value = value;
16 next = null;
17 }
18 }
19
20 ArrayList<Node<K, V>> buckets;
21 int size; // 전체 Node의 개수
22 int numBuckets; // 버킷의 개수
23
24 final double DEFAULT_LOAD_FACTOR = 0.75;
25
26 public RehashingSampleMap() {
27
28 numBuckets = 5; //Initial Bucket Number is 5
29
30 buckets = new ArrayList<>(numBuckets);
31
32 for (int i = 0; i < numBuckets; i++) {
33 buckets.add(null);
34 }
35 System.out.println("HashMap created");
36 System.out.println("Number of pairs in the Map: " + size);
37 System.out.println("Size of Map: " + numBuckets);
38 System.out.println("Default Load Factor : " + DEFAULT_LOAD_FACTOR + "\n");
39 }
40
41 private int getBucketIndex(K key) {
42
43 // Using the inbuilt function from the object class
44 int hashCode = key.hashCode();
45
46 // array index = hashCode%numBuckets
47 return (hashCode % numBuckets);
48 }
49
50 public void insert(K key, V value) {
51 // key와 매칭된 bucket의 인덱스
52 int bucketIndex = getBucketIndex(key);
53
54 // bucket을 가져온다. 이 뜻은 각 버켓의 Head Node를 가져온다는 뜻!!
55 Node<K, V> head = buckets.get(bucketIndex);
56
57 // bucket내에 이미 존재하고 있는 key인지 검사하고 존재한다면 value를 덮어쓰기 하고 종료
58 while (head != null) {
59
60 // If already present the value is updated
61 if (head.key.equals(key)) {
62 head.value = value;
63 return;
64 }
65 head = head.next;
66 }
67
68 // 새로운 노드를 만든다
69 Node<K, V> newElementNode = new Node<>(key, value);
70
71 // 새로운 노드를 넣을 bucket을 가져온다
72 head = buckets.get(bucketIndex);
73
74 // 새로 들어온 Node의 next를 첫번째 Node로 한다
75 // 원형 Linked List 구조!
76 newElementNode.next = head;
77 // 새로 들어온 element가 Head가 될 수 있도록 한다
78 buckets.set(bucketIndex, newElementNode);
79
80 System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n");
81
82 // 전체 Node 개수를 1 증가 시킨다
83 size++;
84
85 // load factor를 재계산 한다.
86 double loadFactor = (1.0 * size) / numBuckets;
87
88 System.out.println("Current Load factor = " + loadFactor);
89
90 // If the load factor is > 0.75, rehashing is done
91 if (loadFactor > DEFAULT_LOAD_FACTOR) {
92 System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR);
93 System.out.println("Therefore Rehashing will be done.\n");
94
95 // Rehash
96 rehash();
97
98 System.out.println("New Size of Map: " + numBuckets + "\n");
99 }
100
101 System.out.println("Number of pairs in the Map: " + size);
102 System.out.println("Size of Map: " + numBuckets + "\n");
103 }
104
105 private void rehash() {
106
107 System.out.println("\n***Rehashing Started***\n");
108
109 // The present bucket list is made temp
110 ArrayList<Node<K, V> > temp = buckets;
111
112 // New bucketList of double the old size is created
113 buckets = new ArrayList<>(2 * numBuckets);
114
115 for (int i = 0; i < 2 * numBuckets; i++) {
116 // Initialised to null
117 buckets.add(null);
118 }
119 // Now size is made zero
120 // and we loop through all the nodes in the original bucket list(temp)
121 // and insert it into the new list
122 size = 0;
123 numBuckets *= 2;
124
125 // insert 작업을 다시 수행한다!!!!
126 for (int i = 0; i < temp.size(); i++) {
127
128 // head of the chain at that index
129 Node<K, V> head = temp.get(i);
130
131 while (head != null) {
132 K key = head.key;
133 V val = head.value;
134
135 // calling the insert function for each node in temp
136 // as the new list is now the bucketArray
137 insert(key, val);
138 head = head.next;
139 }
140 }
141
142 System.out.println("\n***Rehashing Ended***\n");
143 }
144
145 public void printMap() {
146
147 // The present bucket list is made temp
148 ArrayList<Node<K, V> > temp = buckets;
149
150 System.out.println("Current HashMap:");
151 // loop through all the nodes and print them
152 for (int i = 0; i < temp.size(); i++) {
153
154 // head of the chain at that index
155 Node<K, V> head = temp.get(i);
156
157 while (head != null) {
158 System.out.println("key = " + head.key + ", val = " + head.value);
159
160 head = head.next;
161 }
162 }
163 System.out.println();
164 }
165
166 //Function to get an element from Map
167 public V getValue(K key){
168 //Get actual index of the key
169 int actualIndex = getBucketIndex(key);
170 Node<K,V> temp = buckets.get(actualIndex);
171 //Search for key in list
172 while(temp != null){
173 if(temp.key == key){
174 return temp.value;
175 }
176 temp = temp.next;
177 }
178 return null;
179 }
180
181
182
183
184}