JavaScript 数据结构之散列表的创建(1)
一、什么是散列表
二、创建散列表
1.创建散列函数
2.put 方法
3.get 方法
4.delete 方法
三、使用散列表
四、总结
上一篇我们一篇JavaScript 数据结构之字典方法搞定了字典，这篇呢我们学习一个与字典非常相似的数据结构，散列表与字典基本一致，区别是字典存储的 key 是字符串，而散列表是一个数值（哈希值）。
到底如何理解散列表呢？下面进入正题。
一、什么是散列表散列表，也叫做哈希表，可以根据键（Key）直接访问数据在内存中存储的位置。
简单来说，散列表就是字典的另一种实现，它的优势是比字典能更快地找到一个值。在常规的字典操作中，使用get()方法获得一个值，需要遍历整个数据结构，这样明显会比较慢。
散列表为了让查找提速，使用了一个叫散列函数的方法，将 key 转换成一个由 Unicode 码组合而成的数值，这个数值被称为散列值。
最终在散列表中存储数据的结构是：散列值为 key，数据值为 value。这样查找数据时，就可以通过散列值直接定位位置，就好比数组下标一样直接定位元素，免去了整个数据结构的遍历，因此比字典的字符串定位要快上许多。
上述的概念如果比较难理解，看一张图你就明白了：
散列表还可以用来做数据库的索引。在关系型数据库如 MySQL 中，当你新建一张表并创建好了字段，你还可以为某些字段设置索引。设置索引是在散列表中存储了索引值和对应记录的引用，以便快速的找到数据。
当然了散列表还有其他应用，比如我们 JavaScript 当中的对象，那就是一个妥妥的散列表。
二、创建散列表和字典类 Dictionary 一样，用一个对象来存储所有键值对。
class HashMap {
constructor() {
this.table = {}
}
}
然后给类添加方法，主要是这三个：
put：向散列表增加/更新一个项
remove：根据键名移除键值
get：根据键名获取键值
当然还需要和上一篇一样的转换字符串函数：
function keyToString(item) {
if(item === null) {
return 'NULL'
}
if(item === undefined) {
return 'UNDEFINED'
}
if(item instanceof String) {
return `${item}`
}
return item.toString()
}
1.创建散列函数
散列函数就是开头说到的，将字符串转换为散列值的函数。
hashCode(key) {
if(typeof key === 'number') {
return key;
}
let tableKey = keyToString(key)
let hash = 0;
for(let i = 0; i < tableKey.length; i++) {
hash += tableKey.charCodeAt(i)
}
return Math.ceil(hash / 20);
}
上述代码中，hashCode 接受一个 key 值，首先判断参数 key 是否是一个数值，如果是则直接返回。否则的话将 key 值转换为字符串。
结下来的逻辑是，定义一个 hash 变量为 0，然后循环字符串的长度。在循环体内通过 charCodeAt 方法获取每个字母对应的 Unicode 编码，并将结果累加。
最后一行，返回 Math.ceil(hash / 20) 的值，这是什么意思呢？
其实作用非常简单，就是为了避免 hash 值过大，然后才将它除以一个数值然后取整。这里用的 20，你也可以根据你的是实际情况决定数值范围，改用其他数值。
2.put 方法现在我们有了自己的 hashCode 函数，下面来实现 put 方法。
put(key, value) {
if(key !== null && value !== null) {
let pos = this.hashCode(key)
this.table[pos] = new ValuePair(key, value)
return true;
}
return false;
}
put 方法与字典的 set 方法几乎一样，区别只是 table 的属性从 key 变成了 hash。这也是散列表与字典的不同之处，只需要确保 hash 唯一即可。
3.get 方法ValuePair 是上篇介绍的类，用来存储键值对。
从散列表中获取一个值也很简单。
get(key) {
let valuePair = this.table[this.hashCode(key)]
return valuePair ? valuePair.value : undefined;
}
首先通过前面创建的 hashCode 方法获取到 key 的 hash 值，然后在 table 中获取这个 hash 有没有匹配的 value。如果有则返回 value，无则返回 undefined。
最后一个方法是从散列表中删除一个项：
remove(key) {
let hash = this.hashCode(key)
if(this.table[hash]) {
delete this.table[hash]
return true;
}
return false;
}
以上就是散列表的全部实现，下面我们来使用。
三、使用散列表首先添加几个键值对：
var hashmap = new HashMap()
hashmap.put('name', '捷德')
hashmap.put('color', '红黑')
hashmap.put('father', '贝利亚')
console.log('name：', hashmap.hashCode('name')) // name：21
console.log('father：', hashmap.hashCode('father')) // father：32
我们用 hashCode 方法获取了 key 的 hash 值，是两个两位数的数字。
接着我们根据 key 获取 value：
console.log(hashmap.get("name")); // 捷德
console.log(hashmap.get("color")); // 红黑
console.log(hashmap.get("size")); // undefined
然后再删除一个 key：
console.log(hashmap.remove("color")); // true
console.log(hashmap.remove("size")); // false
console.log(hashmap.get("color")); // undefined
你看这三个方法在使用的过程中，和字典的效果几乎一致。我们在类内部实现的 hash 值，在使用类方法的时候是无感知的，只是内部数据存储的结构不同。
四、总结本篇介绍了很常用的散列表数据结构，你学会了吗？散列表与字典很相似，了解他们的区别非常关键。
不过本篇实现的散列表还有一个异常情况，就是生成的散列值可能重复，这样就会出现覆盖的情况。下一篇，我们介绍如何处理散列值的冲突。
