[Python 자료구조] 해시테이블 (Hash Table)

해시 테이블

CodeIt 자료구조 수업을 정리한 내용입니다.

1. Key-Value 데이터

• 110호: "제임스"
• 하나의 key와 그 key에 해당하는 value를 말합니다.
• 하나의 key에는 하나의 value만 존재

2. Direct Access Table

배열 인덱스를 키로 이용해서 데이터를 저장하거나 가져오는 것을 Direct Access Table이라 말합니다.

하지만 위에 사진에서 볼 수 있듯이 사용하는 데이터의 갯수는 5개이지만

인덱스의 가장 큰 값으로 인해 총 길이가 942개중 937개가 낭비되는 현상이 발생합니다.

3. Hash Table

해시 함수와 배열을 함께 사용하는 자료구조를 말합니다.

1. 원하는 크기의 배열을 생성
2. 해시 함수를 이용해 저장할 key:value 데이터의 키를 배열 index 범위의 자연수로 변환
3. 리턴한 배열의 index에 key:value 데이터 저장

3-1. 해시 함수

• 특정 값을 원하는 범위의 자연수로 변환해주는 함수
• 결정론적이야 함 (예측한 그대로 동작하는 것)
• 똑같은 key를 넣었을때 항상 똑같은 결과가 리턴
  • ex) 942 -> 10 고정
• 빨리 계산되어야 함
  • 연산이 느리거나 비효율적이면 해시 테이블도 비효율

3-2. 해시함수 나누기 방법

def get_make_hash_func(key, array_size):
    # 해시 테이블의 key를 나누기 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수
    return key % array_size

3-3. 해시함수 곱하기 방법

# a값은 0과 1 사이에 임의의 소수 아무거나
def get_hash_func_multiple(key, array_size, a):
    # 해시 테이블의 key를 곱셈 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수
    temp = a * key # 곱하기
    temp = temp - int(temp) # 소수점만 남기기

    return int(array_size * temp) #사이즈와 temp를 곱해 정수만 return

print(get_hash_func_multiple(2307, 200, 0.323423)) # 27

3-4. 파이썬의 해시함수

파이썬 내부함수의 해시함수는 특정 범위가 아닌 아무런 정수로만 변경해주고 불변 타입 자료형에만 사용 가능합니다.

불변 타입의 자료형으로는 bool, int, float, tuple, str를 말합니다.

4. Chaining

충돌이 일어날때 쇠사슬처럼 데이터를 연결시켜 충돌이 발생하지 않게 데이터를 저장하도록 하는 방법을 말합니다.

충돌을 대비해 각 인덱스에 링크드리스트를 저장하는 구조를 말합니다.

1. 키값이 101, 204인 2개의 데이터가 해시함수를 통해 배열에 인덱스가 20으로 동일
2. 우선 해당 키값을 해시함수에 넣어 인덱스에 저장
3. 다른 데이터 추가시 동일한 인덱스라면 기존 데이터의 노드에서 next 노드로 지정

chaining은 이런 방식으로 이뤄지게 됩니다.

5. Hash Table Code

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 탐색 (처음부터 끝까지 돌면서 key값으로 매칭하여 return)
    def find_node_with_key(self, key):
        iterator = self.head
        while iterator is not None:
            if iterator.key == key:
                return iterator
            iterator = iterator.next
        return None # 해당 데이터가 없으면 None 

        # 추가
    def append(self, key, value):
        new_node = Node(key, value)

        # 비어있을때
        if self.head is None: 
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

        # 삭제
    def delete(self, node_to_delete):
        # 마지막 1개 노드가 남았을때
        if node_to_delete is self.tail and node_to_delete is self.head:
            self.head = None
            self.tail = None
        # 지울 노드가 head일때
        elif node_to_delete is self.head:
            self.head = self.head.next
            self.head.prev = None
        # 지울 노드가 tail일떄
        elif node_to_delete is self.tail:
            self.tail = self.tail.prev
            self.tail.next = None
        # tail, head가 아닌 중간 노드 삭제시
        else:
            node_to_delete.next.prev = node_to_delete.prev
            node_to_delete.prev.next = node_to_delete.next

    def __str__(self):
        res_str = ""
        iterator = self.head

        while iterator is not None:
            res_str += "{}: \"{}\"\n".format(iterator.key, iterator.value)
            iterator = iterator.next
        return res_str

5-1. 해시테이블 탐색

원하는 key에 해당하는 value값을 찾는 연산을 말합니다.

키값 101을 통해 해시 테이블의 탐색 과정은 아래와 같습니다.

1. 키값 101을 해시함수에 넣어 리턴된 값으로 배열의 인덱스 20에 접근
2. 인덱스에 저장된 링크드 리스트에 원하는 데이터를 탐색
3. 원하는 키가 있는지 순차적으로 선형 탐색

5-2. 해시 테이블 탐색 연산 시간 복잡도

-	탐색 연산 단계
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 탐색	O(n)
총합	O(n)

5-3. 해시테이블 삽입

새로운 key - value 쌍을 저장하는 것을 말합니다.

키값 205를 가지고 삽입하는 과정은 아래와 같습니다.

1. 키값 205를 해시함수에 넣어 배열의 인덱스 20에 접근
2. 해당 배열의 인덱스에 추가하고자 하는 키를 가진 노드가 있는지 탐색
   1. 하나의 key에 하나의 value만 존재하기 때문에
3. key가 이미 존재한다면 삽입하는 value로 변경, key가 없다면 노드를 추가

5-4. 해시 테이블 삽입 연산 시간 복잡도

-	탐색 연산 단계
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 탐색	O(n)
링크드 리스트 저장, 수정	O(1)
총합	O(n)

5-5. 해시테이블 삭제

원하는 key에 해당하는 value값을 삭제하는 연산을 말합니다.

키값 205를 가지고 삭제하는 과정은 아래와 같습니다.

1. 키값 205를 해시함수에 넣어 배열의 인덱스 20에 접근
2. 해당 배열의 인덱스에 추가하고자 하는 키를 가진 노드가 있는지 탐색
3. 원하는 key값의 노드를 삭제

5-6. 해시 테이블 삭제 연산 시간 복잡도

-	탐색 연산 단계
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 탐색	O(n)
링크드 리스트 삭제	O(1)
총합	O(n)

5-7. 해시 테이블 연산 종합

동작	시간복잡도
탐색	O(n)
삽입	O(n)
삭제	O(n)

위에서 알아본 해시 테이블의 3개 연산 모두 키를 이용해 저장된 링크드 리스트의 노드를 탐색하는 과정을 포함합니다.

이 때문에 탐색은 링크드 리스트 총 길이에 비례하는 시간복잡도를 가집니다.

결국 처음부터 끝까지 확인할 수 밖에 없는 구조를 가지며 이 부분을 분할 상환 분석을 적용해보겠습니다.

각각의 연산들은 탐색외에 해시 함수 계산, 인덱스 접근, 삭제 또는 삽입등은 O(1)의 시간이 걸렸습니다.

이때 탐색 연산의 시간복잡도를 O(average_length)로 가정합니다.

탐색의 시간복잡도를 평균 소요시간을 가지고 재평가를 하게 된다면 아래와 같습니다.

평균을 구할 때 총합에서 현재 가진 값을 나누게 되는데 이를 해시 테이블에 적용해보면

사용하는 배열의 크기 m, key - value 쌍 수 n이 있다고 했을때 O(n/m)이 걸리게 됩니다.

이때 중요한 포인트는 해시 테이블을 사용할때 어느정도의 조건까지는 n = m을 유지시켜준다는

암묵적 약속을 하는 것입니다. 이렇게 된다면 1 = 1이 되버리기 때문에 결국 O(n)이 걸리게 됩니다.

이를 통해 분할 상환 분석을 적용한 시간 복잡도는 다음과 같습니다.

동작	시간복잡도
탐색	O(1)
삽입	O(1)
삭제	O(1)

해시 테이블 삽입, 삭제, 탐색 연산은 최악의 경우 O(n), 평균적으로 O(1)

6. Open Addressing

Chaining과 달리 하나의 인덱스에 하나의 key - value를 저장하는 구조를 말합니다.

Chaining의 메모리 문제가 발생하지 않지만 대신 해시 충돌이 생길 수 있습니다.

예를 들어 101과 204의 키값은 해시함수로 변환하면 20이 됩니다.

이때 중복된 키값으로 인해 저장시 충돌이 발생하게 되는데 이때 다른 비어있는 인덱스를 찾아 데이터를 저장합니다.

비어있는 인덱스를 찾는 방법은 다음과 같습니다.

• 선형 탐사: 충돌이 발생시 한칸씩 다음 인덱스가 비었는지 확인 (선형적 찾기)
• 제곱 탐사: 충돌 인덱스에 1의 제곱, 2의 제곱, 3의 제곱 값을 더한 인덱스 확인

6-1. Open Addressing 탐색

선형 탐사를 이용해 해당 데이터를 찾을 때 방법은 아래와 같습니다.

1. 해시함수에 key값을 넣어 배열의 인덱스를 찾기
2. 해당 인덱스에 key 확인
3. 없으면 순차적으로 다음 인덱스 확인
   1. 순차적으로 확인하다가 빈 인덱스를 발견시 값이 없다는 의미

6-2. Open Addressing 삭제

선형 탐사를 이용해 해당 데이터를 지울 때 일반적으로 지우는 방법과는 조금 다릅니다.

탐색시 빈 인덱스를 발견시 값이 없다는 의미로 인식한다고 했었는데요

예를 들어 선형적으로 값을 추가했을때 A,B,C가 있습니다.

이때 B를 지우게 되면 A와 C는 같은 키값을 가진 데이터지만 C는 연결고리가 끊어지게 됩니다.

그래서 값을 지우는 것이 아니라 지웠다라는 약속된 표시를 해주고 탐색시 이런 경우는 그대로 탐색을 이어나갈 수 있게 합니다.

6-3. Open Addressing 종합

탐색, 삽입, 삭제 연산 모두 인덱스를 찾는 확인을 해야합니다.

삽입은 탐사를 통해 빈 인덱스를 찾고 탐색과 삭제 연산은 원하는 키를 갖는 데이터를 찾습니다.

탐색를 제외한 다른 연산의 단계들은 O(1)이 걸렸습니다.

탐색는 최악의 경우 O(n)이 걸립니다. 또한 연산 모두 탐색이 포함되기에 시간복잡도는 O(n)입니다.

연산	시간복잡도(최악)
탐색	O(n)
삽입	O(n)
삭제	O(n)

Open addressing, Chaining 모두 테이블의 모든 연산들을 최악이 아닌 평균적으로 O(1)이 걸립니다.