Javascript 자료구조 04 : Hash Table 충돌방지

protect-me·2021년 4월 8일

Chaining Hash Table JavaScript close hashing closeHashing linked list chaining lonear probing open hashing openHashing 선형탐사 자료구조 체이닝 충돌방지 해쉬테이블

자료구조

목록 보기

4/7

Hash Table의 충돌 방지 방법은 크게
Open Hashing, Close Hashing로 나누어 볼 수 있다.

충돌이 발생할 경우 각각,
Open Hashing은 해시 테이블 밖에 공간을 확보해서 저장하며,
Close Hashing은 해시 테이블 내에 빈 공간을 찾아 저장한다.
아래에서는 각각의 대표 사례를 위주로 구현하였다.

Open Hashing 中 Chaining(체이닝) 기법

충돌 발생 시, Hash Table Slot의 바깥으로 Linked List Chaining을 이음.
참고: 새 데이터를 tail이 아닌 head에 할당함으로써 Linked List의 마지막 index를 찾는 자원을 아낄 수 있음

Open Hashing - Chaining 구현

// Node 구현
function Node(key, value) {
  this.key = key;
  this.value = value;
  this.next = null;
}
//
// Hash Table 생성 - 최대 8자리(0~7)
const hashTable = new Array(8).fill(0);
//
// Hashing Function - key.length를 8로 나눈 값을 return
function hashFunc(key) {
  return key.length % 8;
}
//
// Hashing
function hashing(key, value) {
  const address = hashFunc(key); // Hashing Function
  const node = new Node(key, value);
  if (hashTable[address]) {
    // 기존에 데이터가 있을 경우
    // 새 데이터를 head에 넣고 next에 기존 데이터를 이어준다.
    const current = hashTable[address];
    hashTable[address] = node;
    hashTable[address].next = current;
  } else {
    // 기존에 데이터가 없을 경우
    // 새 데이터를 head로 넣어준다.
    hashTable[address] = node;
  }
}
//
// getData 구현 
function getData(key) {
  const address = hashFunc(key); // Hashing Function
  let current = hashTable[address]; // current 세팅
  while (current) {
    if (current.key === key) break;
    current = current.next;
  }
  return current.value;
}

테스트코드 및 결과화면

// 테스트코드
hashing("first", "chair");
hashing("second", "desk");
hashing("third", "coffee"); // "first"와 충돌 발생
//
console.log(getData("first")); // "chair"
console.log(getData("second")); // "desk"
console.log(getData("third")); // "coffee"

hashTable 펼쳐보기

console.log(hashTable);
//
(8) [0, 0, 0, 0, 0, Node, Node, 0]
0: 0
1: 0
2: 0
3: 0
4: 0
5: Node
   key: "third"
   value: "coffee"
   next: Node
         key: "first"
         value: "chair"
         next: null
6: Node
   key: "second"
   value: "desk"
   next: null
7: 0

Close Hashing 中 Linear Probing(선형 탐사) 기법

충돌 발생 시, Hash Table 안에 빈 slot을 찾아 데이터를 삽입함.

// Hash Table 생성 - 최대 8자리(0~7)
const hashTable = new Array(8).fill(0);
//
// Hashing Function - key.length를 8로 나눈 값을 return
function hashFunc(key) {
  return key.length % 8;
}
//
// Hashing
function hashing(key, value) {
  const address = hashFunc(key); // Hashing Function
  if (hashTable[address]) {
    // 기존 데이터가 있을 경우
    let flag = true;
    // i를 address+1부터 시작해서
    for (let i = address + 1; i !== address; i++) {
      // i가 hashTable의 length와 같으면 i를 다시 0으로 내림.
      // i는 address+1 부터 시작해서 hashTable의 끝까지 돌고,
  	  // 다시 0부터 시작해서 address-1까지 반복
      if (i === hashTable.length) i = 0;
      if (!hashTable[i]) {
        hashTable[i] = [key, value];
        flag = false;
        break;
      }
    }
    // flag가 true이면 데이터를 저장하지 못했다는 뜻으로 -1을 반환
    if (flag) return -1;
  } else {
    // 기존에 데이터가 없을 경우
    // key와 value 값을 배열로 저장
    hashTable[address] = [key, value];
  }
}

테스트코드 및 결과화면

hashing("1111", "chair");
hashing("2222", "chair");
hashing("3333", "chair");
hashing("4444", "chair");
hashing("5555", "chair");
hashing("6666", "chair");
hashing("7777", "chair");
hashing("8888", "chair");
console.log(hashTable);
//(8) [Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2)]
0: (2) ["5555", "chair"]
1: (2) ["6666", "chair"]
2: (2) ["7777", "chair"]
3: (2) ["8888", "chair"]
4: (2) ["1111", "chair"]
5: (2) ["2222", "chair"]
6: (2) ["3333", "chair"]
7: (2) ["4444", "chair"]
length: 8

슬롯이 모두 찼을 경우

console.log(hashing("9999", "chair")); // -1
console.log(hashTable);
// 슬롯이 모두 찼을 경우 새 데이터는 저장되지 않고 -1을 반환함.
// (8) [Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2)]
0: (2) ["5555", "chair"]
1: (2) ["6666", "chair"]
2: (2) ["7777", "chair"]
3: (2) ["8888", "chair"]
4: (2) ["1111", "chair"]
5: (2) ["2222", "chair"]
6: (2) ["3333", "chair"]
7: (2) ["4444", "chair"]