[자료구조]Hash(해시)

1. Hash(해시)

1) Hash Table(해시 테이블)

• Hash Table은 매우 빠른 평균 insert, delete, search 연산 제공
  • Ex) 딕셔너리(Dictionary)
• 딕셔너리는 key와 value가 1:1로 대응된다.(Key : Value, 일대일대응)
• 딕셔너리는 중괄호로 표기한다. {key:value}

D = {}
D['2019317'] = "신창수"

# 2019317 = key, 신창수 = value

2) Hash Table이 나온 이유?

• Data를 순차적으로 저장하는거 너무 비효율적이지 않아?
• 순차적으로 저장하면 원하는 위치(Index)에 정보를 삽입하는데 너무 오랜 시간이 걸린다.!!
• 일반적인 딕셔너리의 삽입과 삭제, 탐색 연산은 \(O(N)\)의 시간 복잡도를 가진다.

순차적 자료구조의 문제점

3) How to Map?

key값을 원하는 위치에 저장해야하는데, 그 과정을 도와주는 것이 바로 해시 함수(Hash function)이다.

위의 그림을 예로들면, key값에 해당하는 것이 학번(2019311, 2018513)이고, value가 이름(신창수, 홍길동)이다. 그림에서보면 첫번째 데이터는 1번 인덱스에 저장되었고, 두 번째 데이터는 3번 인덱스에 저장된 걸 볼 수 있다. 위의 그림의 해쉬 함수는 key값을 10으로 나눈 나머지에 해당한다.

• Ex)
  • 신창수:key = 2019311
    • 2019311 % 10 = 1(10으로 나눈 나머지)
  • 홍길동:key = 2018513
    • 2018513 % 10 = 3(10으로 나눈 나머지)
• 1st Point)
  • Hash function: f(key) = Index Number
• 2nd Point)
  • 이미 다른 Item이 저장되어 있을 때 충돌(Collision)이 발생한다.
  • 어디어 어떤 Rule에 의해 저장해? : Collision Resolution Method
• 3rd Point)
  • Hash
    1. Table: List
    2. Hash Function
    3. Collision Resolution Method

4) 해시 함수(Hash Fucntion)

해시 함수는 결국, 가지고 있는 데이터를 어떠한 인덱스에 넣어줄 지를 결정해주는 하나의 수단이다. 하지만 이 해시 함수를 잘 정하는 것이 중요하다. 왜냐하면 다른 데이터이지만, 해시 함수 를 통과한 후의 결과가 같으면, 같은 인덱스에 mapping이 일어나는 충돌이 일어날 수 있기 때문이다.

데이터와 해시 함수, 해시 테이블의 관계는 위와 같다.

Ex1) 나머지 연산 해시 함수

• \[f(k) = k % m\]
• \[f(k) = (k % p) % m\]

Ex2) Perfect Hash function

Ex3) Universial Hash function

Ex4) 다양한 해시 함수 예시

• 좋은 Hash Table의 조건!!
  1. Less Collision
  2. Fast Computation(But 둘은 Trade off)

2. 충돌 회피방법(Collision Resolution Method)

1) Open Addressing

• 주위에 빈칸을 찾아서 저장한다.
• 방법)
  • Linear Probing
  • Quadratic Probing
  • Double Hashing Probing

### 2) Close Addressing

• Chainging

(1) Linear Probing

• 충돌(collision)이 일어나면 바로 밑, 거기도 차있으면 그 밑, … 해서 채움
• \[k → k+1 → k+2 → k+3 → ...\]

(2) Quadratic Probing

• Linear Probing은 한 칸씩 이동하며 빈공간을 찾아 채워 넣는다.
• 반면 Quadratic Probing은 이름에서 알 수 있듯, 제곱항을 더해주는 것이다.
• \[k → k+1^2 → k+2^2 → k+3^3 → ...\]
• 제곱항이 더해지므로, remove함수가 복잡해진다.

(3) Double Hashing Probing

• Hash 두 개를 연결(Hash_1 + Hash_2)
• Hash_1의 해시 함수는 f(key)이고, Hash_2의 해시 함수는 g(key)이다.
• \[f(key) + g(key) → f(key) + 2g(key) → f(key) + 3g(key) → ...\]

(4) Chainging

• 하나의 Slot에 여러 개의 Item을 저장하면 되잖아!!
• 해시테이블의 각 슬롯이 한방향 연결리스트로 구현되어 있다.
• 이에따라 충돌 key의 평균 개수는 각 슬롯별 연결리스트의 평균 길이와 같다.

• 하나의 slot에 여러 개의 아이템을 저장하는 방식.
• 각 슬롯에 한방향 연결리스트를 만든다.(Doubly Linked List로도 구현 가능)
• set 함수가 항상 \(O(1)\) 시간 보장.
• search, remove 함수는 각 슬롯내의 노드 갯수만큼 \(O(n)\)간 (충돌 key의 평균 갯수)
• C-universal 해시 함수를 사용하면 set, search, remove가 \(O(1)\)
• C-universal 해시 함수를 사용하면 \(\frac{c}{n}\)
• C-universal Hash function을 쓰고 충분한 Load Factor를 확보하면 상수시간 내에 set, search, remove 연산을 수행 가능!!!

(5) Load Factor

• Load Factor = LF = \(\frac{n}{m}\)
• 해시 테이블의 크기가 작고, 아이템의 개수가 많아질수록 LF가 커진다. 그에 따라 충돌횟수가 증가한다.
• n = 아이템(자료)의 개수
• m = 해시 테이블의 크기

(6) Collision Ratio

• Collision Ratio =\(\frac{C}{n}\)
• n = 아이템(자료)의 개수
• C = 충돌횟수(Number of Collision)
• 비율이 작을수록 연산 시간이 작아진다.

3. Python 구현

1) 일반적인 Set, Search, Remove 성능

보통 이 세가지 연산은 Cluster size의 크기에 영향을 받는다.(Cluster size가 크면 성능 감소)

그리고 이 cluster size는 해시함수의 성능과 충돌회피방법에 따라 달라진다. 해시함수의 성능이 좋으면 당연히 클러스터의 크기가 줄어들고, 충돌회피방법(linear, quadratic, double 등)에 따라 성능이 달라진다.

open addressing의 경우, c-universal hash function을 사용하고 클러스터의 크기는 m>2n 이라는 조건 하에서 클러스터의 평균 사이즈가 O(1)이 된다. 이에 따라 set,search,remove 의 성능도 평균적으로 O(1)이 된다.

chaining의 경우, c-universal hash function을 사용하게 되면, O(1) 시간 내에 연산이 가능하다.

2) 구현 방법 1

파이썬의 dict는 해시 테이블로 관리되는 매우 효율적인 자료구조로 해시 테이블과 지원하는 연산이 같다!

파이썬의 dict는 c로 구현되어 있는데, (버전마다 다르지만) resize는 초기 해시테이블의 사이즈는 8이다.

8개 슬롯으로 시작해 전체 슬롯의 1/3은 항상 비어있도록 유지해야한다.

따라서 2/3 이상 슬롯이 차면 해시 테이블의 슬롯을 2배 늘려 resize한다. 이때, 한 번 resize할때마다 연산 시간이 늘어나게 된다. 하지만 resize하는 연산회수의 평균을 내보면 상수시간(O(1))의 연산을 한다.

이처럼 연산의 수행시간을 평균으로 계산하는 방법을 amorized time analysis라고 한다

3) Python 프로그래밍

키(Key): 인풋 데이터 ex) John Smith, Lisa Smith 값(value): 저장할 데이터 ex) 521-8976, 521-1234 해쉬 함수(Hash Function): ‘키’를 해시로 변경해주는 함수 해시(Hash): 인풋 데이터를 고정된 길이의 숫자열로 변환한 결과물

(1) 기본 구현

# Hash Table
class HashTable:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for a in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        self.hash_table[hash_address] = value
        
    def read(self, key):
        hash_address = self.getAddress(key)
        return self.hash_table[hash_address]
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            self.hash_table[hash_address] = 0
            return True
        else:
            return False


#Test Code
h_table = HashTable(8)
h_table.save('a', '1111')
h_table.save('b', '3333')
h_table.save('c', '5555')
h_table.save('d', '8888')  ## 'd'가 key로, 그 key에 해당하는 value값을 리턴한다.
print(h_table.hash_table)
print(h_table.read('d'))

h_table.delete('d')

print(h_table.hash_table)

[Output]

[0, '1111', '3333', '5555', '8888', 0, 0, 0]
8888
[0, '1111', '3333', '5555', 0, 0, 0, 0]

• 문제점: 해시 충돌(Hash Collision)
  • 해시 테이블에는 치명적인 문제점이 있다. 인풋 데이터를 해시 값으로 바꿔주는 과정에서
  • 두 데이터가 다른 문자열임에도 불구하고 같은 숫자로 변환되는 경우가 있다.
  • 이를 해시 충돌(Hash Collision)이라고 한다.
  • 해결법: 1)오픈 어드레싱, 2)클로즈 어드레싱

(2) Close Addressing 중 Chaining

만약 해시 값이 중복되는 경우, 먼저 저장된 데이터에 링크드 리스트를 이용하여 중복 해시 데이터를 연결한다.
파이썬에는 굳이 링크드 리스트를 안 쓰고 슬롯을 이중 리스트 구조로 활용해서 간단하게 구현할 수 있다.

# open hashing
class OpenHash:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for a in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            for a in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][a][0] == key:
                    self.hash_table[hash_address][a][1] = value
                    return
            self.hash_table[hash_address].append([key, value])
        else:
            self.hash_table[hash_address] = [[key, value]]
            
    def read(self, key):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            for a in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][a][0] == key:
                    return self.hash_table[hash_address][a][0]
            return False
        else:
            return False
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            for a in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][a][0] == key:
                    if len(self.hash_table[hash_address]) == 1:
                        self.hash_table[hash_address] = 0
                    else:
                        del self.hash_table[hash_address][a]
                    return
            return False
        else:
            return False
            
            
#Test Code
h_table = OpenHash(8)

h_table.save('aa', '1111')
h_table.read('aa')

data1 = 'aa'
data2 = 'ad'

print(ord(data1[0]))
print(ord(data2[0]))

h_table.save('ad', '2222')
print(h_table.hash_table)

h_table.read('aa')
h_table.read('ad')

h_table.delete('aa')
print(h_table.hash_table)
print(h_table.delete('Data'))
h_table.delete('ad')
print(h_table.hash_table)

[Output]

97
97
[0, [['aa', '1111'], ['ad', '2222']], 0, 0, 0, 0, 0, 0]
[0, [['ad', '2222']], 0, 0, 0, 0, 0, 0]
False
[0, 0, 0, 0, 0, 0, 0, 0]

(3) Open addressing 중 Linear Probing

구조는 간단하다. 위 이미지에서 John Smith와 Sandra Dee의 해시는 똑같이 873이다. 이때 먼저 들어온 John이 873이라는 해시를 먼저 키 값으로 취했고, 다음으로 들어온 Sandra는 바로 다음 값인 874를 키 값으로 가진다. 해시 중복이 발생하면 해당 해시 값부터 순차적으로 빈 공간을 찾기 시작한다. 가장 처 음 찾는 빈 공간에 키와 밸류를 저장한다. 저장 효율을 높이는 방법이다.

#close hashing
class CloseHash:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for a in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            for a in range(hash_address, len(self.hash_table)):
                if self.hash_table[a] == 0:
                    self.hash_table[a] = [key, value]
                    return
                elif self.hash_table[a][0] == key:
                    self.hash_table[a] = [key, value]
                    return
            return None
        else:
            self.hash_table[hash_address] = [key, value]
            
    def read(self, key):
        hash_address = self.getAddress(key)
        
        for a in range(hash_address, len(self.hash_table)):
            if self.hash_table[a][0] == key:
                return self.hash_table[a][1]
        return None
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        for a in range(hash_address, len(self.hash_table)):
            if self.hash_table[a] == 0:
                continue
            if self.hash_table[a][0] == key:
                self.hash_table[a] = 0
                return
        return False
        
        
#Test Code
h_table = CloseHash(8)

data1 = 'aa'
data2 = 'ad'
print(ord(data1[0]), ord(data2[0]))

h_table.save('aa', '3333')
h_table.save('ad', '9999')
print(h_table.hash_table)

h_table.read('ad')

h_table.delete('aa')
print(h_table.hash_table)

h_table.delete('ad')
print(h_table.hash_table)

[Output]

97 97
[0, ['aa', '3333'], ['ad', '9999'], 0, 0, 0, 0, 0]
[0, 0, ['ad', '9999'], 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]

Reference

신찬수 교수님 강의 자료
[python] 자료구조 - 해시 테이블(Hash Table)

DataStructure 카테고리 내 다른 글 보러가기