💡 해시 테이블 (HashTable)
👉 = 해시 맵, 해시 표
👉 키(Key) 와 값(Value) 을 한 쌍의 형태로 데이터를 저장하는 자료구조이다.
- 키를 통해 해당 데이터에 빠르게 접근 할 수 있다.
👉 검색을 빠르게 할 수 있어 배열 내의 특정 데이터에 빠르게 접근할 수 있다.
👉 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
💡 해시 테이블의 구조
👉 키 : 해시 테이블 접근을 위한 입력 값
👉 해시 함수 : 키를 해시 값으로 매핑하는 연산
- 해시함수를 사용해 키를 해시값으로 매핑한 후, 이 해시값을 인덱스 혹은 주소로 삼아 데이터 값을 키와 함께 저장한다.
- 좋은 해시 함수는 해시 값에 골고루 분포될 수 있게 만들어주는 함수
👉 해시 값 : 해시 테이블의 인덱스
👉 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조
💡 해시 충돌
👉 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 발생한다.
- 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 발생
👉 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다.
- 데이터 저장 단위로, 값과 포인터로 구성되어 있다.
- 포인터 (Pointer) : 다음 노드나 이전 노드의 연결 정보 (링크 연결 작업하는 부분)
👉 해시값이 충돌할 때는 연결리스트를 사용하여 유연하게 데이터를 저장할 수 있다.
💡 해시 충돌 해결 방법
👉 개방 주소법 (Open Address)
- 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장하는 방법
- hash와 value가 1:1 관계를 유지한다.
- 비어 있는 공간 탐색 방법에 따라 분류한다. (선형 탐사법, 제곱 탐사법, 이중 해싱)
👉 개방 주소법 - 선형 탐사법 (Linear Probing)
- 빈 공간을 순차적으로 탐사하는 방법
: 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사한다. - 일차 군집화 문제 발생
: 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
👉 개방 주소법 - 제곱 탐사법 (Quadratic Probing)
- 빈 공간을 n 제곱만큼의 간격을 두고 탐사하는 방법
: 충돌 발생 지점 부터 이후의 빈 공간을 n 제곱 간격으로 탐사 - 일차 군집화 문제는 일부 보완할 수 있지만, 이차 군집화 문제 발생 가능성이 있다.
👉 개방 주소법 - 이중 해싱 (Double Hashing)
- 해싱 함수를 이중으로 사용한다.
: 해시 함수 1 : 최초 해시를 구할 때 사용한다.
: 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용한다. - 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포된다.
👉 분리 연결법 (Separate Chaining)
- 해시 테이블을 연결 리스트로 구성한다.
- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아니고 연결 리스트를 사용하여 해당 테이블에 데이터를 연결한다.
BE