Java
[TIL] 해시테이블 (Hash Table) 이란, Hash Table과 Hash Map의 차이 점
하늘☁️
2024. 12. 11. 00:02
해시 테이블 (Hash Table) 이란?
특징
- 데이터를 키 (key) 와 값 (Value) 의 형태로 저장한다. 각 키는 고유해야 하며, 이를 통해 값을 검색하거나 갱신할 수 있다.
- 동기화(Synchronzation) : HashTable 은 스레드 안전 (Thread-Safe) 하다. 멀티 스레딩 환경에서 동시에 접근해도 동기화가 보장된다. 이 점은 HashMap 과의 주요 차이점이다.
- 해시 함수 (Hash Function) : 내부적으로 해시 함수를 사용해서 키를 해시값으로 변환하고, 이 값을 기반으로 데이터를 저장하거나 검색한다.
- HashTable에서는 null 키와 null 값을 허용하지 않는다.
구조
HashTable 은 내부적으로 배열과 체이닝 (Chaining) 방식을 사용한다.
- 배열(Array) : 데이터를 저장하는 기본 구조
- 체이닝 : 충돌 (해시값이 같은 키가 여러 개 발생하는 상황)을 처리하기 위해 같은 해시값에 속한 여러 엔트리를 연결 리스트 형태로 저장한다.
해시 충돌
| Keys | Hash Function | Hash Value | Hash Table |
| 정글 | 민형 | 원딜 - 민형 | |
| 미드 | 민석 | 서폿 - 민석 | |
| 서폿 | 현준 | 정글 - 현준 | |
| 원딜 | 상혁 | 미드 - 상혁 |
예시로 롤 포지션을 집어넣고 해시 함수에서 T1 이라는 처리를 하게 되었을 때 해시 값은 티원의 포지션에 맞는 선수 이름을 값으로 가지게 된다. 만약 여기서 Keys 에 탑이 들어오게 된다면..
| Keys | Hash Function | Hash Value | Hash Table |
| 정글 | 민형 | 원딜 - 민형 | |
| 미드 | 민석 | 서폿 - 민석 | |
| 서폿 | 현준 | 정글 - 현준 | |
| 원딜 | 상혁 | 미드 - 상혁 | |
| 탑 |
25 T1엔 현준이가 두명이라 탑도 현준이를 가리키게 된다. 그러면 탑 정글이 모두 하나의 값, 현준이를 가르키니까 해시 충돌이 발생하게 되는 것!
이 충돌을 막을 수 있는 방법은 크게 개방 주소법과 분리 연결법이 있다.
해시 충돌 해결 방법
개방 주소법 - 선형 탐사법 (Linear Probing)
- 일정한 간격으로 슬롯을 탐색하는 방법
- 간격 = 1인 경우가 보통 일반적
- 탐색 공식 : Hash(key) + i (i는 충돌 발생 횟수)
- 문제점 : 일차 군집화 문제 발생 - 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
| Keys | Hash Function | Hash Value | Hash Table |
| 페이커 | 미드 | 페이커 - 미드 | |
| 구마유시 | 원딜 | 구마유시 - 원딜 | |
| 케리아 | 서폿 | 케리아 - 서폿 | |
이런식으로 데이터가 들어 있고 key 값으로 쵸비, 비디디, 쇼메이커가 들어오게 된다면 (해당 표에서 value값 위치는 key 값과 동일하다고 가정)
| Keys | Hash Function | Hash Value | Hash Table |
| 페이커 | 미드 | 페이커 - 미드 | |
| 쵸비 - 미드 | |||
| 구마유시 | 원딜 | 구마유시 - 원딜 | |
| 비디디 - 미드 | |||
| 케리아 | 서폿 | 케리아 - 서폿 | |
| 쇼메이커 - 미드 | |||
| 쵸비 | |||
| 비디디 | |||
| 쇼메이커 |
새로 들어온 키값들이 미드를 가르키는데, 미드 위치엔 데이터가 이미 있어서 i 를 하나씩 증가시키면서 값이 들어있지 않은 곳에 key와 value를 넣어준다. 그럼 표와같이 같은 값이 계속해서 들어올 경우 1차적으로 군집되는 문제가 발생한다.
개방 주소법 - 제곱 탐사법 (Quadratic Probing)
- 슬롯 간 간격이 제곱 형태로 커지는 방식
- 탐색 공식 : Hash(key) + i ^ 2
- 1차 군집화 문제를 보완할 순 있지만 2차 군집화 문제 발생 가능성이 있다.
| Keys | Hash Function | Hash Value | Hash Table |
| 페이커 | 미드 | 페이커 - 미드 | |
| 쵸비 - 미드 (1 ^ 2 = 1) | |||
| 구마유시 | 원딜 | 구마유시 - 원딜 | |
| 케리아 | 서폿 | 케리아 - 서폿 | |
| 비디디 - 미드 (2 ^ 2 = 4) | |||
| 쵸비 | |||
| 비디디 | |||
| 쇼메이커 | |||
| 쇼메이커 - 미드 (3 ^ 2 = 9) | |||
개방 주소법 - 이중 해싱 (Double Hashing)
- 충돌 시 보조 해시 함수를 사용하여 이동할 간격을 결정한다.
- 탐색 공식 : Hash(key) + i * Hash2(key) (여기서 Hash2(key) 는 0이 아닌 값을 반환)
- 다른 개방 주소법 방법에 비해 데이터가 골고루 분포된다.
분리 연결법 (Separate Chaining)
- 동일한 해시 값을 가진 키들을 연결 리스트 또는 다른 데이터 구조에 저장한다.
- 기본적으로 연결 리스트 형태를 사용하지만 트리나 동적 배열로 구현할 수도 있다.
| Keys | Hash Function | Hash Value | Hash Table |
| 정글 | 민형 | 원딜 - 민형 | |
| 미드 | 민석 | 서폿 - 민석 | |
| 서폿 | 현준 | 정글 - 현준, 탑 - 현준 | |
| 원딜 | 상혁 | 미드 - 상혁 | |
| 탑 |
개방 주소법과 분리 연결법의 비교
| 특징 | 개방 주소법 | 분리 연결법 |
| 메모리 사용 | 테이블 크기 내에서만 저장 가능 (고정 크기) | 추가 메모리 사용 (연결 리스트 등) |
| 충돌 해결 | 테이블 내에서 새 슬롯 탐색 | 버킷에 충돌된 요소를 저장 |
| 테이블 크기 | 테이블 크기가 작으면 성능 저하 | 테이블 크기가 작아도 문제 없음 |
| 성능 | 충돌 시 탐색 시간이 증가 | 충돌 시에도 효율적으로 탐색 가능 |
| 구현 난이도 | 간단 | 약간 복잡 |
| 삭제 | 복잡 | 개방 주소법에 비해 간단 |
주요 메서드
선언 및 초기화
Hashtable<Integer, String> table = new Hashtable<>();
put (데이터 삽입)
table.put(1, "Apple");
table.put(2, "Banana");
table.put(3, "Cherry");
get (데이터 검색)
System.out.println(table.get(2)); // 출력: Banana
remove (데이터 삭제)
table.remove(2);
System.out.println(table); // 출력: {1=Apple, 3=Cherry}
containsKey, containsValue (키 또는 값의 유무)
System.out.println(table.containsKey(1)); // 출력: true
System.out.println(table.containsValue("Banana")); // 출력: false
size (크기 확인)
System.out.println(table.size()); // 출력: 2
HashTable 과 HashMap 의 차이점
위에서 설명한대로 HashTable은 HashMap과 달리 멀티 스레드 환경에서 Thread-Safe 한다. 또한 HashTable에선 키와 값이 null 값을 가지는 것이 허용되지 않지만, HashMap 에서는 하나의 null 키와 다수의 null 값을 허용할 수 있다.
| 특징 | HashTable | HashMap |
| 동기화 | O | X |
| Null 허용 여부 | X | 하나의 Null 키와 다수의 Null 허용 |
| 성능 | 동기화로 인해 상대적으로 느리다. | 동기화가 없어 빠르다. |
| 멀티스레드 환경 사용 여부 | 멀티스레드에 적합 | 단일 스레드 환경에 적합 |