-
해싱함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길의의 데이터로 매핑하는 함수.
-
매핑 전 데이터 값을 Key, 매핑 후 데이터 값을 해시값(Hash value), 매핑하는 과정을 Hashing이라고 한다.
-
해시함수는 언제나 동일한 해시값을 리턴
-
해당 index만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있다.
-
index는 계산이 간단한 함수(상수시간)로 작동한다.
—> 데이터 엑세스(삽입,삭제,탐색)시 **O(1)**을 지향한다.
-
해시함수를 사용하며 키를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터를 키와 함께 저장하는 자료구조
-
데이터가 저장 되는 곳을 bucket 또는 slot 이라고한다
-
장점
- 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
- ex) 하드디스크나 클라우드에 존재하는 무한에 가까운 key들을 유한한 개수의 hash value로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다.
-
Direct-address table : 키의 개수와 동일한 크기의 버킷을 가진 해시테이블
- 해시 충돌 문제가 발생하지 않는다.
- 전체 키에 대한 공간을 만들어 놓는다
- 실제 사용하는 키보다 전체 키가 훨씬 많은 경우 메모리 효율성이 떨어진다.
-
해시함수는 해쉬값의 개수보다 대게 많은 키 값을 해쉬값으로 변환(many-to-one)하기 때문에,
-
==해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값==을 나타내는 **해시충돌(collision)**이 발생하게 된다.
-
현재까지 개발된 거의 모든 해싱함수는 해시충돌을 일으킨다.
-
해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는것이 중요하다.
- 하나의 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다.
- 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)
- 메모리 문제를 야기할 수 있다.
-
시간복잡도
hashtable size : m , keys : n
버킷 하나당 n/m = x개의 데이터 이라 가정.
-
탐색
매핑 O(1) + 버킷요소 x 탐색 O(x) => O(1+x)
-
삽입
매핑 O(1) + 추가 O(1) => O(1)
-
삭제
매핑 O(1) + 탐색 O(x) + 삭제 O(1) => O(1+x)
-
- 한 버킷당 들어갈 수 있는 엔트리가 하나쁜인 해시테이블
- 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용
- 메모리 문제는 발생하지 않지만, 해시충돌이 생길 수 있다.
- 특정 해시값에 키가 몰리게 되면 효율성이 크게 떨어진다.
ex) 해시함수가 '키 값을 8로 나눈 나머지' 10, 18, 26 순으로 해시테이블에 삽입해보자.
세 숫자 중 첫번째 값 10 을 제외한 18, 26인 원래 버킷(2) 말고 각각 다음 (3) , (4)에 저장된다.
[2] 10
[3] 18
[4] 26
—선형탐사
-
open address의 효율성 감소 문제를 해결한다.
-
삽입,삭제,탐색을 수행하기 위해 해시테이블 내 새로운 주소를 찾는 과정
-
선형탐사(Linear probing)
- 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼있으면 해시값에서 고정폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
- 여기에 데이터가 있으면 또 고정폭 만큼 옮긴다.
- 특정 해시값 주면 버킷이 모두 채워져 있는 primary clustering 문제에 최약하다
-
제곱탐사(Quadratic probing)
- 이동 폭이 제곱수로 늘어난다.
- 예를들어, 데이터 엑세스할때 충돌이 일어나면 1^2 칸을 옮긴다. 여기서 또 충돌이 일어나면 2^2 만큼, 그다음엔 3^2 만큼 옮긴다.
- 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약하다.
-
이중 해싱(double hashing)
- 탐사할 해시값의 규칙성을 없애서 clustering을 방지한다.
- 2개의 해시함수를 준비해 하나는 최초의 해시값을 얻을 때, 하나는 해시충돌이 일어났을때 탐사 이동폭을 얻기 위해 사용.
