📌 해시 테이블이란?
해시 테이블(Hash Table): (key, value)로 데이터를 저장하는 자료구조다. 즉, key와 value가 1:1로 연관 되어 key를 통해 value를 도출할 수 있는 자료구조다.
Hash Table은 마치 사전과 같다. 사전은 단어를 찾기 위해 사용되기보단, 단어의 정의를 찾기 위해 사용된다. Hash Table 또한 마찬가지이다. Hash Table에서 key는 단순히 value를 찾기 위한 수단이며, 결국 우리가 얻고자 하는 것은 value이다.
📌 해시 테이블 구성
- key: 임의 크기의 데이터
- hash function: 가변 길이의 값을(key) 고정 크기 값으로(hash) 매핑시켜주는 함수.
- hash (=index): 고정된 크기의 값.
- bucket (=slot): 실제 값이 저장되는 장소. index를 활용하여 값을 저장하거나 검색하게 되는데, 여기서 실제 값이 저장되는 장소가 bucket이다.
- hash table: (key, value)로 데이터를 저장하는 자료구조.
📌 해시 테이블의 특징
1. key, value가 1:1로 연관되어 있기 때문에 삽입, 탐색, 삭제 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있다.
- 데이터를 삽입하기 위해선 hash function을 활용해 임의 길이의 key 값을 고정 길이의 hash로 변경한 뒤, bucket에서 알맞는 hash값을 찾아 value를 저장한다. 그렇기 때문에 삽입에서의 시간복잡도는 O(1)이다. 탐색과 삭제의 경우 또한 마찬가지이다. 탐색의 경우 key와 hash function을 활용해 hash를 찾아내고 bucket에서 해당 hash에 맞는 value를 찾아낸다. 그리고 삭제의 경우 key와 매칭되는 value 값을 찾아 삭제한다. 그렇기 때문에 해시 테이블은 충돌이 발생하지 않을 경우 평균적으로 O(1) 시간 복잡도를 가지고 있다고 볼 수 있다.
2. 순서/ 관계가 있는 배열에는 어울리지 않는다.
3. 여러 key들 중, 특정 key들이 해당하는 hash(=index)가 동일한 경우 해시 충돌(Hash Collision)이 발생하게 된다.
📌 해시 충돌(Hash Collision)
해시 충돌(Hash Collision): 해시 함수가 서로 다른 key 값에 대해 같은 hash(=index)값을 도출하는 현상을 말한다.
아무리 좋은 해시 함수라도 충돌은 발생하게 되며, 그렇기 때문에 충돌을 최소화시키는 것이 중요하다.
비둘기집 원리는 충돌의 원리를 설명하는 예시이다.
비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n>m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다.
[그림 2]와 같은 해시 충돌을 막기 위해선 크게 두 가지 해결 방안이 있다.
1. 체이닝(Chaining)
체이닝은 해시 충돌이 발생했을 때 동일한 bucket에 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다. 체이닝 방법은 연결리스트로 연결되어 있기 때문에 충돌이 발생할 때마다 공간을 만들어서 연결만 시켜주면 된다는 장점을 갖고 있다. 하지만 연결리스트로 연결되어 있기 때문에 값을 탐색할 때 요소들을 하나씩 찾아야 하므로 시간복잡도는 O(n)까지 늘어날 수 있게 된다는 단점 또한 가지고 있다.
2. 오픈 어드레싱(Open Addressing)
오픈 어드레싱은 해시 충돌이 발생했을 때 비어있는 hash를 찾아 데이터를 저장하는 방법이다. 비어 있는 hash를 찾아 데이터를 저장할 때, 크게 선형 탐사(linear probing)방법과 제곱 탐사(quadratic probing)방법이 있다.
- 선형 탐사(linear probing): 단순히 한 칸씩 옆으로 옮기면서 비어있는 해시가 나오면 저장하는 방법.
- 제곱 탐사(quadratic probing): n²씩 건너뛰면서 비어있는 해시가 나오면 저장하는 방법이다.
출처:
1. https://ai-rtistic.com/2022/01/29/data-structure-hash/
자료구조(Data Structure) 톺아보기 - 해시(Hash)
This is a space to organize what I have learned while studying AI, ML, DL and Data Science. If there is anything wrong, please let me know in the comments. 이번 포스트에서는 연관배열 구조를 이용하여 키(key)와 값(value)을 저장하는
ai-rtistic.com
2. https://luv-n-interest.tistory.com/1049
해시 테이블, Hash Table 의 장단점 및 한계
해시태그라 불리는 # 그렇다면 해시 테이블은 뭔지 알까? 수많은 자료 구조들 중 하나로 속도가 빠른 자료구조로 알려져 있다. 한 번 알아보자 해시 테이블은 기본적으로 Key- Value 시스템을 가지
luv-n-interest.tistory.com
3. https://product.kyobobook.co.kr/detail/S000001932748
파이썬 알고리즘 인터뷰 | 박상길 - 교보문고
파이썬 알고리즘 인터뷰 | 코딩 테스트와 인터뷰를 준비하는 취준생과 이직자를 위한 알고리즘 문제 풀이 완벽 마스터!세계 최고 온라인 문제 풀이 사이트인 리트코드(LeetCode)의 기출문제 풀이
product.kyobobook.co.kr
'Computer Science > Data Structure' 카테고리의 다른 글
| Queue와 Priority Queue란? (0) | 2023.01.24 |
|---|---|
| 이진 검색 트리(BST)란? (0) | 2023.01.24 |
| 📖 연결 리스트(Linked list) (0) | 2022.04.26 |
