대부분의 연산이 Amortized O(1), 데이터 양에 관계 없이 빠른 성능을 기대할 수 있음
해시
해시 함수 - 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용하는 함수
해싱 - 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 - 정보를 빠르게 저장하고 검색하기 위한 중요한 기법 - 최적의 검색이 필요한 분야에서 사용 - 심볼 테이블 등 자료구조를 구현 - 체크섬, 손실 압축, 무작위화 함수, 암호 등에 관련됨
성능 좋은 해시 함수의 특징
충돌의 최소화
쉽고 빠른 연산
값의 균일 분포
키의 모든 정보 이용
높은 사용 효율
해시 함수의 충돌 가능성
생일 문제 - 생일은 일반적으로 365일 중 하루 - 생각보다 적은 사람이 모여도 생일이 같은 사람을 쉽게 찾음 (즉, 충돌이 쉽게 일어남) - 366명이 모여야 한 쌍이 생길 것 같지만, 23명만 모여도 50%, 57명이 모여민 99%라고 함
비둘기집 원리 - n개 아이템, m개 컨테이너가 있을 때, n>m이면 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어있음 - 10개 아이템, 9개의 컨테이너 일 때, 좋은 해시함수는 1번의 충돌, 최악의 경우 9번 모두 충돌
해시 함수의 충돌 측정
로드 팩터 - 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것 load factor = n / k - 로드 팩터로 정해지는 것 1) 해시 함수 재작성 2) 해시 테이블의 크기 조정 - 로드 팩터가 증가할수록 해시 테이블 성능이 감소
해시 함수 - 일반적으로 나눗셈 방식 사용 - 입력값 x를 해시 테이블의 크기 m으로 나눈 나머지 h(x) = x mod m - 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋음 - 나눗셈 방식은 단순하면서, 이미 키 세트가 충분히 랜덤한 상태이고, 큰 소수에 의해 순환 구조가 될 확률이 낮아 많이 사용 - 31이 메르센 소수로 많이 사용되는 듯
해시 함수의 충돌 방지 기법
개별 체이닝 (Separate Chaining) - 충돌 발생시 연결 리스트로 연결 - 가장 전통적인 방식 - 대부분 탐색은 O(1)이지만, 모든 해시 충돌의 발생을 가정하면 O(n) - 자바8에서는 데이터 개수가 많아지면 레드-블랙 트리 병행
오픈 어드레싱 (Open Addressing) - 충돌 발생시 탐사(Probing)를 통해 빈 공간을 찾는 방식 - 전체 슬롯 개수 이상은 저장할 수 없음 - 모든 원소가 반드시 자신의 해시값과 일치하는 주소를 갖는다는 보장이 없음
오픈 어드레싱의 특징
선형 탐사 (Linear Probing) - 해싱 위치가 선점되어있으면 바로 그 다음 위치부터 순차적으로 하나씩 탐사하는 기법 - 클러스터링 : 해시 테이블에 데이터들이 고르게 분포되지 않고 뭉치는 문제 - 클러스터링은 탐사 시간이 오래걸리고, 전체 해싱 효율을 떨어뜨림
리해싱 (Rehashing) - 기준 로드 팩터 비율을 넘으면, 그로스 팩터(Growth Factor) 비율에 따라 더 큰 크기의 버킷을 새로 생성하여 이곳으로 복사하는 것
파이썬의 해시 테이블은 오픈 어드레싱 - 파이썬의 딕셔너리는 해시 테이블로 구현된 자료형 - 추가 메모리 할당의 오버헤드로 오픈 어드레싱 기법 사용 - 일반적으로 오픈 어드레싱이 체이닝에 비해 성능이 좋다가, 슬롯이 80%이상 차면 지수적으로 급격히 성능이 저하됨 - 따라서 오픈 어드레싱을 사용하면서 로드 팩터를 낮게 잡아 성능 저하 문제를 해결함
