해시, 해시테이블

해쉬란?

해쉬는 임의의 크기를 가진 데이터를 고정된 크기로 변환시키는 것

 

해시 함수란?

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑 하는 과정 자체를 해싱(hashing)

 

해쉬알고리즘?

해쉬를 하는 방법에 대해 절차적으로 명세

해시 테이블이란?

데이터가 해시 함수를 거쳐 분류된 이후 그 정보가 저장되는 테이블

 

 

해시 테이블

 

 

해시 충돌(collision)
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변화하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌이 발생할 수 있다.

 

 

해시테이블의 장점
적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다.
해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑함으로써
작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다.

 

 

충돌을 극복하기 위한

 

체이닝(chaining)
한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는다.
해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 장식으로 구현(연결 리스트)
유연하다는 장점이 있으나 메모리 문제를 야기

 

선형 탐사(linear probing)
최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예를 들면 1)을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스한다.
cluster(클러스터) 현상이 매우 잘 발생한다.

제곱 탐사(Quadratic probing)
선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.
서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생

 

이중 해싱(Double Hashing)
클러스터 방지를 위해, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용

 

재해싱(Rehashing)
해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것