[TIL] 해쉬 테이블 - Hash Table

해쉬 테이블(Hash Table)이란?  (파이썬의 Dictionary)

• 키에 데이터를 저장하는 데이터 구조이다.
• 데이터 검색 속도가 매우 빠르다
• 배열로 미리 해쉬 테이블 사이즈만큼 생성 후 사용한다.

 

용어

• 해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것
• 해싱함수(Hashing Function) : key를 가지고 연산하여 데이터의 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) : 해싱함수를 이용하여 key에 대한 연산을 통해 해쉬값을 알아냄  
• 해쉬 주소(Hash Address) : 해쉬 값을 기반으로 key에 대한 데이터의 위치를 찾아냄
• 슬롯(Slot) : 한개의 데이터를 저장할 수 있는 공간

 

장점

1. 데이터 검색속도가 빠름 (데이터 저장, 데이터 읽기) // 배열과 비교하여 알아두기
2. 해당 키에 대한 중복 데이터 확인이 쉬움

단점

1. 저장공간이 더 많이 필요함 // 대신 속도가 빠름
2. 데이터 저장 시 충돌의 경우를 대비하여 이를 해결하기 위한 별도의 자료구조가 필요함

---

충돌(Collision) 해결 알고리즘

 1. Chaining : 개방해싱(Open Hashing) 기법중 하나로 해쉬 테이블 저장공간 이외의 공간을 활용하여 충돌을 해결.

                      (충돌 시 해당 주소의 뒤에 링크드 리스트를 연결시켜 데이터를 저장한다.)

 

 2. Linear Probing : 폐쇄해싱(Close Hashing) 기법 중 하나로 해쉬 테이블 저장공간 안에서 충돌을 해결.

                          (충돌 시 해당 해싱주소의 다음 주소부터 빈공간이 나오는 순서대로 저장, 저장공간의 활용도를 높인다.)

 

 3. 해쉬 함수를 재정의하여 저장공간을 확대하는 기법

 

해쉬 테이블의 시간복잡도는?

 - 일반적인 경우로 충돌이 없다면 O(1)로 말할 수 있지만 최악의 경우 충돌이 모두 발생한다면 O(n)