Java - HashTable이란?

 

Java의 데이터구조에서는 이름에 Hash가 붙은 클래스들이 있다. 예를 들면 HashMap, HashSet 등이 있다. Hash가 들어간 클래스들은 모두 HashCode를 사용해서 구현한 데이터구조이다.  HashMap, HashSet을 사용하는 방법은 잘 알고 있는데 어떻게 작동하는지에 대해서도 알아보자. Java에서 Hash를 사용한 자료구조들을 이해하기 위해서는 HashTable에 대해서 알아야하는데 HashTable에 대해서 간략하게 알아보도록하자.  

 

HashTable

HashTable은 위의 사진과 같이 도식화할 수 있다. 그림을 보면 key를 Hash함수에 넣는 것을 확인할 수 있는데, Hash라는 것은 어떤 입력을 넣으면 암호화해서 어떠한 값으로 바꿔주는 기능이다. A라는 키를 Hash 함수에 넣어서 5라는 HashCode가 나온다면 어떠한 경우에도 항상 A를 넣으면 5가 나와야한다. HashCode는 결국 배열에서 index 역할을 하게되고 HashTable은 Hash함수에서 얻은 HashCode에 따라서 정리한 테이블이다. 

 

HashMap을 예시로 어떻게 HashTable을 사용하는지 알아보자. HashMap에 put 함수를 이용해서 abc라는 키값에 값을 넣는다고 하면 abc를 Hash 함수를 사용해서 고유한 Int 값을 얻어낸다. 예를들어 abc 키의 HashCode를 54201이라고 하면 54201번째의 index에 넣어야할까? 그렇게 사용하기에는 메모리 낭비가 너무 심하다. 그렇기 때문에 HashTable에는 capacity가 있다. 예를 들어 capacity가 8이라고 하면 길이가 8인 LinkedList로 이루어진 배열을 만들고 54201을 8로 Modulo해서 나머지 값을 index로 사용한다. 54201을 8로 modulo하면 1이 나온다. 원소의 개수가 많아지다보면 index가 동일한 key가 발생하게 된다. 이를 Hash Collision이라고 한다. 예를들어 aaa라는 키의 HashCode도 8로 나누면 abc와 같은 index를 가질 수 있다. 이 경우를 대비해서 LinkedList가 있는 것이다. aaa라는 키는 abc의 LinkedList 뒤쪽에 붙여주게 된다. 

 

그런데 마냥 LinkedList가 길어진다면 HashMap의 특징인 빠른 조회에 지장이 생기기 때문에 배열의 사용량이 일정 크기를 넘어서게 되면 자동으로 capacity를 증가시킨다. 이게 바로 HashMap의 동작 원리이다.

 

조회하는 방법은 위에서 설명한 방법과 동일하다고 보면 되는데 예를 들어서 abc라는 키 값을 조회 한다고 하면 HashCode를 얻어내서 해당 index의 값을 확인하고 첫번째 값에서 찾았다면 값을 반환하고 만약 찾지 못했다면 LinkedList에서 값을 찾을 때까지 순회한다.

 

HashTable의 구현 방법에도 오픈메모리, 체이닝 방식 등이 있는데 위에서 설명한 방법은 체이닝 방법이고 체이닝 방법이 자바에서 사용하고 있는 방법이니 참고하면 좋겠다.