📍 해쉬란?

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다
즉, 해쉬를 사용하면 즉시 저장하거나 찾고자 하는 데이터의 위치를 즉각적으로 참조할 수 있으므로 다른 알고리즘보다 처리 속도가 빠르다

해쉬 알고리즘을 사용하는 방법으로는 3가지가 있다
이를 살펴보자

📍 Direct Addressing Table

key-value쌍의 데이터를 배열에 저장할 key값을 직접 배열의 인덱스로 사용하는 방법이다

예를 들면, 키값이 400인 데이터가 있으면
배열의 인덱스가 400인 곳에 키 값을 저장한 후 이를 포인터로 연결해 데이터를 가져온다

똑같은 키가 존재하지 않는다는 가정하에 데이터를

• 삽입 -> 각 키마다 자신만의 공간이 정해져 있으므로 해당 위치에 삽입을 진행
• 삭제 -> 해당 키의 위치에 NULL값을 넣어줌

원하는 데이터의 key를 알고 있으면, 해당 위치를 찾는것이 즉시 가능하므로 탐색 / 저장 / 삭제 / 갱신 모두 선형시간인 O(1)에 수행된다.

하지만, key의 크기만큼 배열이 할당되기에 저장하고자 하는 데이터가 적다면 공간낭비가 심할 수 있다.

📍 Hash Table

key값을 함수를 이용해 계산을 진행한 뒤, 그 결과값을 배열의 인덱스로 사용하는 방법이다.
이때, key값을 계산하는 함수를 해쉬 함수 (Hash Function)라고 부른다

예를 들면 k값이 h(k)로 해쒸되었다고 하면, h(k)는 k의 해쉬값이다

Direct Addressing Table과 달리, 테이블의 크기가 key의 크기가 아닌 h(k)만큼의 공간에 저장된다

다만 해쉬테이블의 가장 큰 문제점인 충돌이 존재한다
충돌은 다른 k값이 동일한 h(k)값을 가져 동일한 배열 위치에 저장되는 현상을 말한다

해쉬 함수에서는 이를 최소화하는 방식으로 진행된다

Chaining 방법

이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 말한다
해쉬 테이블에서 동일한 해쉬값이 발생하면, 해당 값에 위치에 있던 데이터들의 key값을 포인터로 연결하는 것이다

즉, 최초로 저장된 h(k)의 데이터를 시작으로 하여 그 이후에 발생되는 h(k)값이 출력되는 데이터들이 연결리스트로 구현된다

적재율

적재율이란, 현재 저장된 key값의 갯수 K와 전체 테이블의 갯수 N을 서로 나눈 값인 K/N을 말한다.
즉, 현재 저장된 데이터가 많아질 수록 충돌 확률이 높아져서 연결 리스트 탐색 확률도 증가한다는 것이다

Simple uniform hash

다음 두가지 조건을 만족하여 좋은 해쉬 함수를 만들어내는 방법이다

• 계산된 해쉬값들은 0부터 배열의 크기 -1사이의 범위를 동일한 확률로 골고루 나타내야 한다
• 각각의 해쉬값들은 서로 독립적으로 생성되어야 한다

첫번째 조건으로 인해 충돌이 일어날 확률을 줄이며
두번째 조건으로 인해 반복적인 충돌을 일으킬 확률을 줄인다

divison method

특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용하는 방법인 modular 연산방법을 이용하는 것이다

📍 Open Addressing

모든 데이터 (key + 데이터)를 테이블에 저장하는 방법이다
데이터를 모두 직접읽어오기에 포인터를 사용할 일이 없다
따라서 포인터 접근에 필요한 시간도 존재하지 않으며, 포인터를 사용함으로서 발생할 수 있는 오버헤드 또한 방지할 수 있다

이에 대한 방법들을 자세히 알아보자

Liner probing

동일한 key값이 발생하여 충돌이 일어나면 바로 다음 인덱스에 데이터를 저장한다
즉, 충돌이 일어나지 않을때까지 다음 인덱스로 이동하면서 빈공간을 탐색하여 저장하는 것이다

만약, 슬롯이 너무 많아지게 된다면 이는 탐색시간도 증가시킬 것이다
이에 대한 차선책으로 등장한것이

Quadratic probing

hash 함수를 2차식의 형태로 만들어 primary clustering을 방지한다
h(k,1) = (h'(k) + c1*i + c2*i^2) mod m
한칸씩 이동하는 것이 아닌 c1* i + c2*i^2만큼 이동한다

하지만, 처음 시작 해쉬값이 같을경우
그 이후의 해쉬값들 모두 동일한 값으로 계산되는 secondary clustering의 문제가 발생한다

Double hashing

secondary clustering을 해결하기 위해 사용한 방법이며,
해쉬함수를 두개의 해쉬함수로 구성하는 것이다

h1(k) = k mod m 
h2(k) = k mod m2
h(k,i) = (h1(k) + i *h2(k)) mod m