[직접 주소 테이블]

• 직접 주소 테이블은 value가 곧 key
• 직접 주소 테이블은 값에 접근하기는 편하지만 공간 효율이 좋지 않다는 단점

Array(91) [
 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 90]

• 적재율이 낮다
• 의미있는 값이 3 10 91 뿐이고 3 10 91의 index에 할당 되어있다
• 3/91의 적재율
• 할당 안된 부분은 0 으로 되어있고 공간만 차지하는중

[해쉬 테이블]

• 해시 테이블은 직접 주소 테이블처럼 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수(Hash Function)이라는 것에 한번 통과

const myTableSize = 5; // 딱 5개의 공간만 할당
const myHashTable = new Array(myTableSize);

function hashFunction (key) {
  // 들어온 값을 테이블의 크기로 나눠주고 나머지를 반환하면 된다.
  return key % myTableSize;
}

myHashTable[hashFunction(1991)] = 1991;
myHashTable[hashFunction(1234)] = 1234;
myHashTable[hashFunction(5678)] = 5678;

console.log(myHashTable); // [empty, 1991, empty, 5678, 1234]

• 충돌의 문제가 있다

hashFunction(1991) // 1
hashFunction(6) // 1

[충돌 문제 해결]

• 최대한 골고루 퍼져서 풀방이 되도록 해야한다

개방 주소법

• 충돌나면 어딘가 옆에 박는 방법

• 선형 탐사법

  • 충돌나면 바로 옆에 박기
  • 데이터의 밀집도가 높아져서 충돌이 연쇄로 발생함

• 제곱 탑사법

  • 충돌나면 제곱으로 늘려나면서 박기
  • 선형 탐사보단 괜찮긴 하지만 1이 계속나오면 계속 결국 박게 된다

• 이중해싱(Double Hashing)

  • 해시를 이중으로 만든다
    • 하나는 최초 인덱스용으로 만들고 하나는 충돌났을때 얼마나 이동할지 계산하는 용도로 만든다

  const myTableSize = 23; // 테이블 사이즈가 소수여야 효과가 좋다
  const myHashTable = [];
  
  const getSaveHash = value => value % myTableSize;
  
  // 스텝 해시에 사용되는 수는 테이블 사이즈보다 약간 작은 소수를 사용한다.
  const getStepHash = value => 17 - (value % 17);
  
  const setValue = value => {
      let index = getSaveHash(value);
      let targetValue = myHashTable[index];
      while (true) {
          if (!targetValue) {
              myHashTable[index] = value;
              console.log(`${index}번 인덱스에 ${value} 저장! `);
              return;
          }
          else if (myHashTable.length >= myTableSize) {
              console.log('풀방입니다');
              return;
          }
          else {
              console.log(`${index}번 인덱스에 ${value} 저장하려다 충돌 발생!ㅜㅜ`);
              index += getStepHash(value);
              index = index > myTableSize ? index - myTableSize : index;
              targetValue = myHashTable[index];
          }
      }
  }
  

  • 소수를 써서 해싱 반복 안하도록 한다