小撒是一只好学的小鸭子，这天，小撒在学习算法
散列表实现了INSERT，SEARCH和DELETE的字典操作。在散列表中查找一个元素的期望时间是O(1)，而最坏情况下则是O(n)。
散列表的实现在于提供一个直接寻址技术。在这里我们认为数组下标取值是直接寻址的，因此我们将通过数组来实现散列表。我们将介绍什么是散列算法，以及什么是碰撞、如何处理碰撞。
散列函数
散列函数通常将一个键（例如一个字符串等）转换为一个自然数（对应数组的下标），从而实现直接寻址。
一个好的散列函数，应当是尽可能均匀分布的，并且散列值与键的相似度尽可能无关。想象如果我们需要在一个散列表中存储一系列手机号，而我们的数据恰好都是173开头的，我们自然不希望这些键的散列值因此频繁发生碰撞。
通常使用的散列方法包括除法散列、乘法散列、全域散列。
其中全域散列的目的是避免最差情况：所有散列后的值进入同一个槽中。因此全域散列将设计一系列将关键字散列至[0, m-1]的散列函数|H|，它们满足对于所有的不相等关键字x和y，使x和y的散列值相等的散列函数的个数等于|H|/m。在散列表创建时，随机从中选择一个散列函数并使用，如果对于某个特定的数据集冲突频繁，那重新选择一个并重建散列表就好啦~
关于全域散列具体的内容小撒在这里就不展开啦（因为小撒并不懂_(:3」∠)_）~
碰撞
由于用于存储数据的数组的长度是固定的，而键是多变的，因此就可能会发生冲突（或称碰撞，Collision）。为了解决碰撞，我们通常会使用链接法与开放寻址法。
链接法
链接法处理碰撞的方式为，在每一个槽中使用链表来存储数据，如果新加入的数据的键的哈希发生了冲突，则把它放进链表。需要注意的是我们不仅要把值放入链表，也需要将原本的键一同放入链表，这样在查找时才能确定哪一个是我们的数据。
使用链接法，插入的性能为O(1)，而查找在最糟的情况下则是O(n)（全部进入同一个槽从而创建了长长的链表）。
开放寻址法
在开放寻址法中，如果散列发生了碰撞，则对散列的结果再次散列，直至寻找到空槽。因此在散列函数的设计上，我们要使得散列函数能遍历到所有的槽。
在开发寻址法中，描述散列表拥挤程度的装载因子 = 关键字个数 / 槽个数将不会大于1。
代码实现（Javascript）
最后，我们将参照Java中的HashMap来实现一个接受以字符串作为键的散列表：
const Symbols = {
array: Symbol('array'),
hash: Symbol('hash'),
size: Symbol('size'),
};
class HashMap {
constructor() {
this[Symbols.array] = [];
this[Symbols.size] = 0;
}
size() {
return this[Symbols.size];
}
has(key) {
const index = this[Symbols.hash](key);
return !!this[Symbols.array][index];
}
get(key) {
const index = this[Symbols.hash](key);
const list = this[Symbols.array][index];
if (!list) return undefined;
let value;
list.some((item) => {
if (item.key === key) {
value = item.value;
return true;
}
return false;
});
return value;
}
set(key, value) {
const index = this[Symbols.hash](key);
let list = this[Symbols.array][index];
if (!list) {
list = this[Symbols.array][index] = [];
}
const found = list.some((item) => {
if (item.key === key) {
item.value = value;
return true;
}
return false;
});
if (!found) {
list.push({
key,
value,
});
this[Symbols.size] += 1;
}
}
[Symbols.hash](key) {
let hashCode = 0;
for (let i = 0; i < key.length; i++) {
hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
}
return hashCode;
}
}
关于ASCII码请参考这里。
这里对于碰撞我们使用了链接法来处理，大家可以使用Aa和BB，AaBB和BBAa等来测试发生碰撞的情况。
大家也许注意到了(hashCode << 5) - hashCode的操作，其实这就是相当于hashCode * 31，不过我们手动通过位移操作进行了优化。而整型的溢出会自然而然的进行取模操作。
这里我们没有实现散列表的删除、获取所有键等方法。同时我们（相当于）在一开始就创建了一个巨大的数组，而Java中的哈希表为了合理利用内存还进行了复杂的resize操作。感兴趣的童鞋可以自己了解一下~
网友评论