1. 해쉬 테이블이란?
저장하고자 하는 데이터를 key 와 value 값을 통하여 저장하는 자료구조
데이터를 저장하고 매우 빠르게 탐색을 수행하기 위한 자료구조 이다.
여러가지 다양한 컨테이너들 중에 어쩌면 컴퓨터의 저장방식을 가장 닮은 저장방식이라고 생각한다.
컴퓨터는 결국 모두 숫자(이진수)로 저장을 하고 특정한 규칙에 따라 그 자료를 해석하는 것인데 해쉬 테이블이
이와 매우 유사하다.
2. 해쉬 함수 (hash function)
해쉬 테이블을 구성하는 데 있어 가장 중요한 것이 해쉬 함수(hash function)이다.
이 해쉬 함수, 즉 알고리즘을 어떻게 짜느냐에 따라 해쉬테이블의 탐색 성능이 좌지우지 된다.
저장하고자 하는 데이터를 해쉬함수를 이용하여 가공하여 그 결과값을 key로 하여 테이블에 저장한다.
효율적인 함수를 짜지 못한 경우 최악의 경우 탐색에 O(n)이 소요될 수 있다.
3. 충돌 (Collision)
우선 해쉬테이블을 만들기 위하여 고정된 크기의 배열을 선언해주는데 저장하고자 하는 데이터의 수가 배열의 크기
보다 크다면 필연적으로 두개 이상의 데이터간의 충돌이 일어날 수 밖에 없다.
(물론 위의 경우가 아니더라도 서로 다른 데이터에 대해 동일한 키 값을 만들어 낼 경우 충돌 발생)
따라서 이 충돌에 대한 것을 어떻게 처리해주느냐가 매우 중요한 문제이다.
그러면 충돌을 해결하는 방법을 알아보자.
3-1. Chainig 방식
이름에서 주는 느낌그대로 해쉬테이블 에서 각각의 컨테이너를 링크드 리스트로 선언하여
저장하고 하는 테이블 인덱스에 이미 다른 데이터가 자리하고 있을경우 그 데이터의 뒤쪽에 연결해서
체인처럼 매달아 주는 방식이다.
탐색을 할 때는 찾고자 하는 key값에 해당하는 리스트에서 원하는 값을 탐색한다.
데이터의 수가 상대적으로 많아질 경우 링크드리스트가 아닌 tree 구조를 이용하여 탐색시간을 줄일 수도 있다.
공간에 대한 제약이 적다.
3-2. Open addressing 방식
1. linear probing
충돌이 발생했을 때 테이블에서 그 키 값의 뒤쪽 index의 버켓 중 빈 곳을 찾아 넣는 방식입니다.
탐색을 할 때 찾고자하는 데이터의 key값에 해당하는 버켓에 갔을 때, 원하는 데이터가 아닐 경우 그 뒤쪽으로 탐색을 시작합니다.
그리고 삭제처리를 할때 신경을 써주어야 하는데 단순히 삭제를 해주는 것이 아닌 dummy 데이터를 넣어 원래 비어있던 곳인지
다른 데이터가 있었다가 삭제가 된 곳인지 구분을 해주어야 탐색을 할 때 문제가 생기는 것을 방지할 수 있습니다.
2.double hashing
단순히 충돌이 발생한 뒤쪽에서 부터 빈 곳에 넣는 linear probing과 달리 2차 해쉬 함수를 통해서 새로운 키 값을 구해서
첫 번째 key값에서 2차 해싱 값만큼 jump하여
테이블에 저장하는 방법 이다. (물론, 또 충돌이 발생할 수는 있습니다.)
4. hash function (해쉬 함수)
결국 좋은 해쉬 함수란 데이터들의 특성에 맞게 데이터를 되도록이면 고르게 분포시킬 수 있도록 하여,
충돌을 최소화 할 수 있게 해주는 함수 이다.
