🏓 Hash Table

Table 이모지를 검색하니 Table Tennis가 나오네요.🤣

---

먼저, 위키피디아의 그림을 같이 봅시다.

전화번호부에 있는 사람을 Hash Table에 저장할 때의 그림인데요.

keys(이름)을 hash function으로 indexing하여 bucket의 각 index에 value를 넣어줍니다.

그런데 공간을 무한정으로 생성할 수 없으니 수에 제한이 있습니다.

만약 80%만큼 채워진다면 2배로 늘리고, 25%만큼 줄었다면 절반으로 줄이는 것이죠.

또, 해싱을 하면 동일한 index를 받을 수도 있고, 이때 충돌이 발생하여 중복이 생깁니다.

예를 한번 들어볼까요?

최대 공간을 10으로 제약합니다. (무한정으로 생성해놓으면 당연히 비효율적이니까요.)

그럼 해시함수로 인덱싱을 할 수 있는 가짓수의 범위는 10가지 이내가 됩니다.

아무리 다양한 숫자를 넣어도 최대 10개만 들어가니까요.

그렇다면 해시함수도 최대 공간의 제약수만큼 1~10까지만 생성을 해봅시다.(간략하게)

그럼 확률적으로 '신짱구'와 '홍길동'의 인덱스가 같은 확률도 있겠죠?

그럼 같은 인덱스가 중복되어 충돌 문제가 발생되는 것입니다.

왜 조건을 이렇게 많이 추가했냐면, 원래는 해시 함수의 모양에 따라 확률이 아주 적어질 수 있으니까요!

이를 해결 하기 위한 방법이 2가지가 있습니다.

1. Separate chaining

entries 부분이 추가되었죠? 이렇게 동일한 index를 받아 충돌이 발생하면

해당 index가 가리키고 있는 Linked List에 노드를 추가하여 값을 추가합니다.

이렇게 하면 데이터를 추가할 때, 충돌이 발생해도 데이터 삽입에 문제가 없습니다.

데이터 추출 시에는 key에 대한 index로 Linked List를 검색하여 데이터를 추출합니다.

2. Open Addressing

index에 대한 충돌에 대해 Linked List를 사용하여 추가적인 메모리 공간을 사용하지 않고,

hash table array의 빈 공간을 사용합니다.

Separate chaining 방식에 비해서 메모리를 덜 사용합니다.

Open Addressing을 구현하는 방식인 Linear Probing을 간단히 알아봅시다.

3. Linear Probing

[한줄요약] : 넣고 싶은데 자리가 없으면 다음 칸에 넣는 방법.

index에 대해 충돌이 발생했을 때, index 뒤의 버킷 중에 빈 버킷을 찾아 데이터를 넣는 방식입니다.

key % 10 해쉬 함수를 사용하는 Hashtable이 있을때, 아래 그림에서는 충돌이 발생하지 않았습니다.

그런데, 여기에 11을 key로 하는 데이터를 넣으면 key가 1인 data와 충돌이 발생합니다!

Linear Probing은 아래 그림처럼 충돌이 발생한 index[1] 뒤의 버킷에 빈 버킷이 있는지 검색합니다.

2번 버킷은 이미 index[2]가 들어있기 때문에 3번 버킷에 저장을 합니다.

4. pseudo Code

pseudo Code를 작성해봅시다!

/* pseudo Code */
해시테이블 {
  limit, bucket
  
  method: insert {
    해시함수로 인덱스를 가져온다.
    인덱스에 맞춰 버킷에 저장한다.
    만약 limit의 80%가 차면 리밋을 확장한다.
  }
  
  method: retrive {
    해시함수로 구한 인덱스에 맞춰 값을 찾는다.
  }
  
  method: remove {
    해시함수로 구한 인덱스에 맞춰 버킷을 돌면서 동일하면 제거한다.
  }
}

해시함수 { }

5. Hash table Code

코드는 두 가지로 나뉩니다.

1. Hash Table Helper
2. Hash Table

5-1. Hash Table Helper

해시 테이블 헬퍼 코드가 주어집니다. (이렇게 친절할수가...)

수정을 해야할 수 있겠지만 일단 그대로 사용해봅니다.

간단하게 읽어보면 제한된 공간을 생성하는 클래스, 해시함수가 있네요!

const LimitedArray = function(limit) {
  const storage = [];

  const limitedArray = {};
  limitedArray.get = function(index) {
    checkLimit(index);
    return storage[index];
  };
  limitedArray.set = function(index, value) {
    checkLimit(index);
    storage[index] = value;
  };
  limitedArray.each = function(callback) {
    for (let i = 0; i < storage.length; i++) {
      callback(storage[i], i, storage);
    }
  };

  var checkLimit = function(index) {
    if (typeof index !== "number") {
      throw new Error("setter requires a numeric index for its first argument");
    }
    if (limit <= index) {
      throw new Error("Error trying to access an over-the-limit index");
    }
  };

  return limitedArray;
};

const getIndexBelowMaxForKey = function(str, max) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash &= hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};

5-2. Hash Table

hashTableHelper를 불러와서 사용합니다.

크기를 미리 지정하고, 각 메소드를 prototype에 구현합니다.

각 구성을 분석해봅시다.

_limit : 크기 제한
_storage : bucket(버킷)
insert : 해시함수로 인덱스를 구하여 버킷에 저장합니다.
retrive : 해시함수로 인덱스를 구하여 버킷에서 가져옵니다.
remove : 해시함수로 인덱스를 구하여 버킷을 돌면서 찾아 삭제합니다.

아직 충돌문제를 해결하지 못하였습니다.

추후 시간에 날 때, 연구해보도록 하겠습니다 :)

const { LimitedArray, getIndexBelowMaxForKey } = require("./hashTableHelpers");

const HashTable = function() {
  this._limit = 8;
  this._storage = LimitedArray(this._limit);
};

HashTable.prototype.insert = function(k, v) {
  const index = getIndexBelowMaxForKey(k, this._limit);
  this._storage.set(index, v);
};

HashTable.prototype.retrieve = function(k) {
  const index = getIndexBelowMaxForKey(k, this._limit);
  return this._storage.get(index);
};

HashTable.prototype.remove = function(k) {
  const index = getIndexBelowMaxForKey(k, this._limit);
  
  this._storage.each((_, i, storage) => {
    if (index === i) {
      storage.splice(i, 1)
    }
  })
};

---

출처: https://bcho.tistory.com/1072 [조대협님 블로그]