[자료구조] Hash Table 03

calendar_todayApril 08, 2021
local_offer#자료구조#algorithm#javascript

Linear Probing 기법

폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 저장공간 활용도를 높이기 위한 기법

const hashTable = Array.from(Array(8)).map(() => 0);
const getKey = data => {
  return `${data.charCodeAt(0)}${data.charCodeAt(1)}${data.charCodeAt(2)}`;
};
const hashFunction = key => {
  return key % 8;
};

const saveData = (data, value) => {
  const index = getKey(data);
  const hashAddress = hashFunction(index);

  if (!hashTable[hashAddress]) {
    hashTable[hashAddress] = [index, value];
  } else {
    for (let i = hashAddress; i < hashTable.length; i++) {
      if (hashTable[i][0] === index) {
        hashTable[i] = [index, value];
        return;
      } else if (!hashTable[i]) {
        hashTable[i] = [index, value];
        return;
      }
    }
  }
};

const readData = data => {
  const index = getKey(data);
  const hashAddress = hashFunction(index);

  if (hashTable[hashAddress][0] === index) {
    return hashTable[hashAddress][1];
  } else {
    for (let i = hashAddress + 1; i < hashTable.length; i++) {
      if (hashTable[i][0] === index) {
        return hashTable[i][1];
      }
    }

    return null;
  }
};

saveData("react", "리액트");
saveData("svelte", "스벨트");
saveData("vue", "뷰");

console.log(hashTable);

console.log(readData("svelte"));
console.log(readData("angular"));

빈번한 충돌을 개선하는 방법

충돌을 해결 할 수 있는 여러 기법들이 있지만, 사실 충돌이 덜 발생하는 것이 제일 좋다.

해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대 가장 간단하면서 일반적인 방법

만약 8개의 공간을 가진 해쉬 테이블에 50%(4개)의 데이터를 저장한다면 충돌이슈가 있을 수 있기 때문에 저장공간을 두 배로(16개) 늘린다.

참고: 해쉬 함수와 키 생성 함수

유명한 해쉬 함수들이 있음: SHA(Secure hash Algorithm, 안전한 해시 알고리즘) 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

시간 복잡도

  • 일반적인 경우(충돌이 없을 경우) O(1)
  • 최악의 경우(충돌이 모두 발생하는 경우)는 O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1) 이라고 말할 수 있음

©koal, Built with Gatsby-blog-starter