❓ 해시 테이블(Hash Table)

해시테이블을 알아가기 전에 해시 함수에 대해 알아보자.

✅ 해시 함수

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

✅ 해시 함수 특성

• 압축성 : 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질
• 효율성 : 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질
• 저항성 : 결과값을 바탕으로 입력값을 찾는 것이 불가능한 성질

❓ 해시테이블이란?

• Hash 함수를 사용하여 평균 O(1) 시간 복잡도로 특정 값을 신속하게 찾는 자료구조이다.

// djb2 hash size
const HASH_SIZE  = 1013;

// Element() : key, value 저장을 위한 생성자
function Element(key, value) {
  this.key = key;
  this.value = value;
}

// HashTable() : 생성자
function HashTable() {
  this.table = new Array(HASH_SIZE);
  this.length = 0;
}

// hashCode() : 해시 함수
HashTable.prototype.hasCode = function (key) {
  // djb2 hash function
  let hash = 5381 // seed
  
  for(let  i =0; i < key.length; i++){
    hash = hash * 33 + key.charCodeAt(i);
  }
  
  return hash % HASH_SIZE;
}

해시테이블을 사용하면 충돌이 일어난다. 예시로 만약 Alice와 Bob이라는 데이터가 순서대로 들어간다고 했을 때, 둘 다 index값을 2를 가지면 제일 마지막에 들어온 데이터가 index 2에 들어가게 되면서 그 전 데이터는 사라지게 될 것이다. 이러한 현상을 충돌(collision)이라고 한다.

✅ 충돌(Collision) 해결 방법

• 해시 함수 변경 : 더큰 숫자의 공간과 Modular 산술 값을 이용해 충돌 최소화
• 자료구조 확장 : Open Addressing Method(선형 조사법, 이중 해시), Close Adderessing Method(체이닝)

close Addressing Method(체이닝)에서는 index가 같을 때 linkedList로 저장을 한다.

✏️ 구현 메서드(Method)

📗 put() : 데이터 추가

HashTable.prototype.put = function (key, value) {
  let index = this.hashCode(key);
  console.log(`key : ${key} -> index : ${index}`);
  
  // 만약 index에 데이터가 있으면 false 반환
  if (this.table[index] !== undefined) {
    return false;
  }
  
  this.table[index] = new Element(key, value);
  this.length++;
  
  return true;
}

📗 get() : 데이터 조회

HashTable.prototype.get = function (key) {
   return this.table[this.hashCode(key)];
}  

📗 remove() : 데이터 삭제

HashTable.prototype.remove = function (key) {
  let element = this.table[this.hashCode(key)];
  
  if (element !== undefined){
    delete this.table[this.hashCode(key)];
    this.length;
  }
}

📗 clear() : 초기화

HashTable.prototype.clear = function () {
  this.table = new Array(HASH_SIZE);
  this.length = 0;
}

📗 size() : 크기 반환

HashTable.prototype.size = function () {
  return this.length;
}

📗 getBuffer() : 데이터 셋 반환

HashTable.prototype.getBuffer = function () {
  let array = [];
  
  for(let i = 0; i < this.table.length; i++){
    if (this.table[i]) {
      array.push(this.table[i]);
    }
  }
  
  return array;
}

📗 print() : 데이터 셋 출력

HashTable.prototype.print = function () {
  for (let i = 0; i < this.table.length; i++){
    if (this.table[i]){
      console.log(i + " -> " + this.table[i].key + ": " + this.table[i].value);
    }
  }
}