Javascript数据结构—

18_哈希表_深入链地址法_哔哩哔哩_bilibili

哈希表（Hash Table），又称为散列表，是一种通过哈希函数组织数据以实现快速访问的数据结构。下面将从其概述、底层实现和前端应用场景等方面进行详细阐述。

概述

哈希表的基本思路是，设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存单元，以每个元素的关键字k为自变量，通过哈希函数把k映射为内存单元的地址（下标），并把该元素存储在这个内存单元中，如此构造的存储结构称为哈希表。简单来说，哈希表就像是一个巨大的书架，每个书架格都有一个编号（哈希值），而每个编号下都可以存放一本书（键值对）。当你想要找一本书时，只需知道它的编号，就能迅速定位到它所在的位置。

哈希函数是哈希表的核心，它接收一个输入（键），并返回一个输出（哈希值），这个哈希值通常是一个整数，用于确定键在表中的位置。理想情况下，哈希函数应该尽可能减少冲突（不同键产生相同哈希值的情况）。当两个键产生相同的哈希值时，就需要冲突解决机制。常见的冲突解决方法有开放寻址法和链地址法。

底层实现

哈希函数：哈希函数的设计至关重要，它决定了哈希表的性能和效率。一个好的哈希函数应该具有快速计算、均匀分布等特点。在JavaScript中，Object类型的哈希表实际上是通过链地址法来解决冲突的，即每个数组索引指向一个链表，链表中存储所有哈希值相同的键值对。
冲突解决：
- 链地址法：每个哈希表的槽位存储一个链表，所有哈希值相同的键值对都存储在这个链表中。这种方法在处理冲突时比较灵活，但可能会增加额外的空间开销。
- 开放寻址法：当发生冲突时，通过一定的探测策略（如线性探测、二次探测、再哈希等）找到一个空闲的槽位来存储键值对。这种方法不需要额外的存储空间，但可能会增加查找时间。
动态扩容：当哈希表中的数据量增加到一定程度时，会进行动态扩容，以避免哈希冲突和保持查找效率。扩容通常涉及重新计算所有键值对的哈希值，并将它们重新插入到新的哈希表中。

前端应用场景

缓存系统：在Web开发中，经常需要将频繁访问的数据存储在缓存中以提高访问速度。哈希表以其快速查找的特性，成为了缓存系统的理想选择。

去重与计数：在处理需要快速去重或计数的场景时，哈希表表现出色。例如，在统计一个字符串中每个字符出现的次数时，可以使用哈希表来记录每个字符及其对应的计数。
路由表：在Web服务器中，路由表负责将URL映射到相应的处理函数。哈希表能够快速根据URL定位到处理函数，提高路由效率。
用户输入处理：在处理用户输入时，可以使用哈希表来快速检查输入数据是否已存在或是否满足某些条件。

总之，哈希表作为数据结构中的瑰宝，在JavaScript开发中发挥着不可替代的作用。通过深入理解哈希表的原理和实现方式，可以更好地利用这一强大工具来优化代码性能和提高开发效率。

手动实现哈希表

实现哈希表（Hash Table）通常涉及两个主要部分：哈希函数（hash function）和存储桶（buckets）。在 JavaScript 中，我们可以使用数组和链表来实现一个简单的哈希表。数组将作为存储桶的集合，而链表将用于处理哈希冲突（即多个键映射到同一个索引的情况）。

以下是一个简单的实现：

定义链表节点：
链表节点将存储键值对以及指向下一个节点的指针。

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

定义哈希表：
哈希表将包含一个数组（存储桶）和一个哈希函数。

class HashTable {  
    constructor(size = 10) {  
        this.size = size;  
        this.buckets = new Array(size).fill(null);  
    }  
  
    // 简单的哈希函数  
    hashFunction(key) {  
        let hash = 0;  
        for (let i = 0; i < key.length; i++) {  
            hash = (hash * 31 + key.charCodeAt(i)) % this.size;  
        }  
        return hash;  
    }  
  
    // 插入键值对  
    set(key, value) {  
        const index = this.hashFunction(key);  
        const bucket = this.buckets[index];  
  
        if (bucket === null) {  
            // 如果桶为空，创建一个新的链表节点  
            this.buckets[index] = new ListNode(key, value);  
        } else {  
            // 如果桶不为空，遍历链表查找键或插入新节点  
            let currentNode = bucket;  
            while (currentNode !== null) {  
                if (currentNode.key === key) {  
                    // 如果键已存在，更新值  
                    currentNode.value = value;  
                    return;  
                }  
                if (currentNode.next === null) {  
                    // 链表末尾，插入新节点  
                    currentNode.next = new ListNode(key, value);  
                    return;  
                }  
                currentNode = currentNode.next;  
            }  
        }  
    }  
  
    // 获取值  
    get(key) {  
        const index = this.hashFunction(key);  
        const bucket = this.buckets[index];  
  
        if (bucket === null) {  
            // 如果桶为空，返回 undefined  
            return undefined;  
        } else {  
            // 遍历链表查找键  
            let currentNode = bucket;  
            while (currentNode !== null) {  
                if (currentNode.key === key) {  
                    return currentNode.value;  
                }  
                currentNode = currentNode.next;  
            }  
        }  
        // 如果键不存在，返回 undefined  
        return undefined;  
    }  
  
    // 删除键值对  
    remove(key) {  
        const index = this.hashFunction(key);  
        let bucket = this.buckets[index];  
  
        if (bucket === null) {  
            // 如果桶为空，不执行任何操作  
            return;  
        } else if (bucket.key === key) {  
            // 如果要删除的节点是桶的第一个节点  
            this.buckets[index] = bucket.next;  
        } else {  
            // 遍历链表查找并删除节点  
            let currentNode = bucket;  
            while (currentNode.next !== null) {  
                if (currentNode.next.key === key) {  
                    currentNode.next = currentNode.next.next;  
                    return;  
                }  
                currentNode = currentNode.next;  
            }  
        }  
    }  
}

使用哈希表：
现在我们可以创建哈希表实例并插入、获取和删除键值对。

const hashTable = new HashTable();  
hashTable.set('name', 'Alice');  
hashTable.set('age', 30);  
hashTable.set('city', 'New York');  
  
console.log(hashTable.get('name')); // 输出: Alice  
console.log(hashTable.get('age'));  // 输出: 30  
console.log(hashTable.get('city')); // 输出: New York  
  
hashTable.remove('age');  
console.log(hashTable.get('age'));  // 输出: undefined

这个简单的哈希表实现展示了如何使用数组和链表来处理哈希冲突，并通过哈希函数将键映射到数组索引。注意，这只是一个基础实现，实际生产中的哈希表可能会使用更复杂的哈希函数、动态数组大小调整（如哈希表的扩展和收缩）以及其他优化技术。