이번 게시글에서는 HashTable에 대해서 간략하게 정리 해보겠다.
spring boot에서 종종 사용하던 HashMap과 비슷하게 작동하는 부분이 있어서 이해하기 크게 어렵지는 않았다.

hash table은 효율적인 탐색을 위한 자료구조로써 key-value쌍의 데이터를 입력받는다.
hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다.

"key k값을 갖는 원소가 위치 h(k)에 hash 된다." 또는 "h(k)는 키 k의 해시값이다"라고 표현 한다.
key는 무조건 존재해야 하며 중복되는 key가 있을 수 없다.

hash table을 구성하고 있는 데이터를 저장할 수 있는 각각의 공간을 slot또는 bucket라고 한다.

🎢 Direct-address

hash table을 짚기 전 direct address table에 대해 먼저 알아보고 진행하는게 이해하는데 도움이 될 것이다.

key 값으로 k를 갖는 data는 index k에 저장된다.

🤔 Direct-address의 문제점

보기에도 굉장히 간단하고 구현하기도 어렵지 않다.
하지만 쉬운만큼 몇가지 문제점이 있기에 한번 알아보겠다.

📌 공간 낭비

key의 값에 따라 배열의 index에 저장하기로 했었다.
이때 만약 특정 data의 key의 값이 굉장히 크다면 배열의 공간 역시 해당 data를 담기 위해 어쩔 수 없이 커져야 할 것이다.

데이터가 몇개 존재하지 않고 key 값의 사이가 매우 멀다면 이는 메모리 공간 낭비로 직결 될 것이다.

📌 key의 type

위의 그림들은 index로 설정이 가능한 값들을 key로 가지고 있는 상황이였다.
만약 data들이 전부 각기 다른 type의 key값을 가지고 있다면 문제가 발생할 것이다.

Integer 값으로 설정된 data는 index에 무리 없이 저장이 가능하지만 key값을 다양하게 가지고 있는 data의 경우 처리 작업이 있어야 저장이 가능할 것 이다.

📘 HashTable

direct address 방식에 문제점이 있는 것을 확인했다.

hash function에서 데이터 타입 변환, 나머지 계산을 하여 index mapping을 한다면 위의 문제는 해결 될 것이다.

하지만 hash function으로 key를 변환 한 h(k) 값이 모두 다르다는 보장은 되지 않으며 중복으로 인한 문제가 발생 할 수 있을 것이다.

Collision

서로 다른 key의 해시값이 똑같을 때를 말한다.
즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이때 collision이 발생한다고 말할 수 있다.
collision이 최대한 적게 나도록 hash function을 잘 설계해야 하고, 어쩔 수 없이 collision이 발생하는 경우 사용할 방법들에 대해 알아보겠다.

📌 Open Addressing

collision이 발생하면 미리 정해놓은 규칙에 따라 비어있는 bucket을 찾아서 데이터를 입력하는 방식 들 이다.
빈 bucket을 찾는 방법은 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉘게 된다.

📝 Linear Probing , Quadratic Probing

선형 조사법은 충돌이 발생한 해시값으로 부터 일정한 값만큼 (+1, +2, +3, ...) 건너 뛰어, 비어 있는 bucket에 데이터를 저장한다.

이차 조사법은 제곱수(+1^2, +2^2, +3^2, ...)로 건너 뛰어, 비어 있는 bucket을 찾는다.

충돌이 여러번 발생하면 여러번 건너 뛰어 빈 slot을 찾는다.
선형 조사법과 이차 조사법의 경우 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링(clustering)현상이 발생하는 단점이 있으며 클러스터링 현상이 발생하면 평균 탐색 시간이 증가한다.

📝 Double Hashing

linear probing이나 quadratic probing을 통해 탐사할 때는 탐사이동폭이 같기 때문에 클러스터링 문제가 발생할 수 있다.
클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식을 이중 해싱이라고 한다.

하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용한다.

첫번째 해시함수를 사용해서 동일한 index에 접근 하더라도 탐사 이동 폭은 unique한 key값으로 계산 된다.

첫번째 h(k)값이 같다 하더라도 탐사 이동 폭은 다르게 출력 될 수 있기에 collision의 성능적 이점을 기대 해볼만 하다.

📌 Separate Chaining

seprate chaning 방식은 linked list 또는 tree를 이용하여 collision을 해결하는 방식이다.

새로운 데이터 추가 시 동일한 해시값으로 인한 collision이 발생하지 않는다면 link를 연결 하여 node를 삽입 한다.

데이터 추가 시 동일한 해시값으로 인한 collision이 발생한다면 linked list에 node를 이어가며 데이터를 추가 및 저장한다.

🤔 worst case

만약 n개의 모든 데이터가 중복 해시값을 갖게 되면 꼬리에 꼬리를 물고 이어지며 길이 n의 linked list가 생성 된다.

사용자가 특정 데이터의 필요성으로 탐색을 하게 된다면 시간 복잡도는 모든 node를 탐색 하는 O(n)이 될 것이다.

당시 가지고 있던 기술 개념으로 작성된 글 이므로 정확하지 않을 수 있으며 문제가 발견 된다면 수정 하겠습니다.