[자료구조] Dictionary / HashMap / HashTable

1. HashTable

HashTable(해시 테이블)은 Key 와 Value 의 쌍으로 데이터를 저장하는 자료구조 입니다.
언어에 따라서 HashMap이라고도 불리며, 파이썬의 Dictionary 또한 HashTable로 구현되어 있습니다.

HashTable(HashMap, Dictionary)의 특징은 다음과 같습니다.

• 순차적으로 데이터를 저장하지 않습니다.
• Key를 통해서 Value값을 얻습니다.
• Value값은 중복가능 하지만 Key는 중복될 수 없습니다.
• 수정 가능합니다.(mutable)

파이썬의 List나 자바스크립트의 Array와 달리 저장된 데이터를 순차적으로 찾는게 아니고,
Key값을 통해서 Value값을 찾기 때문에 빠릅니다.

2. HashTable 내부 구조

1) Hash Function

Hash Function(해시함수)은 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말합니다.

임의의 길이를 갖는 데이터를 해시함수에 적용하여 나온 고정된 길이의 값을 해시값이라고 합니다.

Hashing(해싱)은 해시 함수를 이용해 해시테이블을 탐색하는것으로 작동원리는 다음과 같습니다.
헤시테이블에서 key로 '대한민국', '김태하', '1234', '56789'를 갖고,
각각 '만세', '개발자', '아라비아', '숫자'를 value로 갖습니다.

해시함수를 통해서 해시값으로 영문자와 소문자가 섞인 해시값을 얻을수도 있고, 이 값을 정수로 바꾼 해시값도 얻을수 있는데 아래의 예에서는 해시함수를 통해서 해시값을 정수로 얻은것 입니다.

이렇게 얻은 해시값(정수)을 buckets(버킷, 데이터가 저장되는 공간)의 크기로 나누고, 나온 나머지를 버킷의 인덱스로 갖습니다.
따라서 예시에서는 '대한민국'이라는 key는 버킷의 0번째 인덱스에 value를 저장하고, '김태하'라는 key는 버킷의 2번 인덱스에 value를 저장합니다.

해시값을 버킷의 크기로 나누고 나온 나머지를 버킷의 인덱스로 갖다보니 나머지가 같은 값이 나올수가 있는데 이때, 충돌(Collision)이 발생하게 됩니다. 충돌을 해결하는 방법에는 여러가지가 있으며 여기서는 Chaining 방법에 대해 설명하겠습니다.

2) 충돌 해결 방법 : Chaining

key가 '1234'와 '56789' 일때, 나머지가 같아서 같은 버킷 인덱스를 갖게 되면,
우선 '1234'일때 버킷의 99번 인덱스로가서 value(아라비아)를 저장합니다.
그리고 '56789'일때도 버킷의 99번째 인덱스로 가기는 하는데, 이미 저장된 값이 있기 때문에
연결 리스트 형태로 '56789'의 value값을 저장합니다.

아래의 코드는 '대한민국', '김태하', '1234', '56789'에 해시함수를 적용해서 해시값과 해시값의 크기를 나타낸 파이썬 코드 입니다.
해시값은 달라도 같은 크기인것을 확인할 수 있습니다.

import hashlib

def sha1_hash(input_str):
    
    hash_obj = hashlib.sha1(input_str.encode())
    hash_value = hash_obj.hexdigest()
    return hash_value


hash_value_kor = sha1_hash('대한민국')
print(hash_value_kor)
print(len(hash_value_kor))
print()

hash_value_name = sha1_hash('김태하')
print(hash_value_name)
print(len(hash_value_name))
print()

hash_value_1234 = sha1_hash('1234')
print(hash_value_1234)
print(len(hash_value_1234))
print()

hash_value_56789 = sha1_hash('56789')
print(hash_value_56789)
print(len(hash_value_56789))
print()

#실행결과
4f12e8995f9606c6d2dc54c3cd8d1cfe35b8b83a
40

86c871b56d910a3b96edd3906256c3058deab192
40

7110eda4d09e062aa5e4a390b0a572ac0d2c0220
40

f2231d2871e690a2995704f7a297bd7bc64be720
40

3. 언제 사용하면 좋을까?

• Key 와 Value를 함께 묶어서 표현하는 데이터에 사용하면 유용합니다.