해시테이블(HashTable)
HashTable은 자료구조 중 하나로 (key,value)로 데이터를 저장한다. HashMap도 같은 방법으로 데이터를 저장하는 자료구조인데 둘의 차이은 Thread-Safe에 있다.
//HashTable
public synchronized V put(K key, V value) {}
//HashMap
public V put(K key, V value) {}HashTable은 synchronized키워드를 통해 멀티쓰레드에서 안전하며, HashMap은 멀티쓰레드에서 안잔하지 못하다.
HashTable은 고유의 index를 가지고 있어 자료를 찾을 때 평균 O(1)으로 매우 빠르지만, 해시충돌이 있었다면 연결된 자료들을 봐야해서 최대 O(n)까지 늦어 질 수 있다.
해시충돌
해시충돌이란 해시함수를 거쳐서 나온 해시값이 중복이 되는 경우를 말한다. 해시값이 최대한 충돌이 안나는게 가장 좋겠지만, 데이터가 많아 질 수록 충돌을 피하기는 어렵다.
Separate Chaining
위 그림은 John Smith와 Sandra Dee가 해시충돌을 일으킨 경우다. Separate Chaining은 해시가 충돌할 하여 같은 버킷으로 접근 할 경우 그림과 같이 LikedList같은 자료 구조를 통해 버킷을 연결하여 관리한다. 이 방법은 해시테이블의 활용성과 효율성이 좋지만 추가적인 메모리가 필요하고 충돌난 해시값으로 데이터를 검색할 경우에 연결된 값을 검사해야하므로 느리다는 단점이 있다.
Open Addressing
Open Addressing은 충돌이 발생하면 비어있는 다른 버킷에 데이터를 저장하는 방식이다.
-
Linear Probing : 충돌이나면 일정한 간격으로 버킷에 데이터를 저장.
-
Quadratic Probing : 충돌이 나면 제곱만큼(1,4,9,16...) 떨어진 버킷에 데이터를 저장.
-
Double Hashing : 두 종류의 해시함수를 사용하여 충돌이 나면 다른 해시함수를 또 돌려서 다른 버킷을 선택함.
Separate Chaining보단 메모리를 적게 사용하지만 해시테이블이 커질 수록 충돌이 잦아지며, 데이터를 삭제하면 충돌에 의해 뒤로 밀려난 데이터가 검색이 안될 수 있어 Dummy node를 사용해야하고 나중엔 테이블을 재정리 해야하는 복잡함이 있다.
한 줄평 : 데이터가 많아 질 수록 Open Addressing 방법은 관리가 힘들어 질 것 같다.
