Data Structure (3) Hash Table (해시 테이블)

📌Hash 구조

• Hash Table: key에 data(value)를 저장하는 데이터 구조
• ex) Python의 Dictionary : key와 value를 가지고 있는 데이터 타입으로, key값을 통해 value를 바로 꺼낼 수 있음 (Python에서는 hash구현 없이 바로 dictionary 사용하면 됨)
• 보통 미리 hash table의 크기만큼 배열 생성 후 사용 (공간과 탐색 시간을 맞바꾸는 기법)

 

📌용어

• hash: random 값을 고정 길이로 변환하는 것 (단방향 암호화 기법으로, 해시 알고리즘을 이용하여 고정된 길이의 암호화된 문자열로 변환)
• hash table:
• hashing function: key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수, 즉 임이이 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 (key를 입력으로 받아 hash table의 특정 주소값(hash value / hash address)를 return)
• key: 매핑 전 원래 데이터 값
• hash value / hash address: 매핑 후 데이터 값(key를 hashing function으로 연산하여 나온 값), hash value로 hash table에서 해당 key에 대한 데이터 위치를 일관성있게 검색 가능
• slot: 한 개의 데이터를 저장할 수 있는 공간

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

매핑 전 원래 데이터의 값: key, 매핑 후 데이터의 값을 hash value, 매핑하는 과정 hashing

📌Hash Table의 장단점과 주요 용도

• 장점
  • 검색 속도가 엄청 빠르다. (데이터 저장/읽기 속도가 엄청 빠르다!)
    (array에서 data를 찾으려면 앞에서부터 쭈우우-욱 찾아야 하지만 hash table에서는 data를 읽으면 그 data에 대응하는 key를 자동으로 추출하고 그 key를 hash function에 넣어 데이터 저장 위치를 바로 반환받아 곧바로 탐색이 가능하다.)
  • 중복 처리가 쉽다.
• 단점
  • 저장공간이 내가 저장하고자 하는 data 자체의 size보다 큰 것이 일반적이다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다. (-> 충돌 해결을 위한 가장 간단한 방법은 단순히 저장공간을 늘리는 것이다.)
• 주요 용도
  • 검색이 필요한 경우
  • 저장, 삭제, 읽기가 필요한 경우
  • cash 구현이 필요한 경우 (쉬운 중복 처리)

 

📌Hash 구현

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8 #8로 나눈 나머지를 hash value로

def save_data(data, value):
    hash_address = hash_function(get_key(data)) #key값을 hash function에 넣어 hash value(hash address)값 만들기
    hash_table[hash_address] = value

def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

• hash table size만큼의 list를 미리 생성해야 함
• get_key(): python 내장 함수 hash()를 이용해 data의 고유 key값을 리턴 받는다
• hash_function(): 나머지 값을 이용한 초간단 hash function
  (hash function 고안 기법은 다양하지만 가장 간단한 방식은 division법)
• save_data(): data와 value를 입력으로 받고, 해당 data에 대한 key를 hashing function으로 hash 주소를 특정하고 거기에 value를 저장하는 함수
• read_data(): data를 입력으로 받고, 특정 주소에 저장된 data에 해당하는 value값을 리턴하는 함수

 

📌Hash Collision 해결 알고리즘

한 개 이상의 data가 중복되어 동일한 address에 저장되는 경우, hash collision 발생

1) Chaining 기법

• Open Hashing 기법 (hash table 저장공간 외의 공간을 활용하는 기법: 충돌이 발생하면 추가 공간을 확보하여 저장)
• 충돌이 일어나면, linked list를 사용하여 데이터를 추가로 뒤에 연결시켜서 저장하는 방법
  (linked list를 사용하기 때문에 미리 저장공간을 잡아놓을 필요없이, 충돌이 날 때마다만 추가하면 됨)

 

구현

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data) #key를 별도의 변수에 저장
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0: #hash table에 data가 들어있으면 (충돌이 발생하면)
        for index in range(len(hash_table[hash_address])): #지금 충돌이 일어난 address에 data가 얼마나 저장되어 있는지 확인
            if hash_table[hash_address][index][0] == index_key: #key값이 중복이면 value를 update
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value]) #key값이 중복이 아니면 append(뒤에 추가) -> 하나의 slot을 쪼개서 key, value를 각각 저장(list안에 list)
    else: #slot에 데이터가 없으면(충돌이 없으면) 그냥 바로 넣기
        hash_table[hash_address] = [[index_key, value]] 

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

 

save_data()

• 고유 key값을 value가 들어있는 slot에 같이 저장해야 하기 때문에 index_key변수에 따로 저장해야 한다. -> 같은 adress에 저장되어 있을 때 index_key로 내가 원하는 값을 탐색해야 하게 때문
• 첫번째 if문은 충돌이 일어나는지, 아닌지를 확인하기 위함
• 충돌이 일어나면, for문을 통해 충돌이 일어난 address에 현재 데이터가 얼마나 저장되어 있는지 확인
• address가 같으므로 탐색을 위해서 하나의 slot에 key와 value값을 같이 저장해 주어야 함 (list안에 list)

 

read_data()

• for문으로 내가 읽어오고 싶은 데이터를 찾기까지 반복문 수행

 

2) Linear Probing 기법

• Close Hashing 기법 (hash table 저장공간 내의 공간을 활용하는 기법: 충돌이 발생하면 hash table안의 반 공간을 찾아서 거기에 저장하는 방법)
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장(저장공간 활용도를 높이기 위한 기법)

 

구현

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

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    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)): #현재 address부터 hash table을 끝까지 반복하면서
            if hash_table[index] == 0: #빈공간 찾으면
                hash_table[index] = [index_key, value] #거기에 데이터 넣기
                return
            elif hash_table[index][0] == index_key: #key자체가 같으면 value update
                hash_table[index][1] = value 
                return
    else: #해당 address에 data가 아예 없음 -> 바로 넣으면 됨 (충돌 발생 X)
        hash_table[hash_address] = [index_key, value]

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: #adress에 값이 있긴 있는데 내가 찾는 값은 없음
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else: #읽어올 data 자체가 아예 없음
        return None

 

save_data()

• 충돌한 data를 다른 공간에 넣어야 하므로 chaining 기법과 마찬가지로 data의 고유한 key도 함께 저장해주어야 함 (address가 같으므로 탐색을 위해서 하나의 slot에 key와 value값을 같이 저장해 주어야 함 (list안에 list))
• 첫번째 if문은 충돌이 일어나는지, 아닌지를 확인하기 위함
• 충돌이 일어나면, for문을 통해 현재 address부터 hash table 끝까지 돌면서 빈공간을 찾으면 거기에 데이터 넣기
• 만약 key자체가 동일하면 data value를 update

 

read_data()

• 첫번째 if문은 data가 hash table에 있는지를 검색
• for문으로 hash table을 돌면서 내가 찾고싶은 데이터 찾기
• if hash_table[index] == 0: 값이 0이라는 건 빈공간이라는 뜻 -> 빈공간이 나왔다면 이전에 이미 찾았으야 됐는데, 빈공간이 나올때까지 아직도 못찾았다며 내가 찾는 값이 없다는 얘기

 

빈번한 충돌을 개선하는 방법

• hashing function 재정의
• hash table 저장공간 확대def hash_function(key):{% endhighlight %}
• => 저장공간↑ → 충돌↓, 탐색시간↓ (:hash table은 공간과 탐색시간을 맞바꾼다)
• return key % 16
• {% highlight python %}
  hash_table = list([None for i in range(16)])

 

📌hashing function과 키 생성 함수

• python의 hash()함수는 실행할 때마다, 값이 달라질 수 있음
• 따라서 SHA(Secure Hash Algorithm) 사용: 어떤 데이터도 유일한 고정된 크기의 고정값을 return

import hashlib

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

def get_key(data):
        hash_object = hashlib.sha256()
        hash_object.update(data.encode())
        hex_dig = hash_object.hexdigest()
        return int(hex_dig, 16)

 

📌시간복잡도

• 일반적인 경우(collision이 없는 경우): $O(1)$ (-> 바로 특정위치에 저장하고 검색하기 때문에)
• 최악의 경우(모두 collision이 발생하는 경우): $O(n)$

-> hash table의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 $O(1)$이라고 할 수 있음

 

검색에서 array와 비교하면

• 16개의 배열에 데이터를 저장하고, 검색: $O(n)$ (-> 모두 한번씩 순회해야 하기 때문에)
• 16개의 데이터 저장공간을 가진 해쉬 테이블에 데이터를 저장하고, 검색: $O(1)$