[자료구조4] 해시 구조

 

---

해쉬 구조

 

Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
• 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
• 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

 

알아둘 용어

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

 

자료 구조 해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

 

충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

1. Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

2. Linear Probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

 

참고: 해쉬 함수와 키 생성 함수

• 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
• 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

 

시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

 

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

 

검색에서 해쉬 테이블의 사용 예

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

 

 

---

 

파이썬으로 해시 테이블 구현하기

 

 

1. 해시테이블 생성 (list comprehension 문법: https://www.fun-coding.org/PL&OOP5-2.html)

# 슬롯을 모아놓은 해시 테이블
hash_table = list([0 for i in range(10)])
hash_table # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

2. 해시함수 생성 : key값을 입력받아 고정된 길이의 해시주소를 반환

# Division 법 (나누기를 통한 나머지 값을 사용하는 기법)

def hash_func(key): 
    return key % 5

 

3. 해시테이블 내 해시주소에 해당 데이터 저장

def storage_data(data, value):
    key = ord(data[0]) ## ord(): 문자의 ASCII(아스키)코드 리턴
    hash_address = hash_func(key)
    hash_table[hash_address] = value

 

4. 해시테이블 내에서 데이터 검색 (검색속도 매우 빠름)

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

 

 

 

 

---

충돌(Collision) 방지 알고리즘 -    1.  Chaining 기법 (Open Hashing 기법)

 

• 충돌이 일어나면, 링크드 리스트 자료 구조를 사용해서 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

 

1. 해시 테이블 생성

hash_table = list([0 for i in range(8)])

2. key 값 반환

def get_key(data):
    return hash(data)

3. 동일한 길이의 해시주소를 반환해주는 해시함수 생성

def hash_function(key):
    return key % 8

4. 충돌 발생시 linkedList 자료형으로 해시테이블 밖에 데이터를 저장하는 함수 생성

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # hash_address에 데이터가 들어가 있는 경우 
    if hash_table[hash_address] != 0:
        # 링크드리스트 순회하며
        for index in range(len(hash_table[hash_address])):
            # 기존에 해당 키가 존재하면 값 덮어쓰고
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        # 신규 키면 저장한다. 단,
        # key-value 형태로 저장해야 추후에 동일한 해시주소를 갖는 데이터 끼리 구분할 수 있다.
        hash_table[hash_address].append([index_key, value])
        
    # 주소에 비어있는 경우 바로 저장
    else:
        hash_table[hash_address] = [[index_key, value]]

5. 데이터 검색하는 함수 생성

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        # 링크드리스트 전체를 반복하며 값이 존재하는지 확인한다
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None

6. 확인

Dd와 Data는 동일한 key를 갖기에 hashAddress 또한 동일하다

이때 링크드 리스트를 이용해 key-value 형태로 save_data()한다.

또한 검색할 때 역시 링크드 리스트 내 key를 이용해 read_data()한다.

print (hash('Dave') % 8) # 0
print (hash('Dd') % 8) # 2
print (hash('Data') % 8) # 2

save_data('Dd', '1201023010')
save_data('Data', '3301023010')

read_data('Dd') 
# '1201023010'


hash_table
# [0,
#  0,
#  [[1341610532875195530, '1201023010'], [-9031202661634252870, '3301023010']],
#  0,
#  0,
#  0,
#  0,
#  0]

 

 

---

충돌(Collision) 방지 알고리즘 -    2. Linear Probing 기법 (Close Hashing 기법)

• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

 

4. 충돌 발생시 해시 테이블 내 빈공간을 찾아 데이터를 저장하는 함수 생성

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # hash_address에 데이터가 들어가 있는 경우 
    if hash_table[hash_address] != 0:
        # 비어있는 해시테이블 공간을 찾기 위해 순회하며
        for index in range(hash_address, len(hash_table)):
            # 빈공간 찾은 경우 저장
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            # 기존에 해당 키가 존재하면 값 덮어쓰고
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    # 주소에 비어있는 경우 바로 저장
    else:
        hash_table[hash_address] = [index_key, value]

 

5. 데이터 검색하는 함수 생성

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # 해시테이블 내 해당 주소에 저장된 데이터가 있다면
    if hash_table[hash_address] != 0:
        # 그 주소부터 테이블 끝까지 순회하며
        for index in range(hash_address, len(hash_table)):
            # 빈공간이 나온다면 이 해시테이블에는 해당 값이 없다는 의미
            if hash_table[index] == 0:
                return None
            # 해당 데이터 찾은 경우 value를 반환한다
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
            
    # 해시테이블 내 해당 주소에 아무것도 없는 경우 none 을 리턴
    else:
        return None