해시 테이블(해시 맵) 목차
[해시 테이블 Separate Chaining 자바 구현]
view that code
해시 테이블(해시 맵)
의미
키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조
해시 테이블의 핵심은 해시 함수
- 해시 함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수
- Key: mapping 전 원래데이터
- Hash value : mapping 후 데이터 값
(임의 크기 데이터) -> (고정 크기 값)
ABC(3글자) -> A1(2바이트)
1324BC(6글자) -> Cb(2바이트)
AF32B (5글자) -> D8(2바이트)
- ->: 이 역할이 해시 함수
특징
- 대부분의 연산의 시간 복잡도가 O(1)
데이터 양에 관계 없이 빠른 성능 기대 가능.
[성능 좋은 해시 함수들의 특징]
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
해싱 Hashing
해시 테이블을 인덱싱하기 위해 위처럼 해시 함수를 사용하는 것
- 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나
- 해싱은 최적의 검색이 필요한 분야에 사용됨
[쓰임]
최적의 검색이 필요한 분야
- 심볼 테이블(일반적으로 해시 테이블로 구현) 등의 자료구조를 구현하기에 적합
- 체크섬 Checksum
- 손실 압축
- 무작위화 함수 Randomization Function
- 암호 등 과 관련이 깊음
때로는 서로 혼용되기도 함
그러나 어느 정도는 개념이 겹치긴 하지만, 서로 용도와 요구사항이 다른 만큼 각각 다르게 설계되고 최적화됨
비둘기집 원리(서랍 원리)
= Pigeonhole Principle
충돌의 원리를 설명해주는 이론
n개 아이템을 m개 컨테이너에 넣을 때,
n > m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리
비둘기집 원리에 따라 6개의 공간이 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상은 충돌이 발생하게 된다.
- 좋은 해시 함수: 충돌을 최소화하여 단 2번의 충돌만 일어나게 함
- 좋지 않은 해시 함수: 심하면 9번을 모두 충돌. * 9개의 공간 중 1개밖에 사용하지 못할 수도 있음.
* 여러 번 충돌한다는 것은 그만큼 추가 연산을 필요로 하기 때문에 가급적 충돌은 최소화하는 것이 좋음
[비둘기 집 원리의 예]
45명중 같은 요일에 태어난 사람은 적어도 7명 있다.
(증명)
- 요일은 7일이 있으므로 45 = 6 * 7 + 3
- 적어도 어느 요일은 6명, 어느 요일은 7 이 가능하다.
- 결국 적어도 7명은 같은 요일이다.
[비둘기 집 원리의 확대]
유리수는 유한소수이거나 순환소수로 표현됨
- 1/2 = 0.5
- 1/7 =0.142857142……
무한소수일 때 순환소수가 되는 이유 - 1을 7로 나눌 때 유한소수가 아니므로 나머지 값은 1,2,3,4,5,6 이 나올 수 있다.
- 무한소수이므로 계속 계산을 하면 이 나머지 값이 다시 나옴
- 그러면 그 부분부터 순환지점이 되므로 순환소수임을 알 수 있음
즉, 비둘기집은 6개인데 비둘기는 그 이상이므로 한 집에 2마리 이상의 비둘기가 있게 되는 것이다.
생일 문제 Birthday Problem
충돌문제는 빈번하게 발생
-> 흔한 예가 생일 문제
- 생일의 가짓수는 365개(윤년 제외)
- 여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률을 얼핏 생각해보면 비둘기집 원리
이론) 366명 이상이 모여야 중복이 생김
실제) 다음 그림과 같이 23명만 모여도 50%를 넘고, 57명이 모이면 그때부터는 99%를 넘어선다.
[증명]
파이썬을 활용하면 간단한 실험을 통해 증명 가능
- 이러한 컴퓨터 실험을 통한 증명 방법은 1976년 4색 정리 6(지도에서 인접한 나라끼리 서로 다른 색을 칠하려면 4가지 색이면 충분하다는 정리)가 첫 번째 증명으로 가장 유명
- 이러한 기법들은 ‘해커를 위한 통계학 Statistics for Hackers ’이라 부름 -> 상당한 호응을 얻음.
그렇다면 정말로 23명만 있으면 생일이 같을 확률이 50%를 넘어설 수 있을까?
다음과 같이 계산 코드를 작성 직접 실험
import random
TRIALS = 100000 # 10만 번 실험
same_birthdays = 0 # 생일이 같은 실험의 수
# 10만 번 실험 진행
for _ in range(TRIALS):
birthdays = []
# 23명이 모였을 때, 생일이 같을 경우 same_birthdays +=1
for i in range(23):
birthday = random.randint(1, 365)
if birthday in birthdays:
same_birthdays += 1
break
birthdays.append(birthday)
# 전체 10만 번 실험 중 생일이 같은 실험의 확률
print(f'{same_birthdays / TRIALS * 100}%')
-------
50.708%
(실험 결과)
여기서는 23명이 모이는 경우를 각각 10만 번 실험
- 그 결과, 생일이 같을 확률은약 50.7%
- 정말로 23명만 모여도 생일이 같을 확률이 50%를 넘어섬
이처럼, 일반적인 상식(잘못된 상식)과는 달리, 충돌은 생각보다 쉽게 일어나므로 충돌을 최소화하는 일은 무엇보다 중요
로드 팩터 Load Factor
해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것
\[load factor = n/k\]일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소
사용
로드 팩터 비율에 따은 결정
- 해시 함수의 재작성 여부
- 해시 테이블의 크기를 조정 여부
효율성 측정
- 해시 함수가 키들을 잘 분산해 주는지를 말함
자바의 ‘해시맵 디폴트 로드 팩터’
자바 10에서는 이를 0.75로 정함
‘시간과 공간 비용의 적절한 절충안’이라고 얘기함
- 자바 10의 경우 0.75를 넘어설 경우(로드 팩터가 커질수록 성늘 감소) 동적 배열처럼 해시 테이블의 공간을 재할당한다.
충돌 Collision의 처리 방법
충돌 : 서로 다른 두개의 키가 동일한 해시값을 가질 때
아무리 좋은 해시 함수라도 그림 11-5와 같이 충돌은 발생
- 윤아와 서현이가 충돌
먼저, 입력값은 밑의 표와 같다면,
- 해시: 키를 해싱한 결과
- ‘윤아’와 ‘서 현’을 해싱한 결과는 충돌한다고 가정
개별 체이닝 Separate Chaining
- 해시 테이블의 기본 방식
- 충돌 발생 시, 연결 리스트로 연결 link
위의 입력값 표를 개별 체이닝 방식으로 구현
- 충돌이 발생한 ‘윤아’와 ‘서현’,
- ‘윤아’의 다음 아이템이 ‘서현’인 형태로 서로 연결 리스트로 연결되었다.
이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 필요
- 개별 체이닝 방식은 인기가 많음
원래 해시 테이블구조의 원형, 가장 전통적인 방식
흔히 해시 테이블이라고 하면 이 방식 지칭
[간단한 원리를 요약]
- 키의 해시 값을 계산한다.
- 해시 값을 이용해 배열의 인덱스를 구한다.
- 같은 인덱스가 있다면 연결 리스트로 연결한다.
- 잘 구현한 경우: 대부분의 탐색은 O(1)
- 최악의 경우: 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)
오픈 어드레싱 Open Addressing
- 충돌 발생 시, 테이블 공간 내 탐사 Probing를 통해 빈 공간을 찾아나서는 방식.
- 체이닝 방식
- 무한정 저장 가능
- 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장
- 오픈 어드레싱
- 전체 슬롯의 개수 이상은 저장 불가
- 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없음
- 체이닝 방식
오픈 어드레싱 방식
[1] 선형 탐사 Linear Probing
more learn abour Linear Probing
- 오픈 어드레싱 방식 중 가장 간단한 방식
- 충돌이 발생할 경우, 해당 위치부터 순차적으로 탐사를 하나씩 진행.
- 특정 위치가 선점되어 있으면, 바로 그 다음 위치를 확인.
- 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입
- 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입
(예시 적용)
1) ‘윤아’ 다음에 ‘서현’의 해시값이 동일한 2로 충돌이 발생했고,
2) 다음번 빈 위치를 탐색하며
3) 그다음 위치인 3에 ‘서현’이 삽입
(장점)
- 구현 방법이 간단
- 의외로 전체적인 성능이 좋은 편
(단점) - 해시 테이블에 저장되는 데이터들이
고르게 분포되지 않고 뭉치는 경향존재 - 클러스터링 Clustering : 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상
- 클러스터들이 점점 커지게 되면 인근 클러스터들과 서로 합쳐짐
- 해시 테이블의 특정 위치에는 데이터가 몰림
- 다른 위치에는 상대적으로 데이터가 거의 없는 상태가 될 수 있음.
- 이러한 클러스터링 현상은 탐사 시간을 오래 걸림
- 전체적으로 해싱 효율을 떨어 뜨리는 원인
[2] 제곱탐사
etc…
리해싱 Rehashing
오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입 불가.
기준이 되는 로드 팩터 비율을 넘어서게 되면,
- 1)그로스 팩터 Growth Factor의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성
- 2) 여기에 새롭게 복사
이는 연관 배열 Associative Array과 유사: 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사
언어별 해시 테이블 구현 방식
딕셔너리는 해시 테이블로 구현되어 있다.
- 면접 시 “해시 테이블로 구현된 파이썬의 자료형을 제시하라.”는 질문을 듣는다면 주저 없이 딕셔너리라고 답할 수 있어야 한다.
[파이썬]
오픈 어드레싱 방식으로 구현
CPython 구현에는 다음과 같은 주석이 적혀 있음
체이닝 시 `malloc`으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다.
(파이썬이 체이닝을 사용하지 않는 이유)
- 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요
- 추가 메모리 할당은 상대적으로 느린 작업이기 때문에 택하지 않았다고 기술
- 오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋음
(단점) - 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어남
- 체이닝과 달리 전체 슬롯의 전체 개수 이상, 즉 로드 팩터 1 이상은 저장 불가
- 빈 공간을 탐사하는 선형 탐사 방식은 공간이 찰수록 탐사에 점점 더 오랜 시간이 걸림
(최근 해결책) - 따라서 최근의 루비나 파이썬 같은 모던 Modern 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신,
- 로드 팩터를 작게 잡아 성능 저하 문제를 해결.
- 파이썬의 로드 팩터는 0.66으로 자바보다 작으며
- 루비는 0.5로 훨씬 더 작음
- 둘은 모두 오픈 어드레싱 방식을 택하고 있음
각 언어별 해시 테이블의 구현 방식을 모두 정리하면,
