散列表 - 数据结构训练营

列表非常擅长处理最后一个元素的访问等操作。 然而,正如之前的课程所示,它不太擅长处理不在列表末尾的元素,并且需要手动处理内存地址。 因此,来学习一个新的的数据结构,看看它如何处理添加、访问和删除元素而无需知道内存地址。 哈希表是一种无序的数据结构。 它有“键”和“值”,使用键来计算内存中的地址。 核心思路是我们拥有“可散列”的键(将在稍后介绍),可以用它非常高效地从内存中添加、访问和删除元素。 var hashTable = new HashTable(); hashTable.set('myKey', 'myValue'); hashTable.get('myKey'); // >> 'myValue' 实现散列表数据结构可以提供以下一些运算: 一个生成空散列表的构造函数; 确定散列表元素的运算; 向散列表插入元素的运算; 删除散列表元素的运算; 下面我们将依次介绍其实现。 一个生成空散列表的构造函数 和列表一样,我们还是使用一个普通的 JavaScript 数组来代表内存。 constructor() { this.memory = []; } 为了将哈希表中的键值对存储在内存中,需要一种方法来获取键并将其转换为地址。 也就是“散列”的操作。 本质上,需要一个 key 并将其序列化为该 key 的唯一编号。 hashKey("abc") => 96354 hashKey("xyz") => 119193 但是必须要小心,如果有一个非常大的密钥,将它与不存在的内存地址匹配起来就糟了。 所以散列算法需要限制大小,这意味着对于无限数量的值,需要存储在数量有限的地址里。 最终结果是会发生散列冲突。 两个 key 指向同一个内存地址。 任何真实世界的哈希表实现都必须考虑到这个问题,这里我们只是了解一下并假装其不会发生。 来看一下我们实现的“hashKey”函数。 不用理解这个函数的逻辑,只要知道它接受一个字符串并输出一个我们将在所有其他函数中使用的(大概率)唯一的地址就可以了。 hashKey(key) { let hash = 0; for (let index = 0; index < key.length; index++) { let code = key.charCodeAt(index); hash = ((hash << 5) - hash) + code | 0; } return hash; } 确定散列表元素的运算 接下来,定义“get”函数,这样就有了通过键访问值的方法。 我们首先将 key 转换为地址。然后返回该地址的内容。 散列表访问复杂度是常数 O(1) - “太棒了!!” get(key) { } 向散列表插入元素的运算 还需要在访问数据之前添加数据的方法,创建一个插入元素的“set”函数。 再次将 key 转换为地址。然后在该地址处设置该值。 散列表插入值的复杂度是常数 O(1) - “太棒了!!” set(key, value) { } 删除散列表元素的运算 最后,需要一种从散列表中删除元素的方法。 与之前一样,散列 key 以获取地址。如果它存在,我们就 delete 它。 散列表删除复杂度是常数 O(1) - “太棒了!!” remove(key) { } push 和 pop 都在列表的末尾进行操作,总的来说是非常简单的操作,因为它们不需要关心列表的其余部分。让我们看看当我们在列表的开头使用 unshift 和 shift 操作时会发生什么。
使用正确的数据结构可以大大简化原本复杂的逻辑。如果很注重性能或想节约内存,那么就需要选择正确的数据结构。来和我一起用 JavaScript 语言来实现一些常用数据结构吧。


运行