해시, 해시테이블, 해시충돌이란?

해시테이블이란?

: 키를 활용하여 값에 직접 접근이 가능한 구조

: (파이썬의 딕셔너리는 내부적으로 해시테이블 구조)

 

해시(Hash)는 해시 함수를 통해 나온 값이다.
해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조이다.
해시함수는 여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭시키는 역할을 한다.
해싱(Hashing)은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정이다

해싱의 장점 : 데이터 양에 영향을 덜 받으며 성능이 빠르다.(키를 통해 값을 검색한다.)

 

해시함수

 

---

해시충돌

 

해시충돌이 발생하는 이유는?

가능한 모든 데이터를 알고 있지 않으면 완벽한 해시 함수를 작성하는 것은 불가능

해시충돌은 키가 들어갈 자리(버킷)가 없는 경우에 발생

충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적

 

 

---

해시충돌 방지방법 - 체이닝 (Chaining)

체이닝은 리스트를 활용하여 해시함수에서 매핑된 후,

bucket에서 연결될 수 있는 entry에 제한을 두지 않는 체인 형태로 연결하는 것

해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키값을 뒤이어 연결

 

해시충돌 방지방법 - 오픈 어드레싱 (Open addressing)

 

비어있는 배열 슬롯이 발견될 때까지 array의 위치를 검색하여 해시 충돌을 해결

충돌이 일어나는 경우, 탐사(Probing)를 진행하면서 빈 공간을 찾아야 해결

 

---

좋은 해시함수란?

 

(1) 키와 값의 계산과정이 쉬워야 한다
(2) 충돌을 피할 수 있어야한다.