[자료 구조] 해시테이블(Hash Table)

관리 메뉴

suyeonme

프로그래밍👩🏻‍💻/자료구조

suyeonme 2022. 7. 10. 20:23

데이터를 저장할 위치(index)를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행한다.

키값을 해시값(hash value)로 변환하는 과정을 해시 함수라고 한다.

충돌을 피하려면 해시 함수는 해시 테이블 크기 이하의 정수를 한쪽으로 치우치치 않도록 고르게 만들어야한다. 해시 테이블 크기는 소수(prime number)가 좋다고 알려져있다.

해시 테이블을 만드는데 사용되는 대표적인 해시 함수 목록이다. 키값이 정수(integer)인지에 따라서 해시 함수가 달라진다.

Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터로 해시를 생성하는 방법
Multiplication Method: 숫자로 된 key값 K, 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 h(k)=(kAmod1) × m과 같은 계산을 수행하여 해시를 생성하는 방법
Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택하여 해시를 생성하는 방법
Division Method: 나눗셈을 이용하여 입력값을 테이블의 크기(배열의 크기)로 나누어서(hash = 입력값 % 테이블의 크기)나온 나머지로 해시를 생성하는 방법
Bitwise Operation: 실수 키값에 대해 비트 연산(Bitwise Operation)을 하는 방법

해시값(hash value)을 인덱스로 하여 원래의 키값을 저장한 배열이다. 해시 테이블의 각 요소를 버킷(bucket)이라고 한다.

키값과 해시값의 대응 관계는 보통 n:1이다. 따라서 저장할 버킷이 중복되는 현상을 충돌이라고한다.

예를 들어,

충돌 대처법으로 아래 2가지 방법이 있다.

1. 체인법(chaining), 오픈 해시법이라고도 한다.
2. 오픈 주소법(open addressing)

해시값이 같은 데이터를 사슬(chain)모양의 연결 리스트(linked list)로 연결하는 방법

충돌이 발생했을 때 재해시(rehasing)을 수행하여 비어있는 버킷을 찾아내는 방법이다. 오픈 주소법은 빈 버킷을 만날 때까지 재해시를 여러번 반복하므로 선형 탐사법(Linear Probing)이라고도 한다.

재해시할 때 해시 메서드는 자유롭게 결정할 수 있다. 예를 들어, 충돌이 발생한 경우 재해시 값으로 키값에 1을 더한 값을 배열의 크기로 나눈 나머지(hash = 입력값 + 1 % 테이블의 크기)를 사용할 수 있다.

크기가 13인 해시 테이블에서 인덱스가 5인 값을 삭제한다고 가정해보자.

인덱스가 5인 버킷을 그냥 비워두면 해시값이 같은 18을 검색할 때 '해시값이 5인 데이터는 존재하지 않는다'라고 생각하여 검색에 실패할 것이다. 따라서 버킷에 다음 속성중 하나를 부여한다.

1. 데이터 저장
2. 비어있음 속성값: 해시값이 같은 데이터가 존재하지 않음
3. 삭제 마침 속성값: 해시값이 같은 데이터가 다른 버킷에 저장되어 있음