第7章 字典和散列表 (Dictionary and HashT
2020-08-07 本文已影响0人
晓风残月1994
集合、字典和散列表可以存储不重复的值，在集合中，感兴趣的是每个值本身，并作为主要元素。而在字典和散列表中是以键值对的形式来存储数据。
1. 字典
字典也叫映射，集合以 [值, 值] 的形式来存储数据，而字典以 [键, 值] 的形式来存储数据。ES6 中的 Map 类就是字典。
- set(key,value)：向字典中添加新元素。
- delete(key)：通过使用键值来从字典中移除键值对应的数据值。
- has(key)：如果某个键值存在于这个字典中，则返回true，反之则返回false。
- get(key)：通过键值查找特定的数值并返回。
- clear()：将这个字典中的所有元素全部删除。
- size()：返回字典所包含元素的数量。与数组的length属性类似。
- keys()：将字典所包含的所有键名以数组形式返回。
- values()：将字典所包含的所有数值以数组形式返回。
/**
* 非常简单，仅仅是使用对象本身来存储字典的键值对
*/
function Dictionary() {
var items = {};
this.has = function (key) {
return items.hasOwnProperty(key);
};
this.set = function (key, value) {
items[key] = value;
};
this.delete = function (key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
};
this.get = function (key) {
return this.has(key) ? items[key] : undefined;
};
this.keys = function () {
return Object.keys(items);
};
this.values = function () {
return Object.keys(items).map(key => items[key]);
};
this.clear = function () {
items = {};
};
this.size = function () {
return Object.keys(items).length;
};
// 纯粹为了验证items
this.getItems = function () {
return items;
};
}
2. 散列表
散列表（散列映射），是 Dictionary 类的一种散列表实现方式，叫做 HashTable 类，也叫做 HashMap 类。散列算法的作用是尽可能快地在数据结构中找到一个值，给定一个键值，然后返回值在表中的地址。
最简单的散列算法应该就是 lose lose 散列函数，仅仅是简单地将每个键值中的每个字母的 ASCII 码相加。
image.png
2.1 创建散列表
- ** **put(key,value)：向散列表增加一个新的项（也能更新散列表）。
- remove(key)：根据键值从散列表中移除值。
- get(key)：返回根据键值检索到的特定的值。
/**
* 散列表，基于 lose lose 哈希算法
* 键需要是字符串，值可以是任意类型
* @constructor
*/
function HashTable() {
var table = [];
/**
* 散列函数 lose lose
*
* @param {string} key
* @returns {number}
*/
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i); // 将键值中的每个字母的ASCII值相加
}
return hash % 37; // 为了得到较小的值，和一个数取余，最后数组的存储范围是 0~36
};
this.put = function (key, value) {
var position = loseloseHashCode(key);
console.log(position + ' - ' + key);
table[position] = value;
};
this.get = function (key) {
return table[loseloseHashCode(key)];
};
this.remove = function (key) {
table[loseloseHashCode(key)] = undefined;
};
// 纯粹为了验证table
this.getTable = function () {
return table;
};
}
2.2 散列表和散列集合
在一些编程语言，比如 Java 中，除了 HashMap 还有 HashSet，其实在 Java 中，HashSet 内部就是个 HashMap。散列集合就是 散列函数 + 集合，完全可以重用散列表的实现，只是不再添加键值对，而是只插入值而没有键。
2.3 处理散列表中的冲突
lose lose 散列函数虽然简单，但是冲突率比较高。事实上，再好的散列算法也可能产生哈希冲突，因此需要解决冲突，毕竟数据结构用来保存数据而不是用来丢失的。
2.3.1 分离链接
为散列表的每一个有数据的位置创建一个链表用来存储元素。手段简单，但同时也需要额外的存储空间。
image.png
/**
* 解决hash冲突: 分离链接法
*
* 以下实现中是本人基于书中进行改良，推荐！
* 当发生hash碰撞时，或者重复的key时，都会向表头添加键值对，
* 即使key重复，当get时也能就近获取最近一次设置的value
*
* @constructor
*/
function HashTable() {
var table = [];
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
// 键值对辅助类
var ValuePair = function (key, value) {
this.key = key;
this.value = value;
this.toString = function () {
return '[' + this.key + ' - ' + this.value + ']';
};
};
this.put = function (key, value) {
var position = loseloseHashCode(key);
if (table[position] === undefined) {
table[position] = new LinkedList();
}
table[position].insert(0, new ValuePair(key, value)); // 插入到表头
};
this.get = function (key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
// 遍历链表寻找键值对
var current = table[position].getHead();
while (current) {
if (current.element.key === key) {
return current.element.value;
}
current = current.next;
}
}
return undefined;
};
this.remove = function (key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
var current = table[position].getHead();
while (current) {
if (current.element.key === key) {
table[position].remove(current.element);
if (table[position].isEmpty()) { // 不留下空链表
table[position] = undefined;
}
return true;
}
current = current.next;
}
}
return false;
};
// 纯粹为了验证table
this.getTable = function () {
return table;
};
}
2.3.2 线性探查
当向散列表中某个哈希位置添加新元素时，若位置已被占用，则尝试下一个位置，以此类推。
/**
* 解决hash冲突: 线性探查法
*
* 以下纯粹来自书中实现，但其实有不少问题，不推荐！
*
* @constructor
*/
function HashTable() {
var table = [];
/**
* 散列函数 lose lose
*
* @param key
* @returns {number}
*/
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
// 键值对辅助类
var ValuePair = function (key, value) {
this.key = key;
this.value = value;
this.toString = function () {
return '[' + this.key + ' - ' + this.value + ']';
};
};
this.put = function (key, value) {
var position = loseloseHashCode(key);
console.log(position + ' - ' + key);
var pair = new ValuePair(key, value);
// 当目标位置被占用时尝试position++的位置
if (table[position] === undefined) {
table[position] = pair;
} else {
var index = ++position;
while (table[index] !== undefined) {
index++;
}
table[index] = pair;
}
};
this.get = function (key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
if (table[position].key === key) {
return table[position].value;
} else {
var index = ++position;
while (
table[index] === undefined ||
table[index].key !== key
) {
index++;
}
if (table[index].key === key) {
return table[index].value;
}
}
}
return undefined;
};
this.remove = function (key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
if (table[position].key === key) {
table[position] = undefined;
} else {
var index = ++position;
while (
table[index] === undefined ||
table[index].key !== key
) {
index++;
}
if (table[index].key === key) {
table[index] = undefined;
}
}
}
};
// 纯粹为了验证table
this.getTable = function () {
return table;
};
}
2.4 更好的散列函数 djb2
lose lose 散列函数过于简单、冲突太多，极端情况下退化为链表，失去了散列数组快速访问元素的意义。
因此，一个良好的散列函数既要计算的快，又要冲突少。djb2 是目前最受社区推崇的散列函数之一。
/**
* djb2 散列算法
*
* @param {string} key
* @returns {number}
*/
function djb2HashCode(key) {
var hash = 5381; // 大多数实现都使用 5381
for (var i = 0; i < key.length; i++) {
hash = hash * 33 + hash.charCodeAt(i);
}
return hash % 1013; // 控制下最终哈希值大小，假设散列表大小为1000
}
2.5 ES6中的Map、WeakMap、Set、WeakSet
ES6 中的 Map 和 Set 的 values 和 keys 方法返回的都是 Iterator 迭代器，而不是直接的数组。另外 size 是属性而不是方法。
Map 和 Set 与其弱化版本 WekMap 和 WeakSet 之间的区别是：
- WeakSet或WeakMap类没有entries、keys和values等方法；
- 只能用对象作为键。
