[선형] 17. 체이닝 해시테이블

08 Oct 2021 in 자료구조 on 선형

목차
- 1. 체이닝 해시테이블
- 2. 체이닝 해시테이블 구현하기

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

체이닝

별도의 자료구조인 연결 리스트를 병합 사용하여 Hash 충돌을 해결한 해시테이블 기반 자료구조
객체 초기화 / 크기 반환 : ChainingHashTable.clear(), ChainingHashTable.size()
전체 데이터 반환, 전체 데이터 출력 : ChainingHashTable.getBuffer(), ChainingHashTable.print()
데이터 추가 / 삭제 / 반환 : ChainingHashTable.put(), ChainingHashTable.remove(), ChainingHashTable.get()

3. 구현하기

연결리스트 모듈 가져오기 위해 import 추가
연결리스트 파일은 .mjs (module javascript) 확장명
연결리스트 파일 모듈 export export { LinkedList };

기존 Hash Table 과 동일한 부분

import { LinkedList } from "./LinkedList.mjs"

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;
  // loselosehash
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % HASH_SIZE;
};

// clear() : 초기화
ChainingHashTable.prototype.clear = function () {
    this.table = new Array(HASH_SIZE);
    this.length = 0;
};

// size() : 크기 변환
ChainingHashTable.prototype.size = function () {
    return this.length;
};

let cht = new ChainingHashTable();
console.log(cht) //ChainingHashTable { table: [ <5 empty items> ], length: 0 }

let ll = new LinkedList()
ll.append(new Element("Ana", 172))
console.log(ll)
// LinkedList {
//   head: Node { data: Element { key: 'Ana', value: 172 }, next: null },
//   length: 1
// }

put()

// put() : 데이터 추가
ChainingHashTable.prototype.put = function (key, value) {
  // 1. 해당 인덱스 값 존재 여부 확인
  // 2. 비어 있으면 ll 새로 만들어준다
  // 3. 비어있지 않다면 ll에 append 해준다

  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;
};

let cht = new ChainingHashTable();
console.log(cht); //ChainingHashTable { table: [ <5 empty items> ], length: 0 }

cht.put("Ana", 150); //collision a
cht.put("Donnie", 170); //collision a
cht.put("Sue", 140); //collision b
cht.put("Jamie", 130); //collision b
cht.put("Paul", 110); //

// key: Ana -> index: 13
// key: Donnie -> index: 13
// key: Sue -> index: 5
// key: Jamie -> index: 5
// key: Paul -> index: 32

console.log(cht)
// ChainingHashTable {
//   table: [
//     <5 empty items>,
//     LinkedList { head: [Node], length: 2 },
//     <7 empty items>,
//     LinkedList { head: [Node], length: 2 },
//     <18 empty items>,
//     LinkedList { head: [Node], length: 1 },
//     <4 empty items>
//   ],
//   length: 5
// }

getBuffer(), print()

// 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);
    }
  }
  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("");
    }
  }
};

let cht = new ChainingHashTable();
console.log(cht); //ChainingHashTable { table: [ <5 empty items> ], length: 0 }

cht.put("Ana", 150); //collision a
cht.put("Donnie", 170); //collision a
cht.put("Sue", 140); //collision b
cht.put("Jamie", 130); //collision b
cht.put("Paul", 110); //

cht.print()
// #5-> Sue: 140-> Jamie: 130
// #13-> Ana: 150-> Donnie: 170
// #32-> Paul: 110

console.log(cht.getBuffer())
// [
//   Element { key: 'Sue', value: 140 },
//   Element { key: 'Jamie', value: 130 },
//   Element { key: 'Ana', value: 150 },
//   Element { key: 'Donnie', value: 170 },
//   Element { key: 'Paul', value: 110 }
// ]

get()

// 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;
};

let cht = new ChainingHashTable();
console.log(cht); //ChainingHashTable { table: [ <5 empty items> ], length: 0 }

cht.put("Ana", 150); //collision a
cht.put("Donnie", 170); //collision a
cht.put("Sue", 140); //collision b
cht.put("Jamie", 130); //collision b
cht.put("Paul", 110); //

console.log(cht.get("Ana")) //150
console.log(cht.get("Sue")) //140
console.log(cht.get("Jo")) //undefined

remove()

// remove() : 데이터 삭제
ChainingHashTable.prototype.remove = function (key) {
  // 인덱스에 요소가 있는지 확인
  // 동일한 key 가 있는지 확인
  // remove
  // isEmpty 여부 확인
  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);

    return element;
  }

  return undefined;
};

let cht = new ChainingHashTable();

cht.put("Ana", 150); //collision a
cht.put("Donnie", 170); //collision a
cht.put("Sue", 140); //collision b
cht.put("Jamie", 130); //collision b
cht.put("Paul", 110); 

cht.print();
console.log(cht.remove("Sue")); //Element { key: 'Sue', value: 140 }
cht.print();
console.log(cht.remove("Jamie")); //Element { key: 'Jamie', value: 130 }
cht.print();