[Python] 해시 테이블(Hast Table)

해시 테이블

👉 key - value 데이터

• 하나의 key와 그 key 에 해당하는 value를 합쳐서: key - value 쌍 이라고 한다.
• 하나의 key 에는 하나의 value 만 있어야 한다.

👉 Direct Access Table

• 인덱스 대신 key 를 사용한다고 보면 된다.
• 사용하는 인덱스는 5 이지만, 배열의 크기는 943개를 사용하고 있다.
• 효율적으로 key -value 쌍을 저장하고 가져올 수 있지만, 낭비하는 공간이 너무 커진다.

👉 해시 테이블 개념

해시 함수

• 특정 값을 원하는 범위의 자연수로 바꿔주는 함수

해시 함수의 조건

1. 해시 테이블의 해시 함수는 결정론적이어야 된다.
   • 똑같은 key를 넣었을 때, 항상 똑같은 결과가 나와야한다.
2. 결과 해시값이 치우치지 않고 고르게 나온다.
   • 아무 숫자를 넣었을 때, 원하는 범위가 0부터 100이면 이 사이에 아무 숫자가 나올 확률이 비슷해야한다.
3. 빠르게 계산할 수 있어야 한다.
   • 모든 연산을 할 때마다 해시 함수를 사용해야하기 때문에 효율이 좋아야한다.

해시 테이블

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

 

👉 해시 테이블 충돌(Collision)과 Chaining 개념

Chaining

• 배열 인덱스에 ★링크드 리스트★ 저장해서 충돌 해결!
• 인덱스 값이 중복 되어도 링크드 리스트로 연결 되도록 저장을 한다.

class Node:
	"""링크드 리스트의 노드클래스"""
    def __init__(self, key, value):
    	self.key = key
        self.value = value
        self.next = None # 다음 노드에 대한 레퍼런스
        self.prev = None # 전 노드에 대한 레퍼런스