[TIL] 해시테이블 (Hash Table) 이란, Hash Table과 Hash Map의 차이 점

해시 테이블 (Hash Table) 이란?

특징

1. 데이터를 키 (key) 와 값 (Value) 의 형태로 저장한다. 각 키는 고유해야 하며, 이를 통해 값을 검색하거나 갱신할 수 있다.
2. 동기화(Synchronzation) : HashTable 은 스레드 안전 (Thread-Safe) 하다. 멀티 스레딩 환경에서 동시에 접근해도 동기화가 보장된다. 이 점은 HashMap 과의 주요 차이점이다.
3. 해시 함수 (Hash Function) : 내부적으로 해시 함수를 사용해서 키를 해시값으로 변환하고, 이 값을 기반으로 데이터를 저장하거나 검색한다.
4. 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 허용
성능	동기화로 인해 상대적으로 느리다.	동기화가 없어 빠르다.
멀티스레드 환경 사용 여부	멀티스레드에 적합	단일 스레드 환경에 적합