[javascript] Hash table , 해시테이블 (1)

포스팅 전 주저리 : 오늘 너무 포식한 것 같다. 자스민 사람들 중 생일 맞은 분이 치킨 한 턱 쏘시고 다른 분이 아이스크림케잌까지 먹었다... 다이어트는 물건너 간 느낌이다. ㅋㅋㅋㅋ .

 

HashTable 이란 ?  

해쉬테이블은 value가 key와 매핑되어 O(1)의 시간 복잡도를 가지고 value를 서치할 수 있는 자료구조이다. 

 

Hash Function 이란 ? 

HashTable은 key를 이용해서 value를 서치한다. 그런데 이 key는 string 타입으로 되어있기 때문에 배열에서 해당 키를 사용하려면 number형태로 만들어 index 처럼 사용해야 한다. 

 

쉽게 생각해서 해당 key(string)가 배열에 index로 쓰게 숫자형태로 변환한다고 생각하면 된다. 그런데 여기에는 큰 문제가 있다. 바로 2개의 다른 스트링을 저장할 때 같은 해시값으로 저장 될 수 있어 충돌(Collision)이 일어난다는 점이다. 잘만든 해시함수를 이용하면 충돌은 적어질 수는 있으나 비충돌 확률이 0이 될 수는 없다. 

 

그래서 이를 해결하기 위해 두가지 방식으로 이 충돌을 우회 한다. 바로 Separate Chaning 방식과 Open Adress 방식이다. 

 

Open Adress 방식

Open Adress방식은 해당 key를 해시 함수로 변환한 해시값 말고 다른 해시값의 배열의 빈 공간에 넣는 방식을 말 한다. 

 

Open Adress방식은 3가지의 세부방법으로 다시 나뉘는데 이는 다음과 같다. 

 

linear Probing (선형 탐사)

 

해시함수의 결과를 4의 배수 혹은 6의 배수로 하면 다음과 같이 배열의 빈공간들이 남을 것이다. 

 

 

그리고 충돌이 일어날 경우 해당 index 옆 빈공간에 추가한다.  

 

 

아쉽게도 선형탐사 방식을 사용하면 삽입과 탐색, 삭제의 연산들이 O(1)에서 O(1 + a) 가 될 수 있다. 

 

Quadratic Probing (제곱 탐사)

선형 탐사의 경우 해당 hash값의 2배 전까지의 방들을 탐사했다면 제곱탐사는 해당 hash값의 제곱의 수를 이용하여 빈방을 탐색한다. 

 

해시 펑션의 결과로 2가 나왔는데 데이터가 있다면 4번방을, 빈방이 아니라면 4의 제곱인 16번 방을 탐색한다.

 

Double Hashing (이중 해싱)

 

이중 해싱은 해시함수의 첫번째 로직으로 생성된 처음 해시값을 지정 하고 두번째 로직으로 해당 hash값이 충돌 했을때 새로운 해쉬값을 만들어내 충돌을 방지한다. 

 

Seperate Chaning 

 

배열에 저장할때 linked-list 형태로 저장하여 해쉬값이 중복이 일어난다면 해당 해쉬값에 해당하는 노드 뒤에 새로운 노드를 추가하는 방식이다. 

 

대표적인 해시함수 

인터넷으로 찾아보니 대표적인 해시 함수로 나누기 방법과 곱하기 방법이 있는 듯 하다. 

 

나누기 방법

 

들어온 key 값을 배열의 길이로 나머지 연산을 한 나머지 값을 해쉬값으로 사용하는 것이다. (mod 연산이라고 불린다.) 

 

let array = []; //해당 배열은 size 변수만큼 add할 수 있다고 가정한다.
let size = 20; 

devideHashFunc(key){
	return key.length % size;
}

 

곱하기 방법

 

들어온 key 값의 길이를 일정한 0이상 1이하의 소수를 곱한 뒤 배열의 길이를 곱한다. 이후 해당 값에서의 특정한 자리수값들을 해쉬값으로 사용하는 방법이다. 

 

let array =[];
let size = 100;

MultipleHashFunc(key){
	let random = 0.24252;
    let prevhash = (((key * random) * size).toFixed(5)).toString();
    let hashValue;
    for(let i = 0; i<2; i++){
    	hashValue += prevhash[i];
    }
    
    hashValue = parseInt(hashValue);
    
    return hashValue;
}