[자료구조] (3) 해시테이블(Hash Table)이란?

해시테이블(Hash Table)

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

 

해시테이블은 내부적으로 키를 해시 함수(Hash Function)에 통과시켜 인덱스로 변환하고, 이 인덱스에 데이터를 저장한다.

Key('apple') → [Hash Function] → Index(5) → 배열에 저장

예를 들어 "apple"라는 문자열을 해시 함수에 넣으면 5라는 인덱스가 나오고, 배열의 5번째 칸에 저장하는 방식이다.

왜 해시테이블인가?

배열이나 리스트는 인덱스를 통해 값을 찾을 수는 있지만, 특정 값을 찾으려면 결국 선형 탐색을 해야 한다.
그에 반해, 해시테이블은 키(Key)를 이용해서 거의 O(1) 시간에 값을 찾아낼 수 있다.

 

해시함수(Hash Function)

해시 테이블은 결국 좋은 해시 함수로 이루어져 있어야 해쉬테이블의 품질을 결정한다. 그럼 대표적인 해시함수는 어떤게 있을까?

1. Division Method (나머지 연산 방식)

• 가장 단순하고 널리 쓰이는 방법
• hash(key) = key % table_size

장점 :

• 빠르고 간단

단점 :

• 테이블 크기가 나쁜 수(예: 짝수, 2의 배수)이면 충돌 확률 증가
• 소수(prime number)**를 테이블 크기로 설정하는 게 좋음

2. Multiplication Method (곱셈 방식)

• (A * key) % 1을 구한 뒤, 이를 테이블 크기와 곱해서 인덱스 산출
• h(k) = floor(m × ((k × A) mod 1)) → A는 0과 1 사이의 상수

장점 :

• 키의 분포가 균등하지 않아도 비교적 균등한 해시값을 제공

단점 

• 연산이 복잡해서 속도는 조금 느림

3. Folding Method (접기 방식)

• 키를 일정한 길이로 나누고, 그 조각들을 더하거나 XOR 연산 (예 : key = 987654 → (98 + 76 + 54) = 228 → 228 % tableSize)

장점

• 숫자 키에 유용

단점

• 문자열이나 불규칙한 데이터엔 비효율적

충돌(Collision)과 해결 방법

여러 키가 같은 인덱스로 해시될 수 있는데, 이를 충돌(Collision)이라고 한다.
해시테이블의 성능은 이 충돌을 얼마나 잘 처리하느냐에 따라 결정된다.

충돌 처리 방법

1. 체이닝(Chaining)
   • 같은 인덱스에 여러 값을 리스트 형태로 저장 체이닝(Chaining)
2. 오픈 어드레싱(Open Addressing)
   • 충돌 발생 시 빈 공간을 찾아 저장
   • 선형 탐색(linear probing), 이차 탐색(quadratic probing), 이중 해싱(double hashing) 등 방식 존재