Hash Table (해시 테이블) 정리

 👨🏼‍💻 Hash Table (해시 테이블) 정리 With Python

🥝 Hash Table이란? 

키(key)에 데이터(Value)를 저장하는 데이터 구조입니다.

Key를 통해 바로 데이터를 받을 수 있으므로, 속도가 매우 빠릅니다.

파이썬에서는 딕셔너리 타입을 사용하면 됩니다.

 

🍋 간단한 해시 예시 

hashTable = [0 for i in range(20)]


def hashFunction(key):
    return key % 8


def insertToHashTable(data, value):
    key = ord(data[0])
    hashAddress = hashFunction(key)
    hashTable[hashAddress] = value


def getFromHashTable(data):
    key = ord(data[0])
    hashAddress = hashFunction(key)
    return hashTable[hashAddress]

해쉬 테이블은 위와 같이 해시 함수를 통해 생성된 해시 주소에 맞게 데이터가 저장되는 구조입니다.

이때 키값이 동일하게 생성될 경우 해시 충돌이 일어날 수 있는데 

아래에서 자세히 살펴볼 예정입니다.

또한 매우 간단하게 해시 함수를 구성하였지만

이렇게 해시 함수를 구성하여서는 안되고 중복된 키값이 나오지 않도록 좋은 해시 함수를

구성하여야 합니다 

 

insertToHashTable("밍구리","01012340811")
insertToHashTable("쌈무","01056780811")
insertToHashTable("안댕댕","01099990811")

print(getFromHashTable("밍구리"))
print(getFromHashTable("쌈무"))
print(getFromHashTable("안댕댕"))

출력 예시

 

🍊 해쉬 테이블의 장단점 및 주요 용도 

주요 용도

 

캐시 구현 시 해쉬 테이블이 사용됩니다. -> 중복 확인이 매우 쉽기 때문입니다.

 

캐시는 데이터나 값을 미리 복사해 놓는 임시 장소를 말합니다.

캐시는 캐시의 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용됩니다.

(ex 똑같은 사이트를 다시 띄울 때마다 사이트의 모든 이미지를 다시 불러오는 것은 매우 느릴 것입니다. 그렇기 때문에 이미지 중 변하지 않은 이미지 일부를 캐시에 저장하고 있습니다.)

 

🍉 해쉬 충돌 및 해결 방법 

해시 함수에 의하여 생성된 키 값이 동일할 경우 같은 데이터가 같은 공간에 저장되게 되는

해시 충돌이 일어나게 됩니다.

물론 같은 키 값이 생성되지 않도록 좋은 해시 함수를 만들어야 하지만

해쉬 충돌이 발생할 시 해결 방법은 아래와 같습니다.

 

1. Chaining 기법

 

2. Linear Probing 기법

 

🍈 시간 복잡도