Hash Table(기본 해시함수 예제, 해시충돌부터)

yuns_u·2021년 12월 1일

💛 Hash Table

해시 테이블이란?

해시 테이블:
연관배열구조(associative array)를 이용하여 키(key)에 결과값(value)을 저장하는 자료구조.
키를 빠르게 저장 및 검색할 수 있는 테이블 형태의 자료구조로 키를 활용하여 값에 직접 접근할 수 있다.

연관배열구조(associative array)란 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다.
따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.
해싱의 목적은 보통의 정렬알고리즘과는 달리 검색이 주요한 목표로 검색알고리즘의 성격을 가지고 있다.
해싱은 키를 통해 값을 검색하기 때문에 성능이 빠르며 데이터의 양에 영향을 덜 받는다.

파이썬의 딕셔너리가 내부적으로 해시테이블의 구조로 구현되어 있다고 한다.
즉, 해시테이블은 검색을 위한 자료구조이면서 딕셔너리를 위한 자료구조 역할을 한다.

<연관배열 구조에서 할 수 있는 것들> : 아래의 명령들은 해시 테이블에서도 동일하게 적용된다.

키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 키와 값을 저장하기

키(key)가 주어졌을 때 연관되는 값(value)를 확인하기

키(key)와 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)로 교체하기

키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하기

해시 테이블의 구조

해시 테이블의 구조: 키(key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, slot)으로 이루어져 있다.

키(key)
고유한 값이며 해시 함수의 input이다.
다양한 길이의 값이 될 수 있기 때문에 이 상태로 최종 저장소에 저장된다면 다양한 길이만큼의 저장소를 구성해두어야하기 때문에 함수로 값을 바꿔 저장하여 공간 효율성을 높힐 수 있다.
해시 함수(hash function)
키(key)를 해시(hash)로 바꿔주는 역할을 한다.
여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭시키는 역할을 한다.
다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 바꿔주어 저장소를 효율적으로 운영할 수 있도록 한다.
이 때, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(hash collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

해시 함수의 요구조건
1) 해시함수는 입력값이 같다면, 동일한 출력값을 받아야한다.
2) 입출력값이 일정하지 않다면 적절한 해시함수가 아니다.
3) 하나의 해시함수가 입력 데이터별로 다른 숫자와 매핑된다면 그것은 완벽한 해시함수이다.
(해시함수가 입력데이터에 따라 다른 숫자를 반환하게 되면 해시충돌을 최소화하는 것이다.)

해싱(hashing)
다 흩뜨려놓고 키와 매칭되는 값을 검색하는 과정이라고 할 수 있다.
해시(hash)
해시 함수의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
값(value)
저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

해시 테이블의 기능

Insertion(저장)

해시 테이블에서 자료를 저장하기 위해서는 해시 함수(hash function)으로 키(key)를 해시(hash)로 변경해야 한다.

위의 이미지에서 예시를 들어볼 수 있다.
만약 해시 함수가 input key를 7로 나눈 나머지로 변경해서 출력한다면 key는 76, 해시는 6이 된다.
이 때 미리 준비해놓은 저장소(슬롯, 버킷)인 0, 1, 2, 3, 4, 5, 6에서 맞는 해시값을 찾아 해당 값을 저장한다.

해시 함수로 해시를 산출하는 과정에서 서로 다른 키가 같은 해시로 변경되는 문제가 발생할 수 있는데, 이는 키와 값이 1:1로 매칭되어야 한다는 규칙을 위배한 것이므로 이를 어느 정도 해소하기 위한 방법을 염두에 두어야 한다.

저장의 시간복잡도는 O(1)이다.
키는 고유한 값이며 해시함수의 결과로 나온 해시와 값을 저장소에 넣으면 작업이 끝나기 때문이다.
해시함수의 시간복잡도는 고려하지 않지만 최악의 경우 저장의 시간복잡도는 O(n)이 될 수 있다. 해시 충돌로 인해 모든 버킷의 값들을 찾아봐야하는 경우도 있기 때문이다.

Deletion(삭제)

저장소에 저장되어 있는 값을 삭제하는 것을 의미한다.
이 때에는 저장소에서 해당 key와 매칭되는 값(value)를 찾아서 삭제하면 된다. 저장소에는 hash와 value가 함께 저장되어 있으므로 함께 지우면 된다.

삭제의 시간복잡도는 O(1)이다.
키는 고유한 값이며 해시함수의 결과로 나온 해시에 매칭되는 값을 저장소에서 삭제하면 작업이 끝나기 때문이다.
해시함수의 시간복잡도는 고려하지 않지만 최악의 경우 삭제의 시간복잡도는 O(n)이 될 수도 있다.
해시 충돌로 인해 모든 버킷의 값들을 찾아봐야할 수도 있기 때문이다.

Search(검색)

검색은 key로 value를 찾는 것인데, 이 과정이 삭제의 과정과 유사하다.
먼저 key로 hash를 구한 뒤 hash로 value를 찾는 것이기 때문이다.

저장 단계의 시간복잡도는 O(1)이다.
키는 고유한 값이며 해시함수의 결과로 나온 해시에 매칭되는 값을 찾으면 되기 때문이다.
이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
해시 충돌로 인해 모든 저장소의 값을 찾아봐야한다면 최악의 경우 시간복잡도가 O(n)이 될 수 있다.

기본 해시함수

해시함수는 보통 문자열 입력값에 정수형 출력값을 반환한다.
정수형에서 문자열로 변환하기 위해서, 해시함수는 문자열에 해당하는 개별적인 단어를 활용한다.
- 아래의 예시는 파이썬에서 .encode() 메소드를 활용해서 문자열에서 바이트 코드로 인코드하는 것이다.
- 인코딩된 뒤 정수형은 각 단어를 의미한다.