해쉬 테이블(Hash Table)

오늘은 해쉬 테이블(Hash Table) 에 대해 공부 하도록 하겠습니다.

 

---

1. 해쉬 테이블 이란??

해쉬 테이블은 키(Key) 에 데이터 값(Value) 를 저장하는 자료 구조 입니다.

키를 통해 데이트 값을 찾아 주기 때문에 값을 읽는속도가 매우 빠릅니다. O(1)

파이썬의 딕셔너리(Dictionary), C++의 Unorderd_map이 대표적인 해쉬 테이블 자료구조 예시입니다.

따라서 파이썬, C++은 따로 해쉬 테이블을 구현 안해도 괜찮습니다.

출처 : https://velog.io/@fore0919/TIL-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%89%AC%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

---

2. 해쉬 테이블 용어 정리

• 해쉬(Hash) - 임의 값을 고정 길이로 변환하는 것
• 해싱 함수(Hash Function) - Key를 해쉬 값(Value)으로 저장되는 주소값으로 바꾸기 위한 수식
• 해싱(Hashing) - 키 값을 해시 함수라는 수식을 대입시켜 계산해서 나온 결과를 주소로 사용하여 바로 값에 접근하게 하는 일련의 과정
• 해쉬 주소(Hash Address) - 키를 해싱 함수로 연산후, 해쉬 값을 알아내고, 이것을 해쉬 테이블에서 해당 키에 맞는 데이터를 찾음
• 버킷(Bucket) - 여러개의 슬롯을 저장하는 레코드 형태의 자료 구조, 갯수는 고정적
• 슬롯(Slot) - 한 개의 데이터를 저장할수 있는 공간, 버킷 안에는 여러개의 슬롯이 존재할수 있음

서로 다른 키값이 해쉬 함수에 의해 같은 해쉬 주소로 변환 될수 있음 여러개의 항목을 동일한 버킷, 다른 슬롯에 저장이 가능함

출처 : https://velog.io/@fore0919/TIL-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%89%AC%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

---

3. 해쉬 테이블의 장 단점

장점	단점
데이터의 저장 읽기 속도가 빠르다 O(1)	저장공간이 많이 필요하다
Key에 대한 데이터가 중복인지 확인이 빠르다	여러 키가 같은 해쉬 주소를 가르키고 있으면 충돌이 일어난다.
다량의 데이터를 적은 리소스로 관리가 가능해 효율적	충돌이 일어날경우 시간 복잡도가 O(n)의 가까워진다.
키와 해쉬값이 연관이 전혀 없기 때문에 해쉬 값만 가지고 키를 온전이 알수 없어 보안성이 뛰어나다.

---

4. 문제점

해쉬 충돌(Hash Collision) - 서로 다른 키값이 동일한 인덱스를 가르키는 경우 해쉬 충돌이 발생하여 해시 테이블의 성능을 매우 하락한다. 버킷 안에는 여러 슬롯이 존재하므로 충돌이 생겨도 저장이 가능하다.

 

오버 플로우(OverFlow) - 키가 모든 슬롯이 가득 차있는 버킷과 매핑할경우 위에 충돌에서 슬롯은 유한이기 때문에 주어진 슬롯에 저장을 못하는 경우가 발생 이를 오버플로우라고 함

 

클러스터(Cluster) - 해쉬 함수가 연산한 해쉬 값들이 골고루 분포 되지 않는 경우 저장공간에 한쪽이 치우쳐있다.

 

---

5. 해결 방안

1. 체이닝

동일한 버킷 내에 슬롯들을 한개식 연결리스트 형식으로 저장하는 방식이다.

 

장점

• 매우 쉬운 구현 방식
• 클러스터 영향을 받지 않음
• 삭제 연산 빠름

단점

• 시간복잡도의 증가
• 메모리 공간의 증가

출처 : https://velog.io/@fore0919/TIL-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%89%AC%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

2. 개방 주소법

개방 주소법은 해쉬 함수로 얻은 주소를 그대로 사용하지 않고 비어있는 공간(버킷)을 활용하는 방법

추가적인 메모리는 사용하지 않지만 충돌 확률이 있다.

대표적으로 선형탐사, 이중해싱, 제곱 탐사가 있다.

 

1. 선형 탐사

충돌 발생시 충돌의 발생 지점에서 다음지점에 비어있으면 저장하는 형식 만약 다음에 비어있지않으면 계속 다음을 탐색

장점 : 방식이 매우 간단하며 캐쉬의 효율이 매우 좋음

단점 : 클러스터 현상의 취약, 비어 있는 버킷을 탐색하는 시간이 걸림

 

2. 제곱 탐사

폭이 제곱수로 늘어나는 방식

장점 : 선형 탐사보다 적은 클러스터

단점 : 해시 값이 같으면 다음 탐사 위치도 동일하기 때문에 효율성이 매우 떨어짐

3. 이중 해싱

탐사할 해시 값을 다시한번 해싱을하는 방식

장점 : 클러스터가 거의 없다.

단점 : 더 많은 연산 필요

 

---

6. 체이닝 VS 개방 주소법

체이닝	개방 주소법
삭제 작업이 매우 간단	데이터의 크기가 작으면 성능이 매우 좋아진다.(메모리 절약)
클러스터의 영향을 거의 안받는다.	데이터가 크거나, 매우 가변적이면 체이닝보다 더욱더 효율이 좋다.
사용 중인 슬롯 비율이 높아도 성능 저하가 급격히 일어나지 않는다.

---

7. Reference

https://velog.io/@fore0919/TIL-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%89%AC%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

[TIL] 자료구조 : 해쉬테이블(Hash Table)