データ構造05ハッシュテーブル|JS

Hash Table

Hash Table: Hash collision resolved by seperate chaining

画像ソース

ハッシュ表|HashTable

固定長データにマッピングして効率的なデータ管理

ハッシュ関数を実装することによってデータ値をハッシュ値

にマッピングする

ハッシュ関数

hashcode:ハッシュ関数によって返されるデータの一意の数値(キー値)

hashcode快速検索データ

より少ないリソースでより多くのデータを管理
:限定されたハッシュ値(HDD、クラウドなど)に無限のデータをマッピングすることによって管理

衝突(衝突)

不自然なhash関数でキー値を決定すると、同じ値

を導出することができる

同じキー値は、複数のデータが1つのテーブルで競合していることを示します

Collision:2つの異なるキーが同じインデックスを使用してハッシュされる(hash関数による計算を示す)

良いハッシュ関数の条件

一般的に、良いhash関数は、鍵の一部を参照してハッシュ値を作成するのではなく、鍵全体を参照してハッシュ値を作成する.しかし、良いハッシュ関数は、キーがどのような特性を有するかに依存する.

hash関数を1:1に無条件に設定するよりも、衝突を最小化する方向にどのように設計し、発生した衝突に対応するかが重要である.1:1の対応は難しいが、このようなhash関数を作成するのはarrayと変わらず、メモリが多すぎる.

Collisionが多ければ多いほど,探索に要する時間的複雑さはO(1)からO(n)に近づく.熟練していないhash関数はhashをhashのように使用することを許さない.良いhash関数を選択することは、hashテーブルのパフォーマンスを向上させるために必要です.

競合の解決

オープンアドレスほう

HASH競合時に他のHASHパケットにデータを挿入する方法

「分離式」(Separate Chaining)|「分離式」(Chaining)

切寧:接続リストにノードを追加し続ける(制限なく接続を継続するがメモリの問題)

接続リストの使用

各bucketを接続リスト(リンクリスト)として作成し、競合が発生したときにbucketのリスト

に追加する方法

接続リストの特徴を継承し、削除や挿入は簡単であるが、欠点は依然として存在するため、小さなデータを格納する際、接続リスト自体のオーバーヘッドが大きい.データ量が小さい場合は、リンクリスト

を使用することが望ましい.
ツリーの使用方法

Treeの基本アルゴリズムは、接続リストではなくツリーを使用してSeparate Chainingと同じです

ハッシュ・パケットの動的拡張(Resize)

ハッシュ・パケット数が少ない場合はメモリを節約できますが、ハッシュ競合によるパフォーマンス損失

key-value対データ数が一定数(75%)を超えると、ハッシュパケット数が2倍になる

接続リストによる実装

import LinkedList from '../linked-list/LinkedList';

const defaultHashTableSize = 32;

export default class HashTable {
  constructor(hashTableSize = defaultHashTableSize) {
    // 해시 테이블을 만들고 각 버킷을 빈 연결 리스트로 채움
    this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList());
    this.keys = {};
  }

  // 해시 함수: key 문자열을 해시 번호로 변환
  hash(key) {
    // 단순화 하기 위해 키의 모든 문자의 문자 코드 합계를 사용하여 해시를 계산합니다.
    // 그러나 충돌 횟수를 줄이기 위해 다항식 문자열 해시와 같은 보다 정교한 방식을 사용할 수도 있습니다.
    // hash = charCodeAt(0) * PRIME^(n-1) + charCodeAt(1) * PRIME^(n-2) + ... + 
    // charCodeAt(n-1) 여기서 charCodeAt(i)는 키의 i번째 문자 코드이고 
    // n은 키의 길이이며 PRIME은 31과 같은 임의의 소수입니다.
    const hash = Array.from(key).reduce((hashAccumulator, keySymbol) => {
      hashAccumulator + keySymbol.charCodeAt(0)
    }, 0);
    
    // 해시 테이블 크기에 맞도록 해시 수를 줄입니다.
    return hash % this.buckets.length;
  }

  set(key, value) {
    const keyHash = this.hash(key); // 해시 코드
    this.keys[key] = keyHash; // 해시코드를 keys 객체에 저장
    // 버킷에서 해시코드에 해당하는 연결 리스트를 가져옴
    const bucketLinkedList = this.buckets[keyHash]; 
    // 버킷연결리스트에서 동일한 키를 가진 노드가 있는지 탐색
    const node = 
      bucketLinkedList.find(
        { callback: (nodeValue) => nodeValue.key === key }
      );

    if (!node) {
      // 동일한 키를 가진 노드가 없다면 새 노드를 삽입
      bucketLinkedList.append({ key, value });
    } else {
      // 동일한 키를 가진 노드가 있다면 값 업데이트
      node.value.value = value;
    }
  }
  
  delete(key) {
    const keyHash = this.hash(key); // 해시 코드
    delete this.keys[key]; // 
    const bucketLinkedList = this.buckets[keyHash];
    const node = bucketLinkedList.find(
      { callback: (nodeValue) => nodeValue.key === key }
    );

    if (node) {
      return bucketLinkedList.delete(node.value);
    }

    return null;
  }
  
  get(key) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find(
      { callback: (nodeValue) => nodeValue.key === key }
    );

    return node ? node.value.value : undefined;
  }

  has(key) {
    return Object.hasOwnProperty.call(this.keys, key);
  }

  getKeys() {
    return Object.keys(this.keys);
  }

  getValues() {
    return this.buckets.reduce((values, bucket) => {
      const bucketValues = bucket.toArray()
        .map((linkedListNode) => linkedListNode.value.value);
      return values.concat(bucketValues);
    }, []);
  }
}

📚 リファレンス

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Photo by Alain Pham on Unsplash