해시테이블을 알아보기 전에 먼저 해시(Hash), 해시 함수(Hash Functioni), 해싱(Hashing)에 대해 알아보자.

해시(Hash)란?

해시(Hash)란 데이터를 다루는 기법 중 하나로, 임의의 값을 고정 길이로 변환하는 것을 의미한다.

해시 함수(Hash Function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 특정 연산을 이용하여 키(key)를 받아서 값(value)을 가진 공간의 주소로 바꾸어주는 함수를 의미한다.

매핑 전의 원래 데이터의 값을 키(key)라고 하며, 매핑 후의 데이터의 값을 해시값(Hash value) 또는 해시 코드라고 하며, 키(key)와 값(value) 으로 매핑되는 과정 자체를 해싱(Hashing)이라고 한다.

해시테이블(HashTable)이란?

해시테이블은 연관배열 구조를 이용하여 키(key)에 결과값(value)을 저장하는 자료구조이다.

즉, 해시테이블(HashTable)은 key와 value의 쌍으로 데이터를 저장하는 자료구조이다. 언어에 따라서 해시맵(HashMap)이라고도 불리며, Python의 Dictionary 자료형이 해시테이블과 같은 구조이다.

연관배열 구조(associative array)란?

키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

연관배열 구조는 아래와 같은 명령어를 지원한다.

• 키(key)와 값(value)이 주어졌을 때, 연관배열에 해당 2개 값(key & value)을 저장하는 명령
• 키(key)가 주어졌을 때, 연관되는 값(value)를 얻는 명령
• 키(key)와 새로운 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령
• 키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하는 명령

위 명령어는 해시테이블에서도 동일하게 적용된다.

해시테이블의 특징

해시테이블(해시맵, Dictionary)의 특징은 아래와 같다.

• 순차적으로 데이터를 저장하지 않는다.

• 키(key)를 통해서 값(value)를 얻는다.

• 값(value)은 중복 가능하지만, 키(key)는 중복될 수 없음!

• 수정이 가능한 자료구조이다. (=mutable하다.)

장점

1. 데이터 저장/검색 속도가 빠르다.

2. 해시는 키(key)에 대한 데이터(value)가 있는지(중복) 확인이 쉽다.

단점

1. 보통 저장공간이 좀 더 많이 필요하다.

2. 여러 키(key)에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다. (충돌 해결 알고리즘)

시간 복잡도

• 보통의 경우(충돌 X) : O(1)

• 최악의 경우(모든 경우에 충돌이 발생하는 경우) : O(N)

해시테이블의 구조

출처 : 위키백과

해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장이 된다.

• 키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있고, 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해야 하기때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.

• 해시 함수(Hash Function) : 키(key)를 해시(Hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(Hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(Hash)값을 가지는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

• 해시(Hash) : 해시 함수(Hash Function)의 결과물이다. 저장소(bucket, slot = 데이터가 저장되는 공간)에서 값(value)과 매칭되어 저장된다.

• 값(value) : 저장소(bucket, slot)에 최종적으로 저장되는 값이다. 키(key)와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

※ 간단히 말하면, 키(key)를 해시 함수(Hash Function)에 입력으로 넣어 return 되는 값이 해시(Hash)이며, 이 해시값이 저장소(bukcet, slot)에 값(value)로 저장된다.

원래 데이터의 값(key) --> 해시 함수(Hash Function) --> Hash_Function(key)의 결과 = Hash Code --> Hash Code를 배열의 Index로 사용 --> 해당하는 Index에 data(value) 넣기

해시 충돌 (Hash Collision)

해시테이블은 삽입, 삭제, 탐색 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있어 자료구조의 효율성 측면에서 매우 훌륭하다. 하지만, 이렇게 훌륭한 자료구조도 단점을 가지고 있다.

해시(Hash)를 이용한 자료구조 방식에 필연적으로 나타날 수 있는 문제는

무한한 값(해시테이블에서는 키(key)를 의미)을 유한한 값(해시테이블에서는 해시(Hash)를 의미)으로 표현하면서 서로 다른 2개 이상의 유한한 값이 동일한 출력값을 가지게 된다는 것이다.

아래 그림을 통해 알아보자.

'John Smith'와 'Sandra Dee'의 해시(Hash)가 같다. 이러한 현상을 해시 충돌(Hash Collision)이라고 한다.

앞에서도 언급했지만, 해시 충돌(Hash Collision)은 필연적으로 나타날 수 밖에 없다. N+1개의 비둘기가 N개의 비둘기 집에 들어간다면 적어도 1개 이상의 비둘기 집에 2마리 이상의 비둘기가 있을 것이기 때문이다. (비둘기 집의 원리)

충돌을 해결하는 방법 여러 가지가 존재하는데, 그중 Chaining의 방법만 포스팅 하겠다. 다른 방법도 궁금하시다면 맨 아래 출처 링크에 들어가면 된다.

Seperate Chaining(줄여서 Chaining) -> 충돌 해결 방법 중 하나

'Sandra'가 들어가는데 충돌이 일어나니 기존에 있던 'John'의 값에 연결시켰다.

Chaining기법은 자료 저장 시, 저장소(bucket)에 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법이다. 위 사진에서 'Sandra'를 저장할 때 충돌이 일어났고, 기존에 있던 'John'에 연결시켰다. 이때 연결 리스트(Linked List) 자료구조를 이용한다. 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것이다.

장점

1. 한정된 저장소(bucket)을 효율적으로 사용할 수 있다.

2. 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.

3. 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.

단점

1. 1개의 해시(Hash)에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율이 낮아진다.

2. 외부 저장 공간을 사용한다.

3. 외부 저장 공간 작업을 추가로 해야한다.

시간 복잡도

• 해시테이블의 저장소(bucket)의 길이를 N이라 하고, 키(key)의 개수를 M이라고 하자.
  평균적으로 저장소에서 1개의 해시(Hash)당 (M/N)개의 키가 들어있다.

• [삽입] 충돌이 일어났을 때, 해당 해시(Hash)가 가진 연결리스트의 Head에 자료를 저장할 경우, O(1)의 시간복잡도를 가진다. 해당 해시(Hash)를 산출하고 저장하면서 기존 값(value)를 연결하는 행위만 하면 되기 때문이다.
  반면 Tail에 자료를 저장할 경우, O(M/N)의 시간 복잡도를 가진다. 해당 해시(Hash)를 저장할 때 모든 연결리스트를 지나서 Tail에 접근해야 하기 때문이다. 최악의 경우, O(n)의 시간 복잡도를 가진다. 한 개의 해시(Hash)에 모든 자료가 연결되어 있을 수 있기 때문이다.

• [삭제, 탐색] 삭제와 검색은 시간 복잡도 측면에서 비슷한 개념을 공유한다. 산출된 Hash의 연결리스트를 차례로 살펴보아야 하므로 O(M/N)의 시간 복잡도를 가진다. 최악의 경우 O(n)의 시간복잡도를 가진다. 한 개의 해시(Hash)에 모든 자료가 연결되어 있을 수 있기 때문이다. 이 경우 모든 자료를 다 살펴보아야 한다.

해시테이블 구현 코드 (Python)

import hashlib


# 해시 함수 생성
def sha1_hash(input_str):
    hash_obj = hashlib.sha1(input_str.encode())
    hash_value = hash_obj.hexdigest()

    return hash_value


hash_value_apple = sha1_hash('Apple')
print(hash_value_apple)
print(len(hash_value_apple))

print()

hash_value_banana = sha1_hash('Banana')
print(hash_value_banana)
print(len(hash_value_banana))

print()

hash_value_melon = sha1_hash('Melon')
print(hash_value_melon)
print(len(hash_value_melon))
print()

hash_value_strawberry = sha1_hash('Strawberry')
print(hash_value_strawberry)
print(len(hash_value_strawberry))

>>> 476432a3e85a0aa21c23f5abd2975a89b6820d63
>>> 40

>>> fc6fae10db2bd0b625077d7c6d1b9a96925fd2b7
>>> 40

>>> 26e65e893ae5535d32cd0105721177c58a22b962
>>> 40

>>> 393d46da8467a9e4437aa15a2eef178693e18f06
>>> 40

• 해시테이블의 성능에 대해 정리하고 마치겠다.
  키(key)가 배열의 index로 변환되기 때문에 탐색, 저장, 삭제가 빠르다. 평균 시간 복잡도는 O(1)이다.

	평균적인 경우	최악의 경우
탐색	O(1)	O(N)
삽입	O(1)	O(N)
삭제	O(1)	O(N)

참고 : https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o#%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%8A%94-%EB%8F%84%EB%8C%80%EC%B2%B4-%EB%AC%B4%EC%97%87%EC%9D%BC%EA%B9%8C
https://davinci-ai.tistory.com/19
https://velog.io/@taeha7b/datastructure-hashtable
https://hee96-story.tistory.com/48
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://d2.naver.com/helloworld/831311
https://velog.io/@adam2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94