❓ 체이닝 해시 테이블(Chaining Hash Table)

• 별도의 자료구조인 연결 리스트(Linked List)를 병합 사용하여 Hash 충돌을 해결한 해시 테이블 기반 자료구조이다.

const HASH_SIZE = 37;

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

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

// hashCode() : 해시 함수
ChainingHashTable.prototype.hashCode = function (key) {
  let hash = 0;
  
  for(let i = 0; i < key.length; i++){
    hash += key.charCodeAt(i);
  }
  
  return hash % HASH_SIZE;
}

체이닝 해시 테이블에서 사용하는 연결 리스트 생성자와 관련 메서드들은 모듈로 가지고 와서 사용한다. 연결 리스트 관련 글은 전에 작성한 글에서 참고하면 된다.

연결리스트 글 URL : https://velog.io/@tjdwn9753/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8LinkedList

---

✏️ 구현 메서드(Method)

📗 clear() : 초기화

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

📗 size() : 크기 반환

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

📗 put() : 데이터 추가

ChainingHashTable.prototype.put = function () {
  let index = this.hashCode(key);
  console.log(`key : ${key} -> index : ${index}`);
  
  if (this.table[index] === undefined){
    this.table[index] = new LinkedList();
  }
  this.table[index].append(new Element(key, value));
  this.length++;
  
  return true;
}

📗 getBuffer() : 데이터 셋 반환

ChainingHashTable.prototype.getBuffer = function () {
  let array = [];
  
  for (let i = 0; i < this.table.length; i++){
    if(this.table[i]){
      let current = this.table[i].head;
      
      do {
        array.push(current.data);
        current = current.next;
      } while (current); // null 이면 false
    }
  }
  
  return array;
}

📗 print() : 데이터 셋 출력

ChainingHashTable.prototype.print = function () {
  for (let i = 0; i < this.table.length; i++){
    if (this.table[i]) {
      let current = this.table[i].head;
      process.stdout.write(`#${i}`);
      
      do {
        process.stdout.write(` -> ${current.data.key}: ${current.data.value}`);
        current = current.next;
      } while (current);
      console.log("");
    }
  }
}

📗 get() : 데이터 조회

ChainingHashTable.prototype.get = function (key) {
  let index = this.hashCode(key);
  
  if(this.table[index] !== undefined && !this.table[index].isEmpty()){
    let current = this.table[index].head;
    
    do {
      if (current.data.key === key){
        return current.data.value;
      }
      
      current = current.next;
    } while (current);
  }
  
  return undefined;
}

📗 remove() : 데이터 삭제

ChainingHashTable.prototype.remove = function (key) {
  let index = this.hashCode(key);
  let element = undefined;
  
  if (this.table[index] !== undefined) {
    let current = this.table[index].head;
    
    do {
      if (current.data.key === key){
        element = current.data;
        this.table[index].remove(current.data);
        this.length--;
        
        if (this.table[index].isEmpty()) {
          delete this.table[index];
        }
      }
      current = current.next;
    } while (current);
  }
}