[Data Structure] Hash Table

Hash Table에 대한 공부 기록이다.

Hash Table

입력값에 대해 hash 함수를 거치고,
결과값 즉, key값에 의해 위치가 결정된다.

정렬이 아닌 결정된 위치에 데이터를 보관하기 때문에 빠른 삽입, 검색, 삭제 작업을 제공한다.

예시

해시함수 h(x)=x%13이라고 하면,

입력값에 대해 위의 연산을 진행하고 그 결과값을 key값으로 해당 Table에 저장하는 것.

적재율

입력값에 대해서 해시 함수의 연산 결과가 같으면 어떨까?

Hash Table에 이미 값이 있을 때 충돌이발생한다.

 

Hash Table에 원소가 차 있는 비율을 적재율이라고 한다.

적재율은 Hash Table의 크기가 m이고, 저장된 키의 총 수가 n일 때 n/m으로 정의된다.

 

적재율이 높아지면 충돌 확률이 높아지고, 해시 테이블의 성능이 저하된다.

객체 구조

Hash Table의 객체 구조는 다음과 같다.

1. __table[] : Hash Table로 사용되는 배열
2. __numItems : 원소 개수
3. search(x) : 원소 x를 검색한다.
4. insert(x) : 원소 x를 삽입한다.
5. delete(x) : 원소 x를 삭제한다.
6. isEmpty(x) : Hash Table이 빈 상태인지 알려준다.
7. clear(x) : Hash Table을 비운다.

Hash Function

Hash 함수는 위에서 언급한 대로 원소의 주소를 결정한다.

Hash 함수에서 핵심은 입력값을 고루 분산해서 충돌의 발생을 최소화해야 한다는 것이다.

Division Method

나누기 방법에 의한 함수이다.

h(x)=x%m

m은 Hash Table의 크기이며, 소수를 권장한다.

 

Multiplication Method

곱하기 방법에 의한 함수이다.

h(x)=(x*A mod1)*m의 정수부

A : (0,1) 범위의 상수

충돌 해결

위에서 언급한 대로 충돌은 주소에 이미 다른 값이 위치한 상황이다.
충돌을 최소화해야겠지만, 이에 대한 해결책도 고안해야 한다.

Chaining

충돌이 일어난 원소들을 하나씩 연결 리스트로 관리

테이블의 각 원소는 연결 리스트 하나씩을 링크한다.

import LinkedListBasic
class ChainedHashTable:
    def __init__(self,n):
        self.__table=[LinkedListBasic() for _ in range(n)]
        self.__numItems=0
    def __hash(self,x):
        return x%len(self.__table)
    def insert(self,x):
        slot=self.__hash(x)
        self.__table[slot].insert(0,x)
        self.__numItems+=1
    def search(self,x):
        slot=self.__hash(x)
        if self.__table[slot].isEmpty():
            return None
        else:
            head=prev=self.__table[slot].getNode(-1)
            curr=prev.next
            while curr!=head:
                if curr.item==x:
                    return curr
                else:
                    prev=curr
                    curr=curr.next
            return None

위 코드는 LinkedList를 import 하는데

LinkedList는 일반 연결 리스트이며, 위 코드에서는 비어있는지 확인하는 isEmpty 메서드를 필요로 한다.

 

개방 주소 방법

체이닝 방법과는 다르게 충돌이 일어나면,

다른 주소에 값을 저장하는 방법을 말한다.

 

다른 주소를 어떻게 효율적으로 찾을 수 있을까?

선형 검색

(h(x)+i)%m

충돌이 일어난 횟수만큼을 더해서 저장하는 방법이다.

 

이차원 검색

(h(x)+i**2)%m

충돌이 일어난 횟수의 제곱만큼을 더해서 저장하는 방법이다.

 

더블 해싱

(h(x)+i*f(x))%m

다른 Hash 함수를 한 번 더 사용해서 값을 저장하는 방법이다.

---

마치며

잘못된 정보에 대한 피드백은 환영입니다.

감사합니다.