TIL_35 : 해시 테이블

🙄 key-value 데이터

---

• 이미 알고 있는 정보를 이용해서 저장한 정보를 검색할 수 있는 데이터 유형
• 모든 데이터가 배열, 링크드 리스트 처럼 순서관계가 있지 않음
• key-value 쌍 : 하나의 key와 그 key에 해당하는 value를 가리킴
• 하나의 key에는 하나의 value만 있어야 함

🙄 Direct Access Table

---

• 배열 인덱스를 키로 이용해서 데이터를 저장하고 가져오는 방식
• 효율적으로 key-value 쌍을 저장하고 가져올 수 있음 : $O(1)$
• 낭비되는 공간이 많음

1과 100을 key로 갖는 value가 있을 때
배열 인덱스로 저장하면 쓰이는 공간은 2, 낭비되는 공간은 99

🙄 해시 테이블 (Hash Table)

---

➡ 해시 테이블

• 해시 함수와 배열을 같이 사용하는 구조

1. 고정된 크기의 배열을 만든다
2. 해시 함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다
3. 해시 함수 결과 값 인덱스에 key-value 쌍을 저장한다

• key를 바로 인덱스로 사용하지 않고 해시 함수에서 리턴된 값을 인덱스로 사용
• Direct Access Table에서는 인덱스가 key 자체였기 때문에 value만 저장
• 해시 테이블에서는 한 인덱스에 key와 value를 모두 저장

➡ 해시 함수

• 특정 값을 원하는 범위의 자연수로 바꿔주는 함수
• key가 아무리 커도 원하는 범위 사이의 자연수로 바꿀 수 있음

해시 함수의 조건

1. 한 해시 테이블의 해시 함수는 결정론적이어야 됨
   • 똑같은 key를 넣었을 때 항상 똑같은 결과가 나와야 함
2. 결과 해시값이 치우치지 않고 고르게 나와야 함
   • 아무 숫자를 넣었을 때 특정 숫자만 나오지 않고 아무 숫자가 나올 확률이 비슷해야
3. 빨리 계산할 수 있어야 됨
   • 해시 함수는 모든 연산은 할 때마다 사용 됨 효율적인 해시 테이블을 위해서 필수

나누기 방법

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

print(hash_function_remainder(40, 200))
print(hash_function_remainder(120, 200))
print(hash_function_remainder(788, 200))
print(hash_function_remainder(2307, 200))

# 40 
# 120
# 188
# 107

곱셈 방법

def hash_function_multiplication(key, array_size, a):	# 0 < a < 1   임의의 수
    """해시 테이블의 key를 곱셈 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
    temp = a * key      		# a와 key를 곱한다
    temp = temp - int(temp) 		# a와 key를 곱한 값의 소숫점 오른쪽 부분만 저장한다
    return int(array_size * temp)   	# temp와 배열 크기를 곱한 수의 자연수 부분만 리턴

print(hash_function_multiplication(40, 200, 0.61426212))
print(hash_function_multiplication(120, 200, 0.61426212))
print(hash_function_multiplication(788, 200, 0.61426212))
print(hash_function_multiplication(2307, 200, 0.61426212))

# 114
# 142
# 7
# 20

파이썬 hash 함수

• 내부적으로 제공되는 함수
• 파라미터로 받은 값을 그냥 아무 정수로만 바꿔주는 함수
• 위의 해시 함수와는 달리 특정 범위 안에 있는 정수가 아닌 아무 정수
• 불변 타입 자료형에만 사용할 수 있다는 한계점 존재
• 불변 타입 자료형
  1. 불린형
  2. 정수형
  3. 소수형
  4. 튜플
  5. 문자열

🙄 해시 테이블 충돌과 Chaining

---

➡ 충돌(Collision)이 일어났다!

• 한 인덱스에 두 개의 데이터 쌍을 저장해야 하는 경우
• 해시 테이블을 사용하려면 충돌을 제대로 처리해 줘야 함
• 처리하는 방법 중 하나인 Chaining

➡ Chaining

• 쇠사슬을 엮는다
• 충돌이 일어나면 그 값들을 쇠사슬처럼 엮겠다
• 충돌에 대비해서 각 인덱스에 링크드 리스트를 저장
• 배열 인덱스에 링크드 리스트 저장해서 충돌 해결

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

    def find_node_with_key(self, key):
        """링크드 리스트에서 주어진 데이터를 갖고있는 노드를 리턴, 해당 노드가 없으면 None을 리턴"""
        iterator = self.head

        while iterator is not None:
            if iterator.key == key:
                return iterator

            iterator = iterator.next

        return 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):
        """더블리 링크드 리스트 삭제 연산 메소드"""
        if node_to_delete is self.head and node_to_delete is self.tail:
            self.head = None
            self.tail = None
        elif node_to_delete is self.head:
            self.head = self.head.next
            self.head.prev = None
        elif node_to_delete is self.tail:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            node_to_delete.prev.next = node_to_delete.next
            node_to_delete.next.prev = node_to_delete.prev

    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

linked_list = LinkedList()
linked_list.append(508,"구자현")
linked_list.append(106,"민정호")
linked_list.append(2501,"박준규")

print(linked_list)

# 508: 구자현
# 106: 민정호
# 2501: 박준규

🙄 해시 테이블 연산

---

➡ 탐색

• 원하는 key에 해당하는 value를 찾는 연산

탐색 시간 복잡도

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

➡ 삽입

• key-value 데이터 쌍을 저장, 또는 수정
• 이미 삽입하려는 키가 있는지 없는지를 항상 먼저 확인해야 함
• 같은 키의 노드를 찾으면 노드의 value를 새로운 value로 변경
• 탐색에 실패하면 링크드 리스트 맨 끝에 새로운 노드 추가

삽입 시간 복잡도

	탐색 연산 각 단계들
해시 함수 계산	$O(1)$
배열 인덱스 접근	$O(1)$
링크드 리스트 노드 탐색	$O(n)$
링크드 리스트 저장/노드 수정	$O(1)$
총 합	$O(n+3)$ = $O(n)$

➡ 삭제

• 원하는 key에 대한 key-value 데이터 쌍을 삭제

삭제 시간 복잡도

	탐색 연산 각 단계들
해시 함수 계산	$O(1)$
배열 인덱스 접근	$O(1)$
링크드 리스트 노드 탐색	$O(n)$
링크드 리스트 노드 삭제	$O(1)$
총 합	$O(n+3)$ = $O(n)$

➡ Chaining을 쓰는 해시 테이블 평균 시간 복잡도

• 모든 key-value 데이터 쌍이 하나의 링크드 리스트에 저장됐을 때 $O(n)$
• 모두 같은 링크드에 저장되는 건 거의 일어나지 않는 일
• 링크드의 길이가 $avg\_len$이라면 시간 복잡도는 $O(avg\_len)$
• 배열의 크기 = $m$
  key-value 쌍의 수 = $n$ 일 때
  $avg\_len$ = $n/m$
• 해시 테이블을 만들 때, key-value 쌍 수와 배열의 크기를 비슷하거나 작다고 가정
• 실제 해시 테이블을 사용할 때 세 연산들은 그냥 $O(1)$이 걸린다고 가정하고 사용

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

🙄 Open Addressing을 이용한 충돌 해결

---

➡ Open Addressing

• 충돌이 일어났을 때 다른 비어있는 인덱스를 찾아서 거기에 데이터를 저장하는 방법

➡ 비어있는 인덱스를 찾는 방법

선형 탐사 (Linear Probing)

• 충돌이 일어났을 때, 한 칸씩 다음 인덱스가 비었는지 확인

제곱 탐사 (Quadratic Probing)

• 충돌이 일어났을 때, 제곱을 한 값들을 이용해서 인덱스를 찾음
  ex) 10, 11, 15, 24 순으로 탐사

🙄 Open Addressing 탐색/삭제 연산

---

➡ 탐색 연산

• 선형 탐사를 이용해서 데이터를 찾음
• 해시 함수 return값과 데이터 key가 다르면 다음 인덱스를 선형적으로 확인
• key가 같으면 value값 return
• 선형 탐사 중 빈 인덱스를 발견하면 해당 key에 대한 데이터 저장❌
• 빈 인덱스를 찾으면 연산을 마치면 됨

➡ 삭제 연산

• 해시 함수 return값과 데이터 key가 다르면 다음 인덱스를 선형적으로 확인
• 데이터를 찾고 단순히 삭제만 해선 안됨
• 다음 인덱스에 데이터가 있을 경우 선형 탐사를 할 수 없기 때문
• 삭제한 인덱스를 빈 값으로 두지 않고 "DELETED" 혹은 약속된 표시를 해줌

🙄 Open Addressing 시간 복잡도

---

➡ 최악의 경우 : 인덱스가 한 개만 비어있는 경우

• key를 해시 함수에 넣고, 결과 값으로 인덱스에 접근하는 데 걸리는 시간 $O(1)$
• 원하는 인덱스에 key-value 쌍을 저장하는 것도 $O(1)$
• Open Addressing은 탐색, 삽입, 삭제 전 모두 인덱스를 찾는 탐사를 해야 함

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

➡ 평균 시간 복잡도

• 하지만 해시 테이블이 꽉 차 있는 경우는 잘 일어나지 않음
• 해시 테이블 연산들을 분석할 때는 load factor라는 것을 사용

load factor

• load factor $a$는 해시 테이블이 사용하는 배열의 크기 $m$, 데이터 쌍 수 $n$이라고 할 때
  $a$ = $n/m$
• 해시 테이블 안에 배열의 크기보다 많은 데이터 쌍을 저장할 수 없기 때문에
  load factor $a$는 항상 1보다 작다고 가정
• 해시 테이블에서 평균적으로 탐사를 해야 되는 횟수 (기댓값)는 $1/1-a$ 보다 작음
  ex) 100칸 중 90개의 데이터가 저장되어있을 때 a = 0.9, 기댓값은 10
  👉 빈 인덱스를 찾기 위해서 평균적으로 10개보다 적은 인덱스를 확인해도 된다는 뜻

연산	시간 복잡도 (평균)
삽입	$O(1)$
탐색	$O(1)$
삭제	$O(1)$