JavaScript -- 散列表

以下是一个简单的使用JavaScript实现的散列函数示例，它可以将输入的字符串转换为一个哈希值（这里采用简单的取余法结合字符编码值来计算，实际应用中的散列函数会更复杂和安全）：

function hashFunction(str) {
    let hash = 0;
    if (str.length === 0) return hash;
    for (let i = 0; i < str.length; i++) {
        // 获取字符的Unicode编码值
        let charCode = str.charCodeAt(i);
        hash = ((hash << 5) - hash) + charCode;
        hash = hash & hash; // 转换为32位有符号整数（保持一致性，避免溢出问题）
    }
    return hash % 10000; // 简单取余，让哈希值落在一定范围内，可根据实际需求调整
}

// 示例用法
const input = "hello";
const hashValue = hashFunction(input);
console.log(hashValue);

在上述代码中：

1. 整体思路

这个散列函数的目的是将输入的字符串通过一定的计算规则转化为一个相对固定的数值（哈希值），使得不同的字符串有较大概率产生不同的哈希值，方便后续在一些需要快速查找、对比等场景中使用（比如在简单的哈希表数据结构实现中）。

2. 代码细节解释

变量初始化：
首先定义了变量 hash 并初始化为 0，它将用于存储最终计算得到的哈希值。如果输入的字符串长度为 0，也就是空字符串，直接返回这个初始的 hash 值（也就是 0）。
循环遍历字符串：
通过 for 循环遍历输入字符串的每个字符，在循环中：
- 获取字符编码值：使用 str.charCodeAt(i) 方法获取当前字符的Unicode编码值，将其存储在变量 charCode 中。例如，字符 'a' 的Unicode编码值是 97，这个编码值将参与后续的哈希计算。
- 哈希计算操作：执行 hash = ((hash << 5) - hash) + charCode; 这一步是核心的计算步骤，(hash << 5) - hash 相当于对 hash 进行了一种特定的数学变换（先左移5位再减去原 hash 值，这是一种简单的混合操作，让之前的 hash 值和新的字符编码值能更好地融合，不同顺序的字符会产生不同的影响，以此来区分不同的字符串），然后再加上当前字符的编码值 charCode，更新 hash 的值。接着 hash = hash & hash; 这一步是通过位运算将 hash 转换为32位有符号整数，确保其数值范围在合适的区间内，避免因计算导致数值溢出等异常情况，保持计算的稳定性和一致性。
返回哈希值：
最后，通过 return hash % 10000; 将计算得到的 hash 值对 10000 取余，使得哈希值落在 0 到 9999 的范围内，这只是一种简单的限定范围的方式，可根据实际需求调整取余的数值，比如如果希望哈希值范围更大，可以选择更大的数进行取余操作。

需要注意的是，上述示例只是一个非常基础的散列函数实现，在实际应用场景中，尤其是涉及到安全性要求较高（比如密码存储等情况）或者需要更均匀分布哈希值的情况，会使用更专业、复杂的散列算法，像MD5（虽然现在安全性有所欠缺但曾经广泛使用）、SHA系列（如SHA-256等）等算法，并且通常还会结合盐值（额外添加的随机字符串来增加安全性）等技术手段来保障散列的质量和安全性。

以下是一个结合使用第三方库 crypto（Node.js环境自带的加密模块）来实现更安全的哈希计算（以SHA-256算法为例）的示例代码，这种方式常用于对敏感信息（如密码）进行哈希处理：

const crypto = require('crypto');

function secureHashFunction(str) {
    const hash = crypto.createHash('sha256');
    hash.update(str);
    return hash.digest('hex');
}

// 示例用法
const input = "mysecretpassword";
const hashValue = secureHashFunction(input);
console.log(hashValue);

在这段Node.js环境下的代码中：

首先引入了 crypto 模块，它提供了丰富的加密相关的功能。
然后创建了一个 SHA-256 类型的哈希对象 hash，通过 hash.update(str) 方法将输入的字符串传递进去，告知哈希对象要对这个字符串进行哈希计算。
最后使用 hash.digest('hex') 方法获取计算后的哈希值，并以十六进制字符串的形式返回，这个哈希值就具有较高的安全性和唯一性（对于不同的输入字符串，大概率会产生不同的十六进制哈希值字符串），适用于对敏感信息进行不可逆的哈希处理，保障信息安全。

如果是在浏览器环境中，也可以使用一些现代浏览器支持的 SubtleCrypto 接口（它提供了类似的加密、哈希等功能，但接口使用方式稍有不同）来实现安全的哈希计算，示例如下：

async function browserSecureHashFunction(str) {
    const encoder = new TextEncoder();
    const data = encoder.encode(str);
    const hashBuffer = await window.crypto.subtle.digest('SHA-256', data);
    const hashArray = Array.from(new Uint8Array(hashBuffer));
    const hashHex = hashArray.map(b => b.toString(16).padLeft(2, '0')).join('');
    return hashHex;
}

// 示例用法
const input = "mysecretpassword";
const hashValue = await browserSecureHashFunction(input);
console.log(hashValue);

在浏览器环境的这段代码中：

首先使用 TextEncoder 将输入的字符串转换为字节数组（因为 SubtleCrypto 接口处理的是字节数据）。
然后通过 window.crypto.subtle.digest('SHA-256', data) 异步地执行 SHA-256 哈希计算，得到一个包含哈希结果的 Buffer 对象（在JavaScript中以 ArrayBuffer 形式表示）。
接着将这个 ArrayBuffer 转换为数组形式，并进一步将每个字节转换为十六进制字符串表示，最后拼接起来得到最终的十六进制哈希值字符串并返回。

不同的实现方式适用于不同的环境和应用场景，你可以根据具体的需求选择合适的散列函数实现方法。

哈希冲突

function hashFunction(num, divisor = 100) {
    return num % divisor;
}

// 这个里边我输入 123 和 223 的得到的 hash 不都是 23 吗，这样不就重复了么？}

这个里边我输入 123 和 223 的得到的 hash 不都是 23 吗，这样不就重复了么

产生的原因

除留余数法是通过取输入数据除以一个固定除数（这里是 100）的余数来作为哈希值。当不同的输入数据在除以这个除数后得到相同的余数时，就会产生哈希冲突。

从数学原理上来说，只要两个数与除数相除后余数相同，它们就会被映射到同一个哈希值。比如对于 123 和 223，按照 num % 100 的计算：

123 ÷ 100 = 1……23（商为 1，余数为 23）
223 ÷ 100 = 2……23（商为 2，余数为 23）

所以它们最终得到了相同的哈希值，这是这种简单散列函数很容易出现的情况，尤其是当输入数据分布比较集中或者除数选择不太合适时，哈希冲突发生的概率会更高。

影响哈希冲突频率的因素

（1）除数的选择

除数（也就是代码中的 divisor 参数）的大小和性质对哈希冲突的频率有很大影响。如果除数过小，余数的取值范围就很窄，那么不同输入产生相同余数的可能性就会大大增加。例如，若除数选择为 10，那哈希值就只能是 0 到 9 这 10 种情况，冲突概率自然很高。

相反，除数过大也不一定好，一方面会使得哈希值的范围过大，可能超出实际需要或者在存储、处理哈希值时带来不便；另一方面，对于一些特定的数据分布，过大的除数也未必能有效降低冲突概率，而且还可能增加计算成本等。所以选择一个合适的除数需要综合考虑输入数据的特点、期望的哈希值范围以及对冲突的容忍程度等因素。

（2）输入数据的分布特点

如果输入数据本身呈现出一定的规律，比如是连续的整数、有周期性的数值等，或者集中在某个区间内，那么更容易出现哈希冲突。例如，假设输入的数据都是 100 到 200 之间的整数，使用 100 作为除数，那很多数除以 100 的余数就会集中在一个较小的范围内，冲突频发。

解决哈希冲突的常见方法

（1）链地址法

当出现哈希冲突时，把产生相同哈希值的元素通过链表（在 JavaScript 中可以用对象模拟链表结构等方式）连接起来存储。例如，创建一个哈希表对象，它的每个键对应一个链表（初始为空），当插入一个元素计算出哈希值后，如果该哈希值对应的链表已经存在元素（即发生了冲突），就把新元素添加到这个链表末尾。

以下是一个简单的使用链地址法处理冲突的哈希表示例代码（基于 JavaScript）：

function HashTable() {
    this.table = {};
}

HashTable.prototype.put = function (key, value) {
    const hash = hashFunction(key);
    if (!this.table[hash]) {
        this.table[hash] = [];
    }
    this.table[hash].push({ key, value });
};

HashTable.prototype.get = function (key) {
    const hash = hashFunction(key);
    if (this.table[hash]) {
        const list = this.table[hash];
        for (const item of list) {
            if (item.key === key) {
                return item.value;
            }
        }
    }
    return null;
};

// 示例用法
const hashTable = new HashTable();
hashTable.put(123, 'value1');
hashTable.put(223, 'value2');
console.log(hashTable.get(123)); // 输出 'value1'
console.log(hashTable.get(223)); // 输出 'value2'

在上述代码中：

HashTable 类表示哈希表，this.table 用于存储哈希值对应的链表数据结构。
put 方法用于向哈希表中插入键值对，先计算键的哈希值，若对应哈希值的链表不存在则创建一个空链表，然后将包含键值对的对象添加到链表中。
get 方法用于根据键查找对应的值，先获取键的哈希值，再遍历对应链表查找匹配的键并返回其对应的值，如果没找到则返回 null。

（2）开放定址法

当发生哈希冲突时，按照一定的规则去寻找其他空闲的存储位置来存放冲突的元素。常见的规则有线性探测（按照顺序依次往后查找空闲位置）、二次探测（按照二次函数的规律来确定探测的位置间隔，比如先探测 +1 位置，再探测 +4 位置，再探测 +9 位置等）、双重哈希（再使用另一个散列函数来确定探测的步长等）等方式。

以下是一个简单的使用线性探测开放定址法的哈希表示例代码：

function HashTable(size = 100) {
    this.size = size;
    this.table = new Array(size).fill(null);
}

HashTable.prototype.hashFunction = function (key) {
    return key % this.size;
}

HashTable.prototype.put = function (key, value) {
    let hash = this.hashFunction(key);
    while (this.table[hash]) {
        hash = (hash + 1) % this.size;
    }
    this.table[hash] = { key, value };
};

HashTable.prototype.get = function (key) {
    let hash = this.hashFunction(key);
    while (this.table[hash] && this.table[hash].key!== key) {
        hash = (hash + 1) % this.size;
    }
    return this.table[hash]? this.table[hash].value : null;
};

// 示例用法
const hashTable = new HashTable();
hashTable.put(123, 'value1');
hashTable.put(223, 'value2');
console.log(hashTable.get(123)); // 输出 'value1'
console.log(hashTable.get(223)); // 输出 'value2'

在这个代码中：

HashTable 类定义了哈希表的结构，包括设定大小 size 和用于存储数据的数组 table。
put 方法在插入元素时，先计算出初始哈希值，如果该位置已被占用（有冲突），就按照线性探测规则（依次往后找空闲位置），通过不断更新 hash 的值（取余保证在哈希表范围内），直到找到空闲位置后存入元素。
get 方法查找元素时，同样先获取初始哈希值，然后如果当前位置元素不匹配且不为空（说明可能是冲突后存放在其他位置了），就按照同样的线性探测规则往后查找，直到找到匹配的键或者遇到空位置（表示没找到）返回相应结果。

总之，哈希冲突是简单散列函数常见的问题，不过可以通过合适的冲突处理方法来保证在出现冲突的情况下，数据的存储、查找等操作依然能够正常进行，具体选择哪种方法可以根据实际应用场景的需求、性能要求以及数据特点等来综合决定。

注意

链地址法的注意点：
- 链表维护成本：随着数据量的增加以及冲突的增多，链表可能会变得很长，这会导致在查找、插入和删除元素时遍历链表的时间成本增加，影响哈希表整体的操作效率，所以在数据量较大且冲突频繁的情况下，需要考虑对链表进行优化（比如定期对链表进行整理、采用更高效的查找算法等）。
- 内存占用：每个链表节点都需要占用一定的内存空间来存储数据以及指向下一个节点的指针（在模拟链表结构时），大量的冲突会使得链表节点数量增多，进而导致内存占用较大，要注意内存资源的合理使用和优化。
开放定址法的注意点：
- 聚集问题：像线性探测这种开放定址法容易出现聚集现象，即连续的冲突会导致元素在哈希表中聚集在一起，进一步增加后续冲突的概率，使得查找效率逐渐降低。为了避免或缓解聚集问题，可以采用二次探测、双重哈希等更复杂的探测规则，但这些规则相应地也会增加计算的复杂性和代码实现的难度。
- 删除操作复杂性：在开放定址法中，删除元素不能简单地将对应位置置空，因为这样可能会破坏后续元素的查找路径（后续元素是按照探测规则存放在该位置之后的），所以需要采用标记删除等特殊的处理方式来解决这个问题，这也增加了代码实现和维护的复杂度。
选择冲突处理方法的综合考量：
无论是链地址法还是开放定址法，都有各自的优缺点和适用场景，在实际选择时要充分考虑数据的预期规模、读写操作的频率、对内存的要求以及代码的可维护性等多方面因素，权衡利弊后做出合适的决策，以确保哈希表在整个应用程序中的性能和功能能够满足需求。

总结

冲突问题：无论采用哪种散列函数，都有可能出现不同的输入产生相同哈希值的情况，这被称为哈希冲突。在设计和使用散列函数时，要考虑如何处理这种冲突，常见的处理方法有链地址法（将产生相同哈希值的元素通过链表等方式链接起来存储）、开放定址法（通过一定的规则寻找其他空闲位置来存储冲突的元素）等，具体的处理方式需要根据数据结构和应用场景来选择。
性能考量：复杂的散列算法（如SHA系列算法）虽然安全性高，但计算过程相对耗时，在对性能要求较高、数据量极大的场景下，可能需要权衡安全性和性能之间的关系，选择合适的散列算法或者对现有算法进行优化（比如采用硬件加速等方式，不过这需要特定的硬件支持），避免因哈希计算导致整个程序的运行效率低下。
1. 一些简单的场景：在构建小型的、用于缓存非敏感数据的缓存系统时，简单散列函数能够发挥较好的作用。例如，缓存一些网页中的静态资源（如图片、样式表、脚本文件等）路径与对应内容的映射关系，或者缓存简单的配置信息（如应用程序中某些固定的、不涉及安全的配置参数）等情况
2. 当需要在程序中实现一个哈希表来存储一些普通的数据结构，且数据量不大时，简单散列函数是可行的选择。比如存储一个小型游戏中玩家的简单信息（如玩家编号、昵称等）与对应游戏状态（如得分、当前关卡等）的映射关系，或者在一个小型的文本编辑器中存储单词与出现次数的统计信息等场景。
3. 数据校验与完整性初步检查（非关键数据）在对一些非关键数据进行简单的数据校验，以初步判断数据是否完整或者是否被意外修改时，可以使用简单散列函数。例如，在传输一些普通的文本文件（如日志文件、简单的配置说明文档等）过程中，为文件内容计算一个简单的哈希值，并随文件一同发送，接收方收到文件后同样计算其哈希值并与发送方传来的哈希值进行对比，若相同则大概率说明文件在传输过程中没有出现错误或被篡改。
4. 简单的分类或者分组标识。当需要根据数据的某些特征对其进行快速分类或分组，且对分类的精确性要求不是极高时，可以利用简单散列函数。比如在一个电商系统中，对众多商品按照价格区间进行大致分类（如分为低价、中价、高价商品等），可以通过简单的散列函数将商品价格映射为不同的哈希值，对应不同的分类标识，以便后续进行快速筛选、统计等操作。
5. 教学与学习场景
安全性要求：如果是用于处理敏感信息（如用户密码、重要数据的加密存储等），一定要使用安全性经过验证的散列算法（如现代的SHA-256等），并且结合盐值等手段来增强安全性，防止出现密码被轻易破解等安全风险；而对于一些非敏感信息、仅用于简单的数据快速查找对比等场景，可以根据性能需求等因素选择相对简单的散列函数，但也要考虑到可能出现的哈希冲突等问题对功能的影响。
环境兼容性：像Node.js环境下的 crypto 模块和浏览器环境下的 SubtleCrypto 接口在使用方式、支持的功能等方面存在差异，在跨环境开发或者部署项目时，要确保所采用的散列函数实现能够在相应的环境中正常工作，避免出现因环境不兼容导致的代码无法运行等问题，可以通过适当的代码封装、条件判断等方式来保障在不同环境下的兼容性。

JavaScript

#面试 #JavaScript

JavaScript -- 散列表

http://example.com/2023/11/09/JavaScript-散列表/

作者

lyric

发布于

2023年11月9日

许可协议

JavaScript -- 字典上一篇

JavaScript -- 纯函数下一篇