1. Java의 HashTable
< HashTable이란? >
{Key, Value}로 데이터를 저장하는 자료구조.
내부적으로 배열(버킷)을 사용하므로, 빠른 조회가 가능하다.
( 각각의 Key 값에 해시함수 적용 -> 고유한 index 생성 -> 이 index로 검색. )
해싱 구조로 데이터를 저장하면 1번의 해시 함수 사용으로 O(1)
해시 함수 종류
: 고유 인덱스를 어떻게 계산을 하느냐가 성능에 중요하다.
-
Division Method
: 나눗셈을 이용하는 방법( 주소 = 입력값 % 데이터 테이블의 크기, 2의 제곱수 ) -
Digit Folding
: 각 Key의 문자열을 ASCII 코드로 변경 -> 값을 합한 데이터를 테이블 내의 주소로 사용. -
Multiplication Method
-
Univieral Hashing.
해시 충돌
: 두 변수의 해시값이 동일할 경우 충돌 -> 어떻게 동일한 해시값을 관리하나?
- 분리 연결법
동일한 버킷의 데이터에 대해 자료구조를 활용해 메모리 추가 -> 다음 데이터의 주소를 저장
Java8의 Hash테이블은 Self-Balancing Binary Search Tree를 이용해 Chaining 방식을 구현.
그러나, 데이터의 수가 많아지면 동일한 버킷에 다량의 데이터가 chaining -> 조회성능 저하.
- 개방 주소법
비어있는 해시 테이블의 공간을 활용하는 방법.
Hash Table 재정리 해주는 작업이 필요.
HashTable의 시간복잡도
일반적으로 O(1)이나 해시 충돌이 발생할 경우, O(N)임.( 끝까지 조회를 해야하므로. )
테이블이 꽉 차있는 경우라면, 테이블 확장 -> 심각한 성능 저하.
해시 테이블에서 자주 사용하게 되는 데이터 개시 -> 캐시 hit에 의해서 성능 향상.
Java의 HashTable vs HashMap
: 동기화 지원 여부의 차이가 있다.
2. Java의 HashTable 주요 특징
-
동기화(Synchronized): Hashtable의 모든 메서드는 synchronized 키워드를 사용하여 동기화된다. 따라서 여러 스레드가 동시에 Hashtable에 접근하더라도 일관성이 보장된다. (아래 목차에서 메서드를 살펴보면 이해할 수 있다.)
-
동시성(Concurrency): Hashtable은 여러 스레드에서 동시에 읽기 및 쓰기를 안전하게 수행할 수 있다. 하지만, 모든 메서드가 동기화되어 있기 때문에 많은 스레드가 동시에 Hashtable을 사용하면 성능 저하가 발생할 수 있다.
- 빠른 검색: 해시 테이블을 사용하여 데이터를 저장하므로, 일반적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있다.
잘 사용되지 않는 이유
-
성능 문제: 앞서 설명한 것처럼, 모든 메서드가 synchronized로 동기화되어 있는 Hashtable은 동시성 제어를 위해 단일 락을 사용하므로, 성능이 저하될 수 있다. 높은 동시성이 요구되는 환경에서는 ConcurrentHashMap이 훨씬 더 나은 성능을 제공하기 때문에, Hashtable이 자주 사용되지 않는다. (사실 쓰는 걸 못 봤다.)
-
유연성 부족: Hashtable은 null 키와 값을 허용하지 않는다. 반면 HashMap은 null 키와 값을 허용하며, 일반적인 사용에서 더 유연하다.
-
Java Collections Framework의 발전: Java 2가 도입되면서 Collections Framework가 추가되었고, HashMap, TreeMap, ConcurrentHashMap과 같은 더 나은 성능과 유연성을 제공하는 컬렉션 클래스들이 등장했다. 이로 인해 Hashtable의 사용은 점차 줄어들었다고 한다.
-
더 나은 대체재 존재: HashMap과 ConcurrentHashMap은 Hashtable의 기능을 대체할 수 있는 더 나은 선택지다. 따라서, 새로운 프로젝트나 코드에서는 거의 사용되지 않는다.
HashMap의 작동 원리
하나의 버킷에 들어간 노드 수가 8개가 초과할 경우 자료 구조를 트리(레드 블랙 트리)로의 변경을 시도한다.
하지만 트리로 변경하지 전, HashMap의 전체 크기를 검사하여 64보다 작은 경우 먼저 해시 버킷 배열을 확장(resize)한다
( 버킷이 작으면 잦은 충돌을 발생시키기 때문이다. )
그리고 특정 임계값이 넘어가면, resize를 발동한다.
