키(key), 값(value)의 대응으로 이루어진 테이블 같은 형태의 자료구조
📌 해시 테이블 구조
키(Key) 를 이용해 데이터를 저장하고 검색하는 자료구조
버킷(Bucket): 데이터를 저장하는 공간
버킷 배열: 여러 개의 버킷들이 배열 형태로 구성됨
📌 해시 테이블 동작 원리
1️⃣ 키를 해시 함수에 적용 → 특정 인덱스(버킷) 반환
2️⃣ 반환된 인덱스를 사용해 해당 버킷에 데이터 저장
3️⃣ 키를 다시 사용하면 동일한 인덱스 반환 → 빠른 검색 가능
로드 팩터(loadfactor)
해시 테이블에 저장된 데이터 수를 버킷의 수로 나눈값
해시 테이블이 현재 얼마나 가득 차 있는지에 대한 지표로, 로드 팩터가 클수록 해시 테이블의 성능이 떨어짐
해시 함수
- 임의 길이의 데이터를 고정된 길이의 데이터(해시 값)로 변환하는 단방향 함수
- 단방향성이므로 해시 값으로 원래 데이터를 역추적할 수 없음
📌 해시 알고리즘 종류
- MD5
- SHA-1
- SHA-256, SHA-512, SHA-3
- HMAC 등
- 같은 데이터라도 적용하는 해시 알고리즘이 다르면 해시 값이 달라짐
📌 해시 함수의 특징
- 해시 값은 입력 데이터가 조금만 달라도 완전히 다른 값이 됨
- 데이터 무결성 검증에 사용 → 전송된 데이터의 변조 여부 확인 가능
- 비밀번호 저장 시 활용 → 단방향 암호화를 통해 보안 강화
📌 해시 테이블과 해시 함수
- 빠른 검색 속도를 제공 → 일반적으로 삽입, 삭제, 검색 연산의 시간 복잡도는 O(1)
- 단점: 많은 메모리 공간을 소모
- 해시 충돌 문제 발생 가능 → 이를 해결하기 위해 별도의 충돌 해결 기법 사용
📌 모듈러 연산을 이용한 간단한 해시 함수
- 해시 값 h(K) = K mod M (M: 해시 테이블 크기)
- 예:
- Key = 200, Table Size = 15 → 200 mod 15 = 5
- Key = 100, Table Size = 15 → 100 mod 15 = 10 - 하지만 단순한 해시 함수는 해시 충돌 가능성이 높아 실제로 잘 사용되지 않음
해시 충돌
서로 다른 키(Key) 가 동일한 해시 값(Hash Value)을 가지는 경우 발생
> 예: 다른 이름에 같은 전화번호가 매칭되는 상황📌 해시 충돌 문제점
- 데이터 무결성 검증에서 잘못된 데이터가 유효한 것으로 판단될 가능성
- 보안상 취약점이 발생할 수 있음 (예: SHA-1 해시 충돌 사례)
- 해시 테이블에서 충돌이 발생하면 검색 성능 저하
📌 해시 충돌 해결 방법
1️⃣ 체이닝(Chaining) 기법
- 충돌이 발생하면 같은 인덱스에 연결 리스트로 데이터를 추가
- 장점: 해시 충돌이 많아도 저장 가능
- 단점: 충돌이 많아질 경우 검색 속도가 O(n)까지 떨어질 수 있음
2️⃣ 개방 주소법(Open Addressing)
- 충돌 발생 시 다른 빈 공간(버킷)에 데이터를 저장
- 비어 있는 인덱스를 찾는 과정을 조사(Probe) 라고 함
대표적인 조사 방법:
- 선형 조사(Linear Probing): 충돌 시 f(key) + 1, f(key) + 2, ... 순으로 빈 공간 탐색
- 문제점: 데이터가 특정 위치에 몰려 군집화(Clustering) 가 발생할 가능성이 있음군집화 현상은 오랜 순차 탐색이 필요해 성능 악화로 이어질 수 있음
이차 조사법
이차 조사법(Quadratic Probing)은 선형 조사법의 군집화 문제를 완화하기 위해, 해시 충돌 발생 시 충돌이 발생한 인덱스에서 제곱수 간격으로 떨어진 인덱스를 탐색하는 방법으로, 선형 조사법보다 효과적이지만 제곱수의 규칙성으로 인해 완벽한 해결이 어렵고, 특정 해시 테이블 크기에서는 빈 공간을 찾지 못할 가능성이 있음
3️⃣ 이중 해싱(Double Hashing): 보조 해시 함수를 사용해 새로운 위치 탐색
- 충돌 시 f(key) + g(key), f(key) + 2g(key), f(key) + 3g(key), ... 방식으로 탐색.
- 장점: 선형 조사보다 군집화 문제를 완화할 수 있음
📌 프로그래밍 언어별 해시 테이블 구현
- C++ → unordered_map
- Java → HashTable, HashMap
- Python → dictionary
- JavaScript → Map
- Go → map
추가 설명
키를 해시 함수에 적용하여 특정 위치에 데이터를 저장하는 자료구조
빠른 검색, 삽입, 삭제가 가능하고 일반적으로 O(1) 성능을 보장
버킷: 데이터를 저장하는 공간
해시 함수: 키를 특정한 인덱스로 변환하는 함수
로드 팩터: (저장된 요소 개수) / (버킷 개수), 해시 테이블이 얼마나 차 있는지
해시 충돌: 서로 다른 키가 동일한 해시 값을 가질 때 발생
해시 충돌 해결 방법
체이닝: 같은 인덱스에서 충돌이 발생하면 연결 리스트로 데이터를 저장
개방 주소법: 빈 공간을 찾아 데이터를 저장하는 방식
이중 해싱: 보조 해시 함수를 사용하여 충돌 시 새로운 위치를 탐색
참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 4-4)
