Jadual Hash : Perlanggaran, Saiz semula, Hashing

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

Memahami Jadual Hash

Sama ada anda pernah mendengar tentang kamus, atau peta cincang, atau jadual cincang, semuanya pada asasnya adalah sama. Dalam blog ini, kami akan merujuk struktur data ini sebagai jadual cincang demi kesederhanaan.

Mari kita mulakan dengan mentakrifkan apa itu jadual cincang. jadual cincang ialah struktur data yang memetakan kunci kepada nilai dalam bentuk pasangan nilai kunci untuk carian yang sangat cekap. Terdapat pelbagai cara untuk melaksanakannya.

---

Komponen Utama Jadual Hash

Menggunakan tatasusunan senarai terpaut dan fungsi pencincangan kita boleh melaksanakan jadual cincang. Mari kita selami lebih mendalam tentang fungsi pencincangan.

Apakah Fungsi Hashing?

Fungsi pencincangan ialah komponen penting dalam jadual cincang. Ia adalah algoritma, biasanya dalam bentuk fungsi, yang mengambil input (atau 'kunci') dan mengembalikan rentetan bait bersaiz tetap, biasanya dalam bentuk integer. Output dipanggil kod cincang atau hanya cincang.

Tujuan utama fungsi pencincangan dalam konteks jadual cincang adalah untuk memetakan kod cincang kepada indeks yang sah bagi tatasusunan baldi/slot, yang daripadanya nilai yang dikehendaki boleh didapati. Baldi/slot ini akan dipautkan senarai dalam kes kami.

Ciri-ciri Fungsi Hashing yang Baik:

• Deterministik: Untuk input yang diberikan, ia harus sentiasa menghasilkan output cincang yang sama.
• Pengagihan Seragam: Ia harus memetakan input yang dijangkakan sekata mungkin pada julat outputnya.
• Cekap: Ia sepatutnya cepat untuk dikira.
• Kesan Avalanche: Perubahan kecil dalam input seharusnya menghasilkan output cincang yang berbeza dengan ketara.

Mengapa Menggunakan Tatasusunan Senarai Terpaut?

Penggunaan tatasusunan senarai terpaut dalam pelaksanaan jadual cincang ialah teknik biasa yang dikenali sebagai perantaian. Pendekatan ini menawarkan beberapa kelebihan:

1. Pengendalian Perlanggaran: Sebab utama untuk menggunakan tatasusunan senarai terpaut adalah untuk mengendalikan perlanggaran dengan cekap. Apabila dua kekunci cincang dan petakan ke indeks yang sama, kita hanya boleh menambah pasangan nilai kunci baharu pada senarai terpaut pada indeks tersebut.
2. Kecekapan Ruang: Ia membenarkan jadual cincang menyimpan lebih banyak item daripada saiz tatasusunan asas. Setiap slot tatasusunan boleh memuatkan berbilang item melalui senarai terpautnya.

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

Dalam contoh ini, kunci 1 dan 2 cincang untuk mengindeks 0, manakala kunci 4, 5 dan 6 semuanya cincang kepada indeks 2.

---

Memasukkan Pasangan Nilai Kunci

Sekarang kita mempunyai pemahaman yang baik tentang fungsi cincang dan sebab kami menggunakan perangkaian, mari kita melalui aliran memasukkan pasangan nilai kunci ke dalam jadual cincang:

1. Apabila memasukkan kunci (sebarang nilai), kami mula-mula mengira kod cincang kunci (biasanya int atau panjang). Ada kemungkinan dua kekunci berbeza boleh mempunyai kod cincang yang sama kerana mungkin terdapat # kunci tidak terhingga dan # int terhingga.

2. Peta kod cincang ke indeks dalam tatasusunan. Kaedah biasa untuk memetakan kod cincang ke tatasusunan ialah menggunakan operator modulus. (cth., hash(key) % array.length)). Ada kemungkinan dua kod cincang yang berbeza boleh dipetakan ke indeks yang sama dengan kaedah ini.

3. Pada indeks, terdapat senarai kunci dan nilai yang dipautkan. Simpan pasangan nilai kunci pada indeks ini. Perlanggaran berlaku apabila kunci mempunyai kod cincang yang sama atau kod cincang yang dipetakan ke indeks yang sama.

Mengakses Pasangan Nilai Kunci

Mengakses pasangan nilai kunci adalah sangat cekap dalam pelaksanaan jadual cincang. Hanya kira kod cincang daripada kunci, kemudian kira indeks daripada kod cincang, dan akhirnya cari melalui senarai terpaut untuk nilai dengan kunci ini.

Dengan mengandaikan pelaksanaan yang baik, mengakses pasangan nilai kunci (sisipan dan pemadaman juga), memerlukan $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;
        }
    };
}

Atas ialah kandungan terperinci Jadual Hash : Perlanggaran, Saiz semula, Hashing. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!