[TIL 210612] 자료구조 #6

송진수·2021년 6월 12일

해시테이블(Hash Table)

파이썬의 dictionary 자료형처럼 (key, value)로 데이터를 저장하는 자료구조

자료가 어디에 저장될지(index)는 key와 key를 입력값으로 받아 연산하는 hash function에 의해 결정된다.

예를 들어 10칸짜리 테이블이 있을 때, 데이터를 저장하려면 key % 10 (10으로 나눈 나머지)에 따라 결정하는 방법이 있을 것이다. 이 index = key % 10이 바로 hash function이다.

또, 인덱스 지정이 충돌하는 경우(ex: key=4인 데이터가 입력되어 있을 때 key=14인 데이터를 입력하는 경우)가 발생(Collision)할 수 있는데, 이를 방지하기 위한 Collision Resolution Method가 있다.

즉, 해시테이블은

Table(list)
Hash function
Collision Resolution Method

로 구성되어 있다.

Hash Function

HashFunc은 key를 index로 mapping하는 과정에서 충돌없이 1:1 매치(perfect hashfunc)되게끔 하는 것이 이상적이겠지만, 현실적으로 매우 어렵다.

차선책은 Universal hashfunc으로,

Pr(f(x)==f(y)) = 1/m (m = table의 크기)

즉, 충돌할 확률이 테이블의 크기에 반비례하는 HashFunc이다.

이것도 설계하기 어려워 Pr(f(x)==f(y)) = c/m, 일정한 상수 c를 가진 c-universal hashfunc을 사용한다고 한다.

HashFunc의 종류

인덱스가 숫자형일 때 : division, multiplication, mid-square, extraction 등
인덱스가 스트링일 때 : additive(=sum(key[i]), rotating...

좋은 HashFunc의 조건

less collision
fast computation

일반적으로 두 성질은 trade-off 관계가 있다.

Collision Resolution Method

CRM의 종류

Open addressing(충돌이 발생할 경우, 주변 빈 인덱스에 대신 저장시키는 방법)
1) Linear probing : 인덱스를 한칸씩 옮기면서 빈 인덱스를 찾는 방법
2) Quadratic probing : k = f(key) 일 때, k+1^2, k+2^2, k+3^2 같은 방식으로 인덱스를 건너뛰는 방법
3) Double hashing : HashFunc을 2개 사용하여 인덱스를 2개 만드는 방법
Chaining : 한 인덱스에 연결리스트를 만들어 관리하는 방법

Cluster

테이블 내에서 key가 특정한 부분에 쏠리는 현상

예시로 든 해시테이블이 linear probing을 따를 경우, key=4, 14, 24, 34...인 데이터가 지속적으로 입력되면 충돌이 계속 발생하여 index에 해당하는 슬롯(4,5,6,7...)에 key가 쏠린다.

클러스터가 커질수록, 개수가 많아질수록 collision 발생률은 증가, 즉 연산시간이 증가하므로, 클러스터 발생을 줄일 수 있는 HashFunc이 필요하다.

성능평가

So why use hash table?

해시테이블은 매우 빠른 '평균' 삽입/삭제/탐색 연산을 제공하기 때문이다.

해시테이블의 성능은 [Load Factor = n / m] (n = 테이블에 저장된 item 개수, m = 테이블 사이즈)와 [충돌비율 = collision 횟수 / n] 로 수행시간과 성능평가가 가능하다.

일반적으로, Load Factor가 1에 가까울수록(Table Full) 클러스터는 커지거나 많아지고, 각각의 슬롯을 비교하는 횟수가 늘어나기 때문에 수행시간은 길어진다.

그러나, m >= 2n, 즉 테이블이 최소 50% 이상 빈 슬롯을 유지할 때, 클러스터의 평균 사이즈를 연산하는데 O(1) (상수시간)이 가능하다고 한다.

이 경우 삽입/삭제/탐색도 평균 O(1)의 시간이 걸리므로,

빅데이터 혹은 중요한 데이터를 다루거나, 빠른 연산이 필요한 기업들은 hash table을 사용한다.

Python 코드

class HashTable:
    def __init__(self,size):
        self.size = size
        self.hashTable = [0 for i in range(self.size)]
    
    def hashFunction(self,key): # 키값을 해시테이블의 크기로 나눈 division h.f. 사용
        return key % self.size 
    
    # Open Addressing - Linear probing 에서의 삽입/탐색/삭제 연산

    # 가장 기본적으로, 키값을 인덱스로 변환하여 슬롯을 찾고, 슬롯에 key값이 없으면 key가 삽입될 슬롯 return 혹은
    # Linear probing으로 슬롯 한칸씩 내려가면서 key값이 있으면 그 슬롯을 return  
    def findSlot(self,key): # 키값을 h.f.에 입력해 해시테이블에 저장될 인덱스를 출력하는 함수
        i = self.hashFunction(key)
        start = i
        while (self.hashTable[i] != 0) and (self.hashTable[i][0] != key):
            i = (i+1) % self.size # 한 슬롯씩 내려가다 끝 슬롯 다음이 첫 슬롯이 될 수 있게 나머지 연산을 돌림 
            if i == start : # 테이블을 돌아 원래 슬롯에 돌아왔다는 것은, 테이블이 꽉 찼다는 뜻
                i = None 
                return i
        return i
    
    def set(self,key,value=None):
        i = self.findSlot(key)
        if i == None:
            print("Hash Table is full! Expand table size!")
            return None
        if self.hashTable[i] != 0: # key가 들어간 슬롯이 이미 있어 value값만 업데이트될 때,
            self.hashTable[i] = (key,value)
        else:                      # 아예 빈 슬롯에 key와 value를 추가하는 케이스
            self.hashTable[i] = (key,value)
            return key

    def search(self,key):
        i = self.findSlot(key)
        if i == None:
            print("Hash Table is full! Could not find key!")
            return None
        if self.hashTable[i] == 0:
            print("Could not find key!")
            return None
        else:
            return self.hashTable[i][1] # key값이 들어있는 슬롯의 데이터 읽기

    # collision 발생해서 슬롯이 밀렸던 경우를 고려해서 나머지 슬롯에 있는 값들을 이동시켜야 한다
    def remove(self,key):
        i = self.findSlot(key)
        if self.hashTable[i] == 0 : return None
        j = i
        while True: 
            self.hashTable[i] = 0 # 슬롯 내 데이터를 삭제
            while True: # 밀려서 set된 슬롯들을 찾고, 이동시키는 과정
                j = (j+1) % self.size
                if self.hashTable[j] == 0: # 삭제한 i 슬롯 다음 슬롯이 비었다면, 적어도 i 슬롯의 데이터로 인해 collision이 발생하지 않았다는 뜻. 옮길 게 없다
                    return print('Remove Complete!')
                k = self.hashFunction(self.hashTable[j][0]) # 테이블이 비었다면 j에 있는 데이터가 원래 들어갈 슬롯은 k
                if (k<=i<=j) or (j<k<i) or (i<j<k) : # k 슬롯에 갔어야할 데이터가 밀려 i를 넘어 j 슬롯에 들어간 모든 경우
                    self.hashTable[i] = self.hashTable[j] # 빈 슬롯이 된 i 슬롯에 j 슬롯 데이터를 이동
                    break
            i = j # i를 j로 바꿔 j 슬롯을 비우고 다음 슬롯을 확인하는 while 반복



hT = HashTable(10)   # 10칸짜리 빈 테이블 생성(0만 들어가있으면 빈 슬롯으로 간주)
hT.set(3,'aaaa')     # hashFunction(3) = 3 -> HashTable[3]에 (3,'aaaa') 저장
hT.set(5,'bbbb')
hT.set(13,'cccc')    # HashTable[3]에 입력값이 있으므로 findSlot함수에 의해 그 다음 비어있는 칸 [4]에 저장됨
print(hT.hashTable)  # [0, 0, 0, (3, 'aaaa'), (13, 'cccc'), (5, 'bbbb'), 0, 0, 0, 0]
print(hT.search(5))  # bbbb
hT.remove(3)	     # Remove Complete!
print(hT.hashTable)  # [0, 0, 0, (13, 'cccc'), 0, (5, 'bbbb'), 0, 0, 0, 0]
		     # (3,'aaaa') 가 삭제된 [3] 슬롯에 (13,'cccc') 데이터를 옮김