๐Ÿ“ Hash Table

Table ์ด๋ชจ์ง€๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋‹ˆ Table Tennis๊ฐ€ ๋‚˜์˜ค๋„ค์š”.๐Ÿคฃ


๋จผ์ €, ์œ„ํ‚คํ”ผ๋””์•„์˜ ๊ทธ๋ฆผ์„ ๊ฐ™์ด ๋ด…์‹œ๋‹ค.

image.png

์ „ํ™”๋ฒˆํ˜ธ๋ถ€์— ์žˆ๋Š” ์‚ฌ๋žŒ์„ Hash Table์— ์ €์žฅํ•  ๋•Œ์˜ ๊ทธ๋ฆผ์ธ๋ฐ์š”.

keys(์ด๋ฆ„)์„ hash function์œผ๋กœ indexingํ•˜์—ฌ bucket์˜ ๊ฐ index์— value๋ฅผ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.

๊ทธ๋Ÿฐ๋ฐ ๊ณต๊ฐ„์„ ๋ฌดํ•œ์ •์œผ๋กœ ์ƒ์„ฑํ•  ์ˆ˜ ์—†์œผ๋‹ˆ ์ˆ˜์— ์ œํ•œ์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๋งŒ์•ฝ 80%๋งŒํผ ์ฑ„์›Œ์ง„๋‹ค๋ฉด 2๋ฐฐ๋กœ ๋Š˜๋ฆฌ๊ณ , 25%๋งŒํผ ์ค„์—ˆ๋‹ค๋ฉด ์ ˆ๋ฐ˜์œผ๋กœ ์ค„์ด๋Š” ๊ฒƒ์ด์ฃ .

๋˜, ํ•ด์‹ฑ์„ ํ•˜๋ฉด ๋™์ผํ•œ index๋ฅผ ๋ฐ›์„ ์ˆ˜๋„ ์žˆ๊ณ , ์ด๋•Œ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜์—ฌ ์ค‘๋ณต์ด ์ƒ๊น๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ํ•œ๋ฒˆ ๋“ค์–ด๋ณผ๊นŒ์š”?

์ตœ๋Œ€ ๊ณต๊ฐ„์„ 10์œผ๋กœ ์ œ์•ฝํ•ฉ๋‹ˆ๋‹ค. (๋ฌดํ•œ์ •์œผ๋กœ ์ƒ์„ฑํ•ด๋†“์œผ๋ฉด ๋‹น์—ฐํžˆ ๋น„ํšจ์œจ์ ์ด๋‹ˆ๊นŒ์š”.)

๊ทธ๋Ÿผ ํ•ด์‹œํ•จ์ˆ˜๋กœ ์ธ๋ฑ์‹ฑ์„ ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ€์ง“์ˆ˜์˜ ๋ฒ”์œ„๋Š” 10๊ฐ€์ง€ ์ด๋‚ด๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

์•„๋ฌด๋ฆฌ ๋‹ค์–‘ํ•œ ์ˆซ์ž๋ฅผ ๋„ฃ์–ด๋„ ์ตœ๋Œ€ 10๊ฐœ๋งŒ ๋“ค์–ด๊ฐ€๋‹ˆ๊นŒ์š”.

๊ทธ๋ ‡๋‹ค๋ฉด ํ•ด์‹œํ•จ์ˆ˜๋„ ์ตœ๋Œ€ ๊ณต๊ฐ„์˜ ์ œ์•ฝ์ˆ˜๋งŒํผ 1~10๊นŒ์ง€๋งŒ ์ƒ์„ฑ์„ ํ•ด๋ด…์‹œ๋‹ค.(๊ฐ„๋žตํ•˜๊ฒŒ)

๊ทธ๋Ÿผ ํ™•๋ฅ ์ ์œผ๋กœ '์‹ ์งฑ๊ตฌ'์™€ 'ํ™๊ธธ๋™'์˜ ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ™์€ ํ™•๋ฅ ๋„ ์žˆ๊ฒ ์ฃ ?

๊ทธ๋Ÿผ ๊ฐ™์€ ์ธ๋ฑ์Šค๊ฐ€ ์ค‘๋ณต๋˜์–ด ์ถฉ๋Œ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒ๋˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์™œ ์กฐ๊ฑด์„ ์ด๋ ‡๊ฒŒ ๋งŽ์ด ์ถ”๊ฐ€ํ–ˆ๋ƒ๋ฉด, ์›๋ž˜๋Š” ํ•ด์‹œ ํ•จ์ˆ˜์˜ ๋ชจ์–‘์— ๋”ฐ๋ผ ํ™•๋ฅ ์ด ์•„์ฃผ ์ ์–ด์งˆ ์ˆ˜ ์žˆ์œผ๋‹ˆ๊นŒ์š”!

์ด๋ฅผ ํ•ด๊ฒฐ ํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์ด 2๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

1. Separate chaining

image.png
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์ด ์žˆ์„๋•Œ, ์•„๋ž˜ ๊ทธ๋ฆผ์—์„œ๋Š” ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค.

image.png

๊ทธ๋Ÿฐ๋ฐ, ์—ฌ๊ธฐ์— 11์„ key๋กœ ํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ์œผ๋ฉด key๊ฐ€ 1์ธ data์™€ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค!

Linear Probing์€ ์•„๋ž˜ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•œ index[1] ๋’ค์˜ ๋ฒ„ํ‚ท์— ๋นˆ ๋ฒ„ํ‚ท์ด ์žˆ๋Š”์ง€ ๊ฒ€์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.

2๋ฒˆ ๋ฒ„ํ‚ท์€ ์ด๋ฏธ index[2]๊ฐ€ ๋“ค์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— 3๋ฒˆ ๋ฒ„ํ‚ท์— ์ €์žฅ์„ ํ•ฉ๋‹ˆ๋‹ค.

image.png

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 [์กฐ๋Œ€ํ˜‘๋‹˜ ๋ธ”๋กœ๊ทธ]