해싱

hashing

산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾는 계산 검색 방식

Hash Function

키 값을 원소 위치로 변환하는 함수

Hash Table

해시 함수에 의해 계산된 주소 위치에 항목을 저장한 표

• 해싱 검색은 키 값에 대하여 해시 함수를 계산하여 주소를 구하고 구한 주소에 해당하는 해시 테이블로 바로 이동하여 찾는 항목이 있으면 검색 성공이 되고 없으면 검색 실패가 된다.
• 해시 테이블은 버킷 n개와 슬롯m개로 구성한다. 해시함수에 의해 계산된 주소가 버킷 주소가 된다. 이 때 해시 함수는 0과 n-1사이의 버킷 주소만 만들어야 한다.
• 해시 함수로 알아낸 버킷에 키 값이 저장된 슬롯이 여러 개 있는 경우 순차검색을 해 슬롯을 검색한다.

Synonym(동거자)

다른 키 값을 가지지만 해시 함수에 의해 같은 버킷에 저장된 키 값, 효율의 이유로

collision(충돌)

키 값이 다른데 해시 함수에 의해 주어진 버킷 주소가 같은 경우

overflow

포화 버킷 상태에서 또 그 버킷을 지정 받은 키 값이 있어 충돌이 발생하면 오버플로우가 된다.

키 값 밀도

실제 사용중인 키 값의 개수/ 사용 가능한 키 값의 개수

적재 밀도

실제 사용중인 키 값의 개수/ 해시 테이블에 저장 가능한 전체 키 값의 개수(버킷 * 슬롯)

• 해시 함수는 계산이 쉬워야한다. 비교검색을 사용하여 키 값의 비교 연산을 수행하는 시간보다 해싱 검색이 빨라야 의미가 있다.
• 해시 함수는 충돌이 적어야 한다. 비어 있는 버킷이 많다 하더라도 어떤 버킷은 오버플로가 발생할 수 있는 상태가 된다.
• 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

중간 제곱 함수

키 값을 제곱한 결과에 중간에 있는 적당한 비트를 주소로 사용한다. 제곱 결과에서 주소로 사용하는 비트 수는 해시 테이블의 버킷 개수에 따라 결정된다.

제산(Division)함수

나머지 연산자 mod를 사용한 방법으로 키 값을 해시 테이블의 버킷 크기로 나눈 나머지를 주소로 사용. 적당한 크기의 소수로 나눈다

승산(Multiplication)함수

곱하기 연산을 사용한 방법. 키 값 k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부부만을 테이블 크기와 곱하여 그 정수 값을 주소로 사용

접지 함수

키와 비트 수가 해시 테이블 인덱스의 비트 수 보다 클 때 사용한다. 키 값을 해시테이블 인덱스의 비트 수와 같은 크기로 분할한 후 분할된 부분을 모두 더해 해시 주소를 만든다.
12312312에 대해서

• 이동 접지 함수: 123+123+12=258
• 경계 접지 함수: 123+321+12=456

숫자 분석 함수

키 값을 이루는 각 자릿수의 분포를 분석하여 해시 주소로 사용한다. 각 키 값을 적절히 선택한 진수로 변환한 후에 각 자릿수의 분포를 분석하여 가장 편중된 분산을 가진 자릿수는 생략하고 가장 고르게 분포된 자릿수부터 해시 테이블 주소의 자릿수만큼 차례로 뽑아서 만든 수를 역순으로 바꿔 주소로 사용한다.

진법 변환 함수

키 값이 10진수가 아닌 다른 진수일 때 10진수로 변환하고, 해시 테이블 주소로 필요한 자릿수만큼만 하위 자리의 수를 사용한다.

비트 추출 함수

해시 테이블의 크기가 2^k일 때, 키 값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용한다. 충돌 발생 가능성이 많으므로 테이블 일부에 주소가 편중되지 않도록 키 값의 비트를 미리 분석하여 사용해야 한다.

해싱에서 오버플로를 처리하는 방법

1. open hashing(chainging): 주소 밖에 새로운 공간을 할당하여 문제 해결

2. closed hashing(open addressing): 처음에 주어진 테이블 내에서만 접근

• 체이닝: 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법. 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해 연결 리스트를 사용한다. 각 버킷에 대한 헤드 노드는 1차원 배열이고, 슬롯은 헤드 노드에 연결리스트 형태로 이어진다. 버킷 내에서는 원하는 슬롯을 검색하려면 버킷의 연결 리스트를 선형 검색한다.

• 선형 개방 주소법: 선형 탐색(linear probing)이라고도 한다. 선형개방 주소법에서 해시 함수로 구한 버킷에 빈 슬롯이 없어서 오버 플로가 발생하면 그 다음 버킷에 빈 슬롯이 있는지 조사한다. 있으면 저장 없으면 그 다음(정해진 상수 만큼 떨어진) 버킷 조사, 특정 위치에 군집화되는 문제가 발생할 수 있다.

• quadratic probing : linear probing과 비슷 하지만 정해진 상수의 제곱만큼 떨어진 버킷 조사

• double hashing: 하나는 해시 테이블에 접근할 때, 하나는 충돌시 이동할 때 사용

• rehasing: 부하율이 1에서 너무 멀어지면 해시함수를 수정하여 부하율이 1에 가까운 값이 되도록 만드는 것

  부하율(load factor)= 전체 키 개수/ 해시 테이블 크기

cuckoo hashing

• 크기가 같은 두 개의 해시 테이블을 사용(더 많이도 가능할 듯)
• 각 테이블은 다른 해시 함수 적용
• 두 테이블 중 한 곳에 원소 존재
• 원소가 다른 위치로 이동 가능
• 1 원소를 삽입 시 테이블 확인 후 다른 원소 2가 있다면 2를 두 번째 해시 테입르로 옮김, 반복
• 사이클이 생기면 리해싱
• 부하율이 0.5일 경우 높은 성능 보장

bloom filter

• 결정적 솔루션 대신 부정확한 결과
• 해시 테이블에 비해 높은 공간 효율
• 여러 해시 함수 사용(3개 이상)
• 실제 값 대신 값의 존재를 나타내는 부울 타입 사용
• 모든 해시 함수 값을 계산하고 대응되는 위치의 비트 값이 1인지 검사
  • 모든 비트가 1이면 true, 아니면 false
• 결정적이지 않은 이유는 대응되는 비트가 다른 원소에 의해 1이 될 수 있기 때문이다(false positive)