자바 해시 테이블( Hashtable), 해시 맵(HashMap) 구조와 원리

막연하게 자바 해쉬 테이블이나 해쉬 맵을 당연하게 사용하고 있었다. 이를 테면 자전거를 타는 방법은 아는데 남한테 설명을 하라고 하면 제대로 설명을 하지 못하는 것과 비슷한 느낌이다.

 

예전에 자바를 초기에 공부할 때 LinkedList를 직접 구현해서 사용해본적이 있었는데 10년이 지난 지금까지 정확하게 기억은 안나도 시간이 조금 주어지면 금방 다시 만들수 있을 것 같기도 한데... 암튼 해시 테이블, 해시맵 정리해보자.

 

아주 간단히 생각해보자면 키와 값을 저장하는 컨테이너 컬렉션이다.

 

자바 해시 테이블(HashTable) vs 해시맵(HashMap) 차이 비교

 

중복 키에 대한 처리

키가 같은 값을 두번 넣게 되면 초기 값을 유지하게 되고, 해시맵은 키가 같은 값을 두번 넣게 되면 두번째 값으로 덮어버리는 차이가 있다.... 

 

쓰레드 세이프한 해시 테이블

해시테이블의 함수는 synchronized가 걸려있기 때문에 멀티 스레드 환경에서 데이터 조작에 대한 일관성이 보장된다. 물론 'Collections.synchronizedMap' 처럼 synchronized를 래핑하는 함수를 활용하면 HashMap도 충분히 스레드 세이프하게 동작시킬 수 있다. 쓰레드 세이프한 구현체인 ConCurrentHashMap를 사용해도 된다. ( null 키도 허용하지 않음. ) 

 

synchronized 처리가 없는 해시맵 속도가 압도적으로 빠르다. 

 

해시맵은 키에 널 값 허용

 

 

정도로 이해하고 있다.

---

해시맵(HashMap), 해시테이블(Hashtable) 원리

 

원리가 중요한데 우리가 해시맵, 해시테이블을 key, value 컬렉션으로 가장 많이 사용하는 이유는 당연 편하기 때문이고 데이터 탐색 구조가 O(n)이 아니라 O(1)이기 때문이다. 

키의 해시 처리 한 뒤 해시로 인덱싱을 관리하여 버킷에 저장하는 구조인 해시테이블, 해시맵

자바에서 int hashCode()를 이용해서 배열에 넣게 되는데 int 32비트 정수형으로 모든 해시 값을 담기에는 부족하기 때문에 

 

int index = X.hashCode() % M;

 

이런 형태로 M 개 배열을 사용하여 데이터 구현체를 관리한다. 해시맵 초기 용량은 16이고 로드팩터 0.75로 75%가 차면 용량을 2배로 늘리는 작업이 일어난다. 용량이 크게 필요한 경우 초기 용량을 정해주면 성능에 좋다. 75%가 되면 작업이 일어나므로 원하는 사이즈의 150% 정도로 설정해놓으면 용량 증가 작업이 일어나지 않게 사용 가능할 것이다. 

 

여기서 1 / m 확률로 같은 공간을 사용하게 되는데 이걸 해시 충돌이라 부르고 open addressing과 Separate Chaining 두가지 방식으로 자료 구조를 관리한다. 

 

먼저 오픈 어드레싱(open addressing)은 

해시 충돌이 발생하면 근처 버킷에 자료를 저장하는 방식을 가지기 때문에 그림처럼 존 스미스와 산드라 디가 같은 인덱스를 가질 때 152에 저장하지 못하고 153 버킷에 저장한다. 그 다음 테드 베이커가 153에 저장되려고 보면 산드라 디가 저장되어있어서 삭제를 비롯 다른 근처 버킷에 저장해야 하는 단점이 존재한다. 

 

검색할 때에도 충돌 검색이 이루어진다면 근처 버킷을 순회하여 찾는 방식으로 비어있는 버킷이 보일때까지 찾는다. 

---

해시 충돌 - 세퍼레이트 체이닝(Separate Chaining) 

 

자바 해시테이블, 해시맵은 두번째 방식인 세퍼레이트 체이닝(Separate Chaining)은 이름처럼 여러개를 해당 버킷에 엮는 방식이라 생각하면 된다. 링크드리스트로 엮는다. 

 

Separate chaining with linked lists

해시 충돌 - Separate chaining with linked lists

 

자바 해시 맵을 보면 Node와 TreeNode를 이용해서 엮는 걸 볼 수 있다. 대충 map.get(key)를 하게 되면 아래처럼 노드를 탐색하는 부분을 볼 수 있다. 

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

---

세퍼레이트 체이닝(Separate Chaining)과 오픈 어드레싱(open addressing) 효율 비교

 

데이터 갯수가 적을땐 오픈 어드레싱, 반대의 경우엔 체이닝이 효율이 좋다. 

---

 

자바 HashMap을 열어보면 최대 버킷수는 

static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

1073741824개가 될 수 있다. 갯수의 문제는 없을 것 같다.

 

초기 로드팩터가 별도로 설정하지 않으면 0.75로 설정되어있고

static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

75%가 차게 되면 버킷 양을 두배로 늘린다. 물론 최대 갯수인 1073741824개까지 2배로 늘리는 형태이다. 

---

이렇게 자바 해시테이블, 해시맵  associative array ( 연관 배열 ) 구현체에 대해서 알아봤는데 단순하게 키를 해시처리하여 O(1)로 값을 찾을 수 있는 효율적인 자료 구조다. 표준 데이터 포맷인 JSON과도 1:1이고 일부 dto나 vo를 대체하여 사용하기도 한다. 많은 프레임워크, 라이브러리 내부에서도 쉼 없이 만들어지고 없어진다. 

 

개인적으로 자바에서 가장 애정하는 데이터 구조체다. 

---

참고.

 

https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

https://github.com/wjdrbs96/Today-I-Learn/blob/master/Java/Collection/Map/HashMap%EC%9D%B4%EB%9E%80%3F.md#%ED%95%B4%EC%8B%9C-%EC%B6%A9%EB%8F%8Ccollisions

wjdrbs96/Today-I-Learn

https://d2.naver.com/helloworld/831311

 

https://www.youtube.com/watch?v=xls6jEZNA7Y