后端开发教程 - Java、Spring Boot 实战 - msg200.com
JavaScript 哈希表完成了 JavaScript 数据结构课程，以下是我学到的有关哈希表的知识。
什么是哈希表？
为啥那么快？
处理碰撞
我们应该实现自己的哈希函数吗？
执行
可能，哈希表就是我所寻找的！
结论
参考
在最近的几篇文章中，我概述了我在 Udemy 上学习 JavaScript 数据结构和算法课程时学到的链表、队列、堆栈、二叉搜索树和二叉堆。与此同时，我也在为我的 Chrome 扩展程序项目寻找一种更好的结构来降低时间复杂度。
目前，我将主要数据作为对象存储在数组中，如下所示：
// Result of console.log(MainData)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}
我想实现高效删除/编辑每个数据的功能，但在这种情况下，这两个功能的时间复杂度都是 O（n）。
继二叉堆之后，我学习了哈希表。在本文中，我将思考它是否适用。
什么是哈希表？
哈希表（也称哈希映射）是基于哈希的结构之一。它看起来类似于数组——我们将索引映射到值，但对于哈希表，我们使用键而不是索引。
与数组类似，哈希表也是许多计算机语言的内置数据结构。在 JavaScript 中，Object和Map提供了一种非常高效的哈希表结构。
例如，如果每个数据中都有一个像名称这样的唯一值，我们就可以使用名称作为其键。这些特性使我们能够非常快速地访问单个项目。
如果它是一个常规数组，我们需要循环遍历每个元素来找到一个元素。因此，它的时间复杂度为 O(n)。
let StudentResidence = [];
class Student {
constructor(name, age, grade, licenceEnds) {
this.name = name;
this.age = age;
this.grade = grade;
this.licenceEnds = licenceEnds;
}
}
StudentResidence.push(new Student('Tara Joyce', 18, 'A', '11-06-2021'))
StudentResidence.push(new Student('Brian Brown', 19, 'A', '05-06-2020'))
StudentResidence.push(new Student('John Smith', 18, 'B', '07-06-2021'))
// To change Tara's age, we need to look up each item
for (let i=0; i<StudentResidence.length; i++) {
if(StudentResidence[i].name === 'Tara Joyce') {
StudentResidence[i].age = 19;
}
}
但是，如果它以键值对的形式存储，则无需循环数据。
let StudentResidence = {};
class Student {
constructor(age, grade, licenceEnds) {
this.age = age;
this.grade = grade;
this.licenceEnds = licenceEnds;
}
}
StudentResidence['Tara Joyce'] = new Student(18, 'A', '11-06-2021');
StudentResidence['Brian Brown'] = new Student(19, 'A', '05-06-2020');
StudentResidence['John Smith'] = new Student(18, 'B', '07-06-2021');
// To change Tara's age, no need to look up each item
StudentResidence['Tara Joyce'].age = 19;
我们也可以用Map来实现。
let StudentResidence = new Map();
class Student {
constructor(age, grade, licenceEnds) {
this.age = age;
this.grade = grade;
this.licenceEnds = licenceEnds;
}
}
StudentResidence.set('Tara Joyce', new Student(18, 'A', '11-06-2021'));
StudentResidence.set('Brian Brown', new Student(19, 'A', '05-06-2020'));
StudentResidence.set('John Smith', new Student(18, 'B', '07-06-2021'));
// To change Tara's age, no need to look up each item
StudentResidence.get('Tara Joyce').age = 19
这些仅需要 O(1)，即恒定时间。
为啥那么快？
哈希表的背后原理是，它使用哈希函数根据键计算索引，索引决定了值应该存储在哪个桶中。因此，当我们想要找到值的存储位置时，可以使用哈希函数计算索引，并找到所需值的存储位置。
理想情况下，哈希函数将每个键分配给一个唯一的存储桶，但我们需要考虑哈希函数为多个键生成相同索引的情况。
处理碰撞
处理碰撞的策略有很多，但我们将在这里讨论其中两种常见的策略。
方法 1：单独链接
使用分离链接时，我们将它们存储在同一个 bucket 中，并在其中嵌套另一种类型的列表。如果使用链表或数组实现，查找时间将取决于每个 bucket 的平均键数。
方法二：线性探测
线性探测是开放寻址策略的一种，在开放寻址策略中，每个桶只允许一个键值对集合。当发现冲突时，我们会搜索整个数组，直到找到一个未被占用的桶。
我们应该实现自己的哈希函数吗？
当我们使用 JavaScript 并试图实现快速和轻量级时，首先我们应该考虑使用常规的 Object 或 Map，因为它们已经能够高效地处理。然而，实现我们自己的哈希表将有助于我们理解幕后发生的事情。
执行
首先，我们将HashTable定义为一个数组。
class HashTable {
constructor(size=53) {
this.keyMap = new Array(size);
}
_hash(key) {
}
set(key, value) {
}
get(key) {
}
}
哈希函数
该哈希函数根据密钥生成 0 到 53 之间的索引。
_hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total + WEIRD_PRIME * value) % this.keyMap.length;
}
return total;
}
使用单独链接方法插入
我们在每个存储桶内创建数组，因此我们只需将键值对推送到存储桶中的数组中。
set(key, value) {
let index = this._hash(key);
if (this.keyMap[index] === null) {
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
}
抬头
这仅花费 O(1) 的时间来查找存储桶，再加上循环遍历存储桶内的数组。
get(key) {
let target = this._hash(key);
if (this.keyMap[target]) {
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[target][i][0] === key) {
return this.keyMap[target][i][1];
}
}
}
return undefined;
}
可能，哈希表就是我所寻找的！
那么回到正题——什么样的数据结构适合我的 Chrome 扩展程序项目的主要数据？数据是一个词汇表，它看起来像这样：
// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}
只接受唯一的单词，这样我们就可以将其作为键来实现。我可以简单地将其实现为 Object：
MainData = {}
class Word {
constructor(tag, category, definition) {
this.tag = tag
this.category = category
this.definition = definition
}
}
const saveWord = (word, tag, category, definition) => {
if (MainData[word] == null) {
MainData[word] = new Word(tag, category, definition)
} else {
alert('This word already exists in the list.')
}
}
通过此实现，主要数据将如下所示：
// Result of console.log(MainData)
arbitrary: { category: "Book1", meanings: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"]};
interpretation: { category: "Machine Learning", meanings: "the action of explaining the meaning of something", tag:["noun"]};
intuitive: { category: "Book2", meanings: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"]};
precision: { category: "Machine Learning", meanings: "the quality, condition, or fact of being exact and acurate", tag: ["noun"]};
删除/编辑每个对象仅需O(1)。
结论
到目前为止，我已经研究过几种数据结构，但到目前为止，哈希表似乎是最适合主要数据的结构。然而，我需要不断提醒自己这些话：
最好的并不总是最好的。我们需要务实地选择合适的算法——最快的算法并不总是最适合任务的。（摘自《程序员修炼之道》）
还有太多数据结构需要学习，JavaScript 的 Object 和 Map 也有很多知识需要了解。时刻保持进步的心态，这样我们才不会错失提升技能的机会。
参考
JavaScript 数据结构与算法大师班 - Udemy
JavaScript Hashmap 等效 - StackOverflow
使用 JavaScript Hashmap 的 5 种方法 - Sunfish Empire LLC
JavaScript 中的对象和哈希表 - Medium
哈希表 - 维基百科
JS 对象是哈希表吗？ - Quora
学习使用 JavaScript 哈希编码 - Codelikethis。
程序员修炼之道 - goodreads.com