해싱(해싱이란?, 해시함수)

데이터를 탐색할 때, 원하는 정보를 찾기 위해서 저장된 값들과 키 값을 비교하면서 찾아나가게 된다.
이렇게 키 값을 비교하는 과정에서 시간이 소요되게 되는데,
해싱을 통하여 해당 시간을 줄일 수 있다.

해싱은 키 값에 특정 연산 방법 등을 사용하여 키 값으로 직접 접근이 가능하도록 구성해준다.

그리고 이렇게 해싱을 시키는 과정에서 해시함수가 사용된다.

간단하게 3가지 정도의 방법을 소개하려고 한다.

우선 해시 테이블은 8의 길이를 가진 이차원 배열로 생각했다.
(해시함수를 통과하였지만, 해당 위치에 이미 데이터가 있는 상황을 '충돌'이라고 표현한다. 이 충돌을 해결하거나, 우회하거나, 다르게 사용하는 방법들에는 몇 가지가 존재하는데 일단 깊게 생각하지는 않고 이차원 배열로 잡았다.)

1. 제산 잔여법

let hArr = Array.from({ length: 8 }, () => []);

function a(numList) {
  for (let i = 0; i < numList.length; i++) {
    let b = numList[i] % 8;
    hArr[b].push(numList[i]);
  }
  return console.log(hArr);
}

제산 잔여법은 키 값을 특정 값으로 나누어 나머지에 해당하는 인덱스 위치로 분배해주는 방법이다.

2. 비닝

function b(numList) {
  for (let i = 0; i < numList.length; i++) {
    hArr[i % 8].push(numList[i]);
  }
  return hArr;
}

비닝은 단순하게 키 값의 범위를 나누어 저장한다.
예를 들어 키 값이 0~79의 범위를 가지고 있고
테이블의 길이가 8일 때,
0~7은 해시 테이블의 0번 슬롯 ... 와 같이 분배된다.

3. 중간 제곱법

let hArr2 = Array.from({ length: 100 }, () => []);

function c(numList) {
  for (let i = 0; i < numList.length; i++) {
    let b = String(numList[i] * numList[i]).split('');
    let c = b.splice(Math.floor(b.length / 2) - 1, 2).join('');
    hArr2[c].push(numList[i]);
  }
  return hArr2;
}

설명만 보고... 막 짜본거라 코드가 너무 지저분하다...ㅠ

아래는 챗gpt를 통해서 만든 중간 제곱법 해시 함수이다.

// 중간 제곱법 해시 함수 구현
function middleSquareHash(input, length) {
    const squared = input * input;
    const squaredStr = squared.toString();
    
    const middle = Math.floor(squaredStr.length / 4);
    const middleDigits = squaredStr.slice(middle, middle + length);
    
    return parseInt(middleDigits) % length;
}

// 테스트
const inputValue = 123456; // 입력 값
const tableSize = 100;     // 해시 테이블 크기

이상!