[Python] HashTable (Chaining, Open Addressing)

해시테이블이란, 해시함수를 이용해 키를 값에 매핑하는 자료구조입니다.

 

해시함수란, 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수로, 쉽게 말해 임의의 값을 넣어도 예상 크기 내에서 결과가 나오는 함수입니다. 예를 들면 ‘나머지를 반환하는 함수’가 좋은 해시 함수의 예입니다.

---

 

HashTable

    해시함수를 이용해 키를 값에 매핑하는 자료구조

 

 

해시함수

• 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수
• 쉽게 말해 임의의 값을 넣어도 예상 크기 내에서 결과가 나오는 함수
• ‘나머지를 반환하는 함수’가 좋은 해시 함수의 예

def modThree(n):
    return n % 3

print(modThree(0)) # 0
print(modThree(1)) # 1
print(modThree(2)) # 2
print(modThree(0)) # 0

 

충돌 !

 

 

• 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.
• 입력값이 달라도 똑같은 결과가 나오면 충돌이라고 한다.
• 충돌을 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 두 가지
• 체이닝은 충돌 발생 시 ‘연결’해가는 것이고, 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식

 

체이닝 ▽

 

 

오픈 어드레싱 ▽ 

 

 

• 체이닝은 메모리 오버헤드가 길어질 경우 탐색이 느려진다.
• 오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있다
• 그래서 각 언어 별로 해시테이블의 구현 방식이 상이함

      :  C++, Java, Go는 체이닝을 택하고 Python, Ruby는 오픈 어드레싱을 택하고 있다.