ハッシュ テーブル : 衝突、サイズ変更、ハッシュ

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

ハッシュテーブルを理解する

辞書、ハッシュ マップ、ハッシュ テーブルについて聞いたことがあるかどうかに関係なく、それらはすべて本質的に同じです。このブログでは、わかりやすくするために、このデータ構造をハッシュ テーブルとして参照します。

ハッシュ テーブルとは何かを定義することから始めましょう。 ハッシュ テーブル は、非常に効率的な検索を実現するために、キーと値のペア の形式でキーを値にマップするデータ構造です。実装するには複数の方法があります。

---

ハッシュ テーブルの主要なコンポーネント

リンクされたリストの配列とハッシュ関数を使用して、ハッシュ テーブルを実装できます。ハッシュ関数とは何かをさらに詳しく見てみましょう。

ハッシュ関数とは何ですか?

ハッシュ関数は、ハッシュ テーブルの重要なコンポーネントです。これは、入力 (または「キー」) を受け取り、固定サイズのバイト文字列を通常は整数の形式で返す、通常は関数の形式のアルゴリズムです。出力はハッシュ コード、または単にハッシュと呼ばれます。

ハッシュ テーブルのコンテキストにおけるハッシュ関数の主な目的は、ハッシュ コードをバケット/スロットの配列の有効なインデックスにマップし、そこから目的の値を見つけることです。この場合、これらのバケット/スロットはリンク リストになります。

優れたハッシュ関数の特徴:

• 決定的: 指定された入力に対して、常に同じハッシュ出力を生成する必要があります。
• 均一分布: 予想される入力を出力範囲全体にわたってできるだけ均等にマッピングする必要があります。
• 効率的: 計算が速いはずです。
• 雪崩効果: 入力の小さな変更により、ハッシュ出力が大幅に異なります。

リンクされたリストの配列を使用する理由

ハッシュ テーブルの実装におけるリンク リストの配列の使用は、チェーンとして知られる一般的な手法です。このアプローチにはいくつかの利点があります。

1. 衝突処理: リンク リストの配列を使用する主な理由は、衝突を効率的に処理することです。 2 つのキーをハッシュして同じインデックスにマップする場合、新しいキーと値のペアをそのインデックスのリンク リストに追加するだけです。
2. スペース効率: ハッシュ テーブルが基になる配列のサイズよりも多くの項目を格納できるようになります。各配列スロットは、リンクされたリストを通じて複数の項目を保持できます。

Array:  [0] -> (key1, value1) -> (key2, value2)
        [1] -> (key3, value3)
        [2] -> (key4, value4) -> (key5, value5) -> (key6, value6)
        [3] -> Empty
        [4] -> (key7, value7)

この例では、キー 1 と 2 はインデックス 0 にハッシュされ、キー 4、5、および 6 はすべてインデックス 2 にハッシュされます。

---

キーと値のペアの挿入

ハッシュ関数とチェーンを使用する理由をよく理解したところで、キーと値のペアをハッシュ テーブルに挿入するフローを見てみましょう。

1. キー (任意の値) を挿入するときは、最初にキーの ハッシュ コード (通常は int または long) を計算します。 キーの数は無限で、整数の数は有限である可能性があるため、2 つの異なるキーが同じハッシュ コードを持つ可能性があります。

2. ハッシュ コードを配列内のインデックスにマッピングします。ハッシュ コードを配列にマッピングする一般的な方法は、モジュラス演算子 を使用することです。 (例: hash(key) % array.length))。 このメソッドを使用すると、2 つの異なるハッシュ コードが同じインデックスにマッピングされる可能性があります。

3. インデックスには、キーと値のリンクされたリストがあります。キーと値のペアをこのインデックスに保存します。キーに同じハッシュ コードがある場合、またはハッシュ コードが同じインデックスにマップされている場合、衝突が発生します。

キーと値のペアへのアクセス

ハッシュ テーブルの実装では、キーと値のペアへのアクセスが非常に効率的です。単純にキーからハッシュ コードを計算し、次にハッシュ コードからインデックスを計算し、最後にリンク リストでこのキーの値を検索します。

実装が適切であると仮定すると、キーと値のペア (挿入と削除も) にアクセスするには がかかります $O(1)$O(1) .

---

What Makes a Hash Table Implementation "Good"?

A well-implemented hash table should balance efficiency, space utilization, and collision handling. Here are the key factors that contribute to a good hash table implementation:

A Good Hash Function

The heart of any hash table is its hash function. A good hash function should:

• Be quick to compute
• Minimize collisions

Optimal Load Factor

The load factor is the ratio of filled slots to total slots in the hash table. Maintaining an appropriate load factor is crucial:

A typical sweet spot is between 0.6 and 0.75

• Too low (< 0.5): Wastes space
• Too high (> 0.8): Increases collision risk

Collision Resolution Techniques

Two primary methods for handling collisions are:

1. Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.

2. Open Addressing: If a collision occurs, look for the next available slot. Keeps all data in the table but requires careful implementation to avoid clustering of stored data.

Note that chaining and open-addressing cannot coexist easily. Logically, it would not make sense to look for the next available slot but store collided items at a specific index.

Dynamic Resizing

As the number of elements grows, the hash table should resize to maintain performance:

Typically, the table size is doubled when the load factor exceeds a threshold. All elements need to be rehashed into the new, larger table.

This operation is expensive but infrequent, keeping the amortized time complexity at O(1).

---

JavaScript Implementation

This implementation will utilize resizing and chaining for collision resolution. We will assume that our keys are integers.

For the hash function + mapping, we will keep it very simple and simply perform the following given a key:

$$key\mathrm{\%}arraycapacity$$key%arraycapacity

Classical OOP

class HashNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class HashTable {
    constructor(capacity = 16) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = new Array(this.capacity).fill(null);
        this.threshold = 0.75;
    }

    hash(key) {
        return key % this.capacity;
    }

    insert(key, value) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = new HashNode(key, value);
            this.size++;
        } else {
            let currentNode = this.buckets[index];
            while (currentNode.next) {
                if (currentNode.key === key) {
                    currentNode.value = value;
                    return;
                }
                currentNode = currentNode.next;
            }
            if (currentNode.key === key) {
                currentNode.value = value;
            } else {
                currentNode.next = new HashNode(key, value);
                this.size++;
            }
        }

        if (this.size / this.capacity >= this.threshold) {
            this.resize();
        }
    }

    get(key) {
        const index = this.hash(key);
        let currentNode = this.buckets[index];
        while (currentNode) {
            if (currentNode.key === key) {
                return currentNode.value;
            }
            currentNode = currentNode.next;
        }
        return undefined;
    }

    remove(key) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            return false;
        }
        if (this.buckets[index].key === key) {
            this.buckets[index] = this.buckets[index].next;
            this.size--;
            return true;
        }
        let currentNode = this.buckets[index];
        while (currentNode.next) {
            if (currentNode.next.key === key) {
                currentNode.next = currentNode.next.next;
                this.size--;
                return true;
            }
            currentNode = currentNode.next;
        }
        return false;
    }

    resize() {
        const newCapacity = this.capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        this.buckets.forEach(head => {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        this.buckets = newBuckets;
        this.capacity = newCapacity;
    }

    getSize() {
        return this.size;
    }

    getCapacity() {
        return this.capacity;
    }
}

Functional OOP

function createHashTable(initialCapacity = 16) {
    let capacity = initialCapacity;
    let size = 0;
    let buckets = new Array(capacity).fill(null);
    const threshold = 0.75;

    function hash(key) {
        return key % capacity;
    }

    function resize() {
        const newCapacity = capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        buckets.forEach(function(head) {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        buckets = newBuckets;
        capacity = newCapacity;
    }

    return {
        insert: function(key, value) {
            const index = hash(key);
            const newNode = { key, value, next: null };

            if (!buckets[index]) {
                buckets[index] = newNode;
                size++;
            } else {
                let currentNode = buckets[index];
                while (currentNode.next) {
                    if (currentNode.key === key) {
                        currentNode.value = value;
                        return;
                    }
                    currentNode = currentNode.next;
                }
                if (currentNode.key === key) {
                    currentNode.value = value;
                } else {
                    currentNode.next = newNode;
                    size++;
                }
            }

            if (size / capacity >= threshold) {
                resize();
            }
        },

        get: function(key) {
            const index = hash(key);
            let currentNode = buckets[index];
            while (currentNode) {
                if (currentNode.key === key) {
                    return currentNode.value;
                }
                currentNode = currentNode.next;
            }
            return undefined;
        },

        remove: function(key) {
            const index = hash(key);
            if (!buckets[index]) {
                return false;
            }
            if (buckets[index].key === key) {
                buckets[index] = buckets[index].next;
                size--;
                return true;
            }
            let currentNode = buckets[index];
            while (currentNode.next) {
                if (currentNode.next.key === key) {
                    currentNode.next = currentNode.next.next;
                    size--;
                    return true;
                }
                currentNode = currentNode.next;
            }
            return false;
        },

        getSize: function() {
            return size;
        },

        getCapacity: function() {
            return capacity;
        }
    };
}

以上がハッシュ テーブル : 衝突、サイズ変更、ハッシュの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。