해시 테이블
키와 값의 대응으로 이루어진 테이블과 같은 형태의 자료구조
키는 해시 테이블에 대한 입력
값은 키를 통해 얻고자 하는 데이터
구조
키를 통해 얻고자 하는 데이터는 버킷에 저장됨
버킷은 여러 개가 존재하고 배열을 형성
로드 팩터
해시 테이블에 저장된 데이터 수를 버킷의 수로 나눈 값
해시 테이블이 현재 얼마나 가득 차 있는지에 대한 지표
로드 팩터가 클수록 해시 충돌 가능성이 높아져 해시 테이블의 성능이 떨어짐
해시 함수
해시 함수는 키를 인자로 활용해 버킷 배열의 인덱스를 반환
해시 테이블의 핵심은 해시 함수에 있음
임의의 길이를 지닌 데이터를 고정된 길이의 데이터(해시 값)로 변환하는 단방향 함수
단방향 함수이므로 데이터를 해시 값으로 변환할 수는 있어도 해시 값을 데이터로 도출하기 어려움
같은 데이터라 하더라도 적용된 해시 알고리즘이 다르면 도출되는 해시 값이 달라짐
데이터 1개만 달라도 해시 값이 크게 달라질 수 있어서 무작위 값을 만들거나 단방향 암호를 만들 때, 데이터의 무결성을 검증하기 위해 사용됨
- 송신할 때 데이터와 해시 값을 모두 전달하여 수신자가 받은 데이터로 해시 값을 계산하여 해시 값이 동일한지를 검사하여 전달된 데이터를 검증
성능
해시 테이블을 사용하는 이유는 빠른 검색 속도 때문
일반적인 상황에서 검색, 삽입, 삭제 연산의 시간 복잡도는 O(1)
버킷 때문에 상대적으로 많은 메모리 공간 소모
해시 충돌 문제 해결해야 함
해시 충돌
서로 다른 키가 같은 해시 값으로 대응되는 상황
해결 방법으로는 체이닝과 개방 주소법
체이닝
하나의 해시 테이블 인덱스에 서로 다른 키를 연결 리스트의 노드로 추가하는 방법
연결 리스트로 인해 검색, 삽입, 삭제가 느려져 해시의 빠른 속도 장점을 잃게 됨 : O(n)
개방 주소법
충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 저장하는 방법
조사 : 충돌이 발생했을 때 비어있는 다른 버킷의 인덱스를 찾는 과정
선형 조사법
충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 찾는 방법
해시 충돌이 발생하는 인근에 충돌이 발생한 여러 데이터가 몰리는 현상인 군집화가 발생하면 순차 탐색으로 성능이 떨어짐
이차 조사법
충돌이 발생한 인덱스에서 제곱수만큼 떨어진 인덱스를 찾는 방법
f(key) + 1^2, f(key) + 2^2 ...
군집화를 해결하는 근본적인 방법은 아님
이중 해싱
충돌이 발생했을 때 다른 해시 함수를 통해 얻은 해시 값만큼 떨어진 인덱스를 찾는 방법
f(key) + g(key), f(key) + 2g(key), ...
해시 함수를 통해 무작위로 인덱스가 생성되어 군집화를 많이 피할 수 있음