Hash Table이란?

해시 테이블(해시 맵이라고도 합니다)은 키, 값 쌍을 저장하고 있는 자료 구조입니다.(연관배열 구조(associative array) 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환합니다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지합니다.

해시테이블의 구성

키(key)

고유한 값이며, 해시 함수에 입력되어 함수로직에 의해 일정한 값의 형태로 바뀌게 된다.

해시 함수Hash Function

키(key)를 받아 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이는 가지는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경한다.

해시함수의 특징

1.어떤 입력 값에도 항상 고정된 길이의 해시 값을 출력한다.
2.입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.(눈사태 효과)
3.출력된 결과 값을 토대로 입력 값을 유추할 수 없다.
4.입력 값은 항상 동일한 해시 값을 출력한다.

해시(Hash)

해시 함수(Hash Function)에서 반환되는 값이며, 저장소(Bucket, Slot)에서 값과 매칭되어 저장된다.

값(value)

저장소(Bucket, Slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야한다.

저장소(Bucket, Slot)

저장할 값(value)이 저장되어지는 장소이다.

Collision

Hash Function을 통해서 해시값을 얻어 bucket에 데이터를 저장하는 과정에서 해시값이 동일할 경우 같은번지수의 주소에 데이터를 저장을 시도하게 된다 이럴때 발생하는 것을 충돌(collision)이라한다.
Hash Function의 결과값이 절대 일치하지 않도록 타이트하게 설정해 줘야 한다.하지만 현실적으로 그것이 불가능하다면 해결할 수 있는 방법이 있어야 되지 않을까?

아래 그림에서 John Smith라는 키 값과 Sandra Dee라는 키값은 Hash Function을 통해 152라는 동일한 결과(Hash)를 얻어 bucket에 데이터를 저장할때 충돌이 발생한다

collision solutions

1. 열린 어드레싱 방법 ( Open Addressing Method)

선형 조사법(Linear Probing)

: 충돌이 발생했을때 옆자리가 비어있는지 살펴보고, 비어 있을경우 그자리에 대신 저장하는 방식.

이중 해시(Double Hash)

: 미리 함수를 두개를 준비해서 처번째 함수를 지속적으로 사용하다, 충돌이 발생하면 두번째 함수를 사용해서 다른 해시값을 갖도록 한다.

재해싱 (Rehasing)

: Hash Table 크기를 늘리고 새로운 Hash Table에 모든 데이터를 이주시킨다.

2. 닫힌 어드레싱 방법(Closed Addressing Method)

체이닝(Chaining)

: 위 그림에서 충돌이 발생한 후 entries에 Linked List 등으로 연결하는 방식이다.

Hash Table Code

아래코드는 JavaScript이고 JavaScript에서 배열의 크기는 동적이기 때문에 배열의 크기를 한정적으로 만들기 위해 "LimitedArray"라는 함수는 따로 만어 주어야 한다.또한 Hash Function도 만든이 마음이기 때문에 해당 코드에 적용되어 있지 않다.

class HashTable {
 constructor() {
   this._size = 0;
   this._bucketNum = 8;
   this._storage = LimitedArray(this._bucketNum);
 }
	//주어진 키와 값을 저장합니다.
 insert(key, value) {
   if(this._size >= this._bucketNum * 0.75){
     this._resize(this._bucketNum * 2);
   }
   const index = hashFunction(key, this._bucketNum);
   let bucket = [];
   let tuple = [key,value];
   if(!this._storage[index]){
     bucket.push(tuple);
     this._storage[index] = bucket;
   }else{
     //index가 존재 할 경우 덮어쓰기
     for(let element of this._storage[index]){
       if(element[0] === key){
         element[1] = value;
       }else{
         this._storage[index].push(tuple);
       }
     }
   }
   this._size ++;
 }
	//주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
 retrieve(key) {
   const index = hashFunction(key, this._bucketNum);
   if(this._storage[index]){
     for(let element of this._storage[index]){
       if(element[0] === key){
         return element[1];
       }
     }
   }
 }
	//주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
 remove(key) {
   if(this._size <= this._bucketNum * 0.25){
     this._resize(this._bucketNum / 2);
   }
   const index = hashFunction(key, this._bucketNum);
   let bucket = this._storage[index];
   let result ;
   if(bucket){
     for(let element of bucket){
       if(element[0] === key){
         result = bucket.splice(bucket.indexOf(element),1);
       }
     }
   }
   this._size--;
   return result;
 }
	//해시 테이블의 스토리지 배열을 newBucketNum으로 리사이징하는 함수입니다. 
	//해시 테이블에 저장된 key-value 쌍이 bucketNum의 75%를 넘는 경우 bucketNum을 2배로 늘리고, 
	//25%보다 작아지는 경우 bucketNum을 절반으로 줄입니다. 
	//리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 
	//구현 후 HashTable 내부에서 사용하시면 됩니다.
 _resize(newBucketNum) {
   let perStorage = this._storage; // 구
   this._bucketNum = newBucketNum;
   this._storage = LimitedArray(newBucketNum)// 신 
   //구 > 신 이주
   for(let i in perStorage){
     this._storage[i] = perStorage[i]
   }
 }
}