HashMap은 Java의 Map인터페이스를 구현한 클래스입니다. 하지만 Map인터페이스, 즉 Java에서 Collection Framework로 표준화된 데이터 구조 인터페이스를 제공하기 전에는 HashTable 클래스가 있었습니다. HashMap의 HashTable을 개선한 클래스입니다.
HashMap의 정의와 특징을 살펴보기 전에 간단히 Hash Table을 살펴보겠습니다. (지금부터 설명하는 Hash Table은 Java의 HashTable클래스가 아닌 일반적인 Hash Table 데이터 구조입니다)
HashTable
HashTable은 데이터를 저장 및 처리하는 데이터 구조입니다. 저장하려하는 데이터를 통(bin)에 나눠 담는 형식으로 데이터를 저장하고 검색합니다. 그렇기 때문에 array처럼 데이터를 연속적으로 저장하거나 처리하지 않습니다.
또 저장하려는 데이터와 특정 bin으로 분류하는 기준이 다릅니다. 이는 물류창고에서의 제품과 바코드에 비유할 수 있습니다.
저는 물류창고에서 알바를 한 경험이 있는데요, 물류 창고에는 정말 수 많은 제품들이 있습니다. 물류창고로 실려온 실제 제품은 특정 위치에 진열이 되고 고객이 주문한 수량만큼 넘겨져 배송됩니다. 이 때 진열되는 위치는 상품 그 자체보다는 상품의 바코드와 관련이 있습니다. 주문이 들어온 상품을 찾으러갈 때도 상품의 사진을 보며 찾아가는것이 아니라, 상품의 바코드를 찍어서 나온 위치 정보를 보고 곧장 그 위치로 갈 수 있습니다.
이처럼 데이터 그 자체가 아닌 데이터와 1:1로 매칭되는 숫자(바코드)를 통해 데이터를 분류해서 효과적으로 데이터를 저장 및 처리하는 데이터 구조가 Hash Table입니다.
Hash Table의 저장 과정
Hash Table은 array와 hash 함수로 이루어져있습니다. Hash Table에 데이터를 저장할 때의 과정은 아래와 같습니다.
- 저장하려는 데이터를 hash 함수에 입력값으로 넣고 실행합니다
- 반환된 hash 함수의 결과 값(hashcode, 음이 아닌 정수)을 index로 변환합니다
- index로 데이터를 저장하는 array에 접근하여 해당 위치에 데이터를 저장합니다
2번 단계에서 얻은 hashcode를 index로 변환할 때는 보통 hashcode를 array의 길이로 나머지 함수를 실행한 결과값을 사용합니다.
Hash Table의 특징
위의 저장 과정을 살펴보면 Hash Table의 여러 특성을 알 수 있습니다.
- 데이터 그 자체가 저장과 검색의 기준이 될 수 있습니다. 데이터를 hash 함수에 입력값으로 넣어 얻은 결과값을 index로 활용하기 때문입니다
- 탐색속도가 빠릅니다. 데이터를 일일히 대조해서 검색하는 것이 아니라, hashcode로 저장 위치(bin)를 얻을 수 있기 때문입니다
- Hash Table은 hashcode를 기준으로 여러 bin(array)에 나눠 저장되기 때문에 데이터의 정렬이 다른 데이터 구조보다 불리합니다. 그래서 데이터 정렬에 신경을 쓰지 않아도 될 때 Hash Table을 사용해야합니다
collision
Hash Table에서 데이터를 저장하는 array의 길이가 3이라고 가정해봅시다. "kitty", "beer", "cat"이라는 세 개의 데이터를 저장해야 하는데, hash 함수를 통해 얻은 index가 모두 0이 나온다면 충돌(collision)이 발생합니다. 세개의 데이터 모두가 저장되지 못하거나 많아도 하나만 저장되겠죠.
다른 데이터를 hash function에 돌렸을 때 같은 output이 나오는 경우, 또 다른 hash코드를 index로 변환했을 때 index가 동일 할 때 충돌이 발생합니다. 이 충돌을 방지하기 위해서는 chaining이라는 방식을 사용합니다.
chaining
Hash Table에서 데이터를 array가 아닌 Linked List의 첫번째 Node를 저장하는 방법입니다. c언어라면 pointer를 저장하겠지만 Java에는 pointer가 없으니까요. 충돌을 방지하기 위해 그냥 모든 데이터를 연결하여 저장하는 것으로 해결하는 방법입니다. Linked List 형태이기 때문에 데이터들을 비연속적으로 저장할 수 있습니다. array처럼 반드시 연속된 저장공간을 확보하지 않아도 되죠. 새 값을 저장할 때는 기존 값의 위치를 가리키는 정보를 새 값이 대신 저장하고, 그 곳에 새 값의 위치 정보를 저장하면 됩니다. 때문에 (순차적인)저장 속도가 빠릅니다. 또 길이를 계속해서 늘릴 수 있기 때문에 많은 양의 데이터를 저장하는데 매우 효과적입니다.
그렇다고 해서 collision이 발생할 때마다 계속 Linked List의 길이를 늘여가는 것은 바람직하지 않습니다. 때문에 중복된 값을 최소한으로 반환하는 hash 함수의 알고리즘이 Hash Table에서는 매우매우 중요합니다. Hash Table에 대한 설명은 이쯤하고, 다시 HashMap으로 돌아가볼까요?
HashMap
HashMap이란
Java의 Map 인터페이스를 구현한 클래스인 HashMap은 Key와 Value, 한 쌍의 데이터를 저장하는 데이터 구조입니다. HashTable의 구조를 그대로 사용합니다. 데이터를 저장하는 LinkedList와 LinkedList의 첫 Node를 저장하는 array로 구성되어있습니다.
HashMap의 특징
- key로 데이터를 검색하기 때문에 HashMap 내에서 유일한 값이어야합니다
- 중복된 key로 값을 저장하면 값이 새로 저장되는 데이터로 덮어씌워집니다
- 내부적으로 LinkedList를 사용하여 비연속적인 저장공간을 가지고 한정되지 않은 수의 데이터를 저장하는데 사용됩니다
- 검색 속도가 빠릅니다. O(1)이라고 하죠. input값과 상관없이 처리 속도가 동일하다는 의미입니다. 하지만 LinkedList의 길이에 따라 O(n)(입력값이 커질수록 처리 시간이 증가)이 될 수도 있습니다. (참고: 시간표기법과 BigO 표기법)
- 저장 순서를 보장하지 않습니다
- 새로 저장하려는 요소가 새로운 요소임을 판단하는 기준은 다음과 같습니다
1. hashCode()의 반환값이 일치하지 않거나(or)
2. equals()가 false일 때
따라서 HashMap에 저장할 새로운 클래스를 정의할 때 주소값이 아닌 다른 기준으로 요소를 비교하고 싶다면, equlas() 뿐만 아니라 hashCode()도 오버라이딩을 해야합니다.
HashMap 구현하기
HashMap에대한 특징들을 살펴봤으니 본격적으로 HashMap을 구현해보겠습니다.
먼저 HashMap 클래스를 작성해줍니다.
public class HashMap{
}HashMap은 key와 value 한쌍의 데이터를 저장하는 데이터구조입니다. 관련된 데이터를 함께 다루기 위해 내부 클래스 Node를 선언하겠습니다.
public class HashMap{
class Node {
int hash; //hashcode 저장
String key;
String value;
Node nextNode; //다음 Node의 주소를 저장
public Node(int hash, String key, String value) {
this.hash = key.hashCode();
this.key = key;
this.value = value;
}
void setValue(String value) {
this.value = value;
}
String getValue(){
return value;
}
int getHash(){ return hash; }
String getKey() { return key; }
}
}HashMap에 저장하는 key, value, hashcode 그리고 LinkedList 구조이기 때문에 다음 요소를 참조하는 nextNode를 멤버변수로 선언했습니다. 이를 초기화하는 생성자와 getter, setter도 작성했습니다.
HashMap은 LinkedList와 LinkedList의 첫 Node들을 저장하는 array, 그리고 hash 함수로 구성됩니다. 첫 Node를 저장하는 array를 선언하고 이를 초기화하는 생성자도 작성하겠습니다.
public class HashMap{
Node[] table;
HashTable(int size) {
this.table = new Node[size];
}
class Node {
int hash; //hashcode 저장
String key;
String value;
Node nextNode; //다음 Node의 주소를 저장
...
}
}간단한 hash 함수를 작성할까.. 했는데 오버라이딩이 쉽지 않을 것 같아서 Object와 String 클래스의 hashCode()를 그대로 사용하겠습니다.
public class HashMap{
Node[] table;
HashTable(int size) {
this.table = new Node[size];
}
class Node {
int hash; //hashcode 저장
String key;
String value;
Node nextNode; //다음 Node의 주소를 저장
...
}
public int hash(String key){
return key != null ? key.hashCode() : 0;
}
}이 hashcode를 index로 변환하는 코드를 작성해볼까요? 나머지 연산을 사용하여 간단하고 classic하게 구현해보았습니다.
public int convertToIndex(int hashCode) {
return hashCode % table.length;
}바로 HashMap에 key와 value를 저장하는 put메서드를 작성해보겠습니다.
public void put(String key, String value) {
int hash = hash(key);
int index = convertToIndex(hash);
Node e; // current element
Node n; // next element
if ((e = table[index]) == null) { //array에 어떤 Node도 저장되어 있지 않다면
table[index] = new Node(hash, key, value); //새로운 Node 생성해서 저장
} else {
do {
if (hash == e.getHash() //연결된 node들을 찾아다니면서 같은 node가 있다면 덮어쓰기를,
&& key.equals(e.getKey())) {
e.setValue(value);
break;
} else if ((n = e.nextNode) == null) { //없다면 마지막node에 추가 하기
e.nextNode = new Node(hash, key, value);
break;
}
e = n;
} while (true);
}
}사실 같은 Node를 찾는 조건에는 key.equals(e.getKey()))만 있어도 되지만, 실제 HashMap에서는 equals 메서드와 더불어 hashcode도 비교하기 때문에 hash == e.getHash()를 추가했습니다.(여전히 실제 HashMap 코드와는 차이가 있습니다)
저장한 요소를 찾는 메서드 searchKey입니다.
public Node searchKey(Node node, String key) {
do {
if(hash(key) == node.getHash()
&& key.equals(node.getKey())){
return node;
}
node = node.nextNode;
} while (node != null);
return null;
}저장한 요소를 가져오는 메서드 get입니다
public String get(String key) {
int hashCode = hash(key);
int index = convertToIndex(hashCode);
System.out.println(key + ", hashCode(" + hashCode + "), index(" + index + ")");
Node node = searchKey(table[index], key);
return node == null ? "Not found" : node.getValue();
}요청한 key에 해당하는 값이 HashMap에 저장되어있지 않은 경우 Not found를 반환하도록 구현했습니다. 또 key, hashcode, 그리고 index를 확인하기 위해서 println()를 작성했습니다.
그럼 이제 HashMap 클래스를 생성해서 사용해볼까요?
public class Main {
public static void main(String[] args) {
HashTable h = new HashTable(3);
h.put("ahn", "she is smart");
h.put("kim", "he is cute");
h.put("kim", "he is not cute"); // 중복 값
h.put("park", "he is tough");
System.out.println(h.get("ahn"));
System.out.println(h.get("kim"));
System.out.println(h.get("sung")); //존재 하지 않는 값
System.out.println(h.get("park"));
}
}
위의 사진은 console에 출력된 결과값입니다. 결과값 중 눈여겨 볼 것은 두가지 입니다
- "kim"이라는 중복된 key로 작성했을 때 value가 덮어 씌워지는 것을 확인할 수 있습니다
- "sung"이라는 존재하지 않는 key로 데이터를 요청했을 때 Not found를 반환하는 것을 확인할 수 있습니다
작성한 코드는 이 영상과 Java HashMap 내부 구현 코드를 참고하고 수정하여 작성한 코드입니다.
Hash Table, HashMap의 정의와 특징을 살펴보고 직접 HashMap을 간단히 구현해보았습니다. 데이터를 다루는 구조를 잘 알고 활용하는 것이 결국 데이터(숫자)를 저장하고 처리하는 기계인 컴퓨터를 잘 활용할 수 있는 방법임을 배울 수 있었습니다. 개선사항이나 수정해야할 내용이 있다면 알려주시면 감사드리겠습니다. 끝 까지 읽어주셔서 감사합니다.
참고한 영상, 책, 사이트
1. https://www.youtube.com/watch?v=nvzVHwrrub0
2. https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table해시-해싱-해시테이블-자료구조의-이해-6ijyonph6o#해시-테이블hash-table
3. https://www.youtube.com/watch?v=S7vni1hdsZE
4. https://www.youtube.com/watch?v=Vi0hauJemxA
5. 자바의 정석(남궁성)
사진 출처
1. https://namu.wiki/jump/pnGvDbMADynTwaKKKGQw1RFI3xAiXFNbOna1k47Yu10LfvjKhQq1OlGttln26hW2CuemXUjD%2FGCjSU5l%2Bbjn%2Fw%3D%3D
2. https://unsplash.com/ko/%EC%82%AC%EC%A7%84/JwMGy1h-JsY
3. https://www.youtube.com/watch?v=nvzVHwrrub0
