学习《JavaScript 数据结构与算法》读书笔记
7 字典和散列表
7.1 字典
在字典中，存储的是 [键, 键] 对，其中键名是用来查询特定严肃的。字典和集合很相似，集合以 [值, 值] 的形式存储元素，字典则是以 [键, 键] 的形式来存储元素。字典也被称作 映射 。
7.1.1 创建字典
与 Set 类相似，ECMAScript 6 同样包含了一个 Map 类的实现，即我们所说的字典。
1
2
3
| function Dictionary() {
var items = {};
}
|
1. has 和 set 方法
1
2
3
| this.has = function(key) {
return items.hasOwnProperty(key);
};
|
1
2
3
| this.set = function(key, value) {
items[key] = value;
};
|
2. delete 方法
1
2
3
4
5
6
7
| this.delete = function(key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
};
|
然后我们可以使用 JavaScript 的 remove 操作符来从 items 对象中移除 key 属性。
3. get 和 values 方法
1
2
3
| this.get = function(key) {
return this.has(key) ? items[key] : undefined;
};
|
1
2
3
4
5
6
7
8
9
| this.values = function() {
var values = [];
for (var k in items) {
if (this.has(k)) {
values.push(items[k]);
}
}
return values;
};
|
4. clear 、 size 、 keys 和 getItems 方法
1
2
3
| this.clear = function () {
items = {};
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| this.size = function() {
return Object.keys(items).length;
};
this.sizeLegacy = function() {
let count = 0;
for (let key in items) {
if (items.hasOwnProperty(key)) {
++count;
}
}
return count;
};
|
1
2
3
| this.keys = function() {
return Object.keys(items);
};
|
1
2
3
| this.getItems = function() {
return items;
};
|
7.1.2 使用 Dictionary 类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var dictionary = new Dictionary();
dictionary.set('Gandalf', '[email protected]');
dictionary.set('John', '[email protected]');
dictionary.set('Tyrion', '[email protected]');
console.log(dictionary.has('Gandalf'));
console.log(dictionary.size());
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.get('Tyrion'));
dictionary.delete('John');
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dicitonary.getItems());
|
7.2 散列表
HashTable 类，也叫 HashMap 类，它是 Dictionary 类的一种散列表实现方式。
散列算法 的作用是尽可能快地在数据结构中找到一个值。在之前的章节中，已经知道如果要在数据结构中获得一个值（get），需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。
举个栗子，我们使用电子邮件地址簿。我们将要使用最常见的散列函数 lose lose 散列函数，方法时简单地将每个键值中的每个字母的ASCII值相加
7.2.1 创建散列表
1
2
3
| function HashTable() {
var table = [];
}
|
1
2
3
4
5
6
7
| var loseloseHashCode = function(key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
|
1
2
3
| this.put = function(key) {
return table[loseloseHashCode(key)];
}
|
1
2
3
| this.remove = function(key) {
table[loseloseHashCode(key)] = undefined;
}
|
7.2.2 使用 HashTable 类
1
2
3
4
5
6
7
8
9
10
| var hash = new HashTable();
hash.put('Gandalf', '[email protected]');
hash.put('John', '[email protected]');
hash.put('Tyrion', '[email protected]');
console.log(hash.get('Gandalf'));
console.log(hash.get('Loiane'));
hash.remove('Gandalf');
console.log(hash.get('Gandalf'));
|
7.2.4 处理散列表中的冲突
有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。
同一散列值，最后一个被添加的，会将与之冲突的元素覆盖。
使用一个数据结构来保存数据的目的显然不是去丢失这些数据，而是通过某种方法将它们全部保存起来。处理冲突有几种方法：分离链接、线性探查、双散列法
1. 分离链接
分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在 HashTable 实例之外还需要额外的存储空间。
即在冲突的散列值位置，添加所有元素的 LinkedList 实例。
对于分离链接和线性探查来说，只需要重写 put 、 get 、 remove 。
为了实现一个使用分离链接的 HashTable 实例，我们需要一个新的辅助类来表示将要加入的 LinkedList 实例的元素。我们管它加 ValuePair 类。
1
2
3
4
5
6
7
| var ValuePair = function(key, value) {
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
|
1
2
3
4
5
6
7
| this.put = function(key, value) {
var position = loseloseHashCode(key);
if (table[position] === undefined) {
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key, value));
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| this.get = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
var current = table[position].getHead();
while(current.next) {
if (current.element.key === key) {
return current.element.value;
}
current = current.next;
}
if (current.element.key === key) {
return current.element.value;
}
}
return undefined;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| this.remove = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined) {
var current = table[position].getHead();
while (current.next) {
if (current.element.key === key) {
table[position].remove(current.element);
if (table[position].isEmpty()) {
table[position] = undefined;
}
return true;
}
current = current.next;
}
if (current.element.key === key) {
table[position].remove(current.element);
if (table[position].isEmpty()) {
table[position] = undefined;
}
return true;
}
}
return false;
};
|
2.线性探查
当想向表中某个位置加入一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+1 的位置。如果 index+1 的位置也被占据了，就尝试 index+2 的位置，以此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
| this.put = function(key, value) {
var position = loseloseHashCode(key);
if (table[position] === undefined) {
table[position] = new ValuePair(key, value);
} else {
var index = ++position;
while (table[inedx] !== undefined) {
index++;
}
table[index] = new ValuePair(key, value);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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;
};
|
remove 方法和 get 方法基本相同，只需要把 return table[index].value; 替换为 table[index] = undefined;
7.2.5 创建更好的散列函数
一个表现良好的散列函数由几个方面构成：插入和检索元素的时间（即性能），当然也包括较低的冲突可能性。
另一个可以实现的比 lose lose 更好的散列函数是 djb2
1
2
3
4
5
6
7
8
9
10
11
12
| var djb2HashCode = function(key) {
var hash = 5381;
for (var i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i);
}
return hash % 1013;
};
|
这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。
7.3 ES6 Map类
1
2
3
4
5
6
7
8
9
10
11
| var map = new Map();
map.set('Gandalf', '[email protected]');
map.set('John', '[email protected]');
map.set('Tyrion', '[email protected]');
console.log(map.has('Gandalf'))
console.log(map.size)
console.log(map.keys())
console.log(map.values())
console.log(map.get('Tyrion'))
|
ES6 的 Map 类的 values 方法和 keys 方法都返回 Iterator ，而不是值或键构成的数组。
删除 map 中的元素可以用 delete 方法：
clear 方法会重置 map 数据结构。
7.4 WeakMap 类和 WeakSet 类
除了 Set 和 Map 这两种新的数据结构，ES6还增加了它们的弱化版本 WeakSet 和 WeakMap
WeakSet 或 WeakMap 类没有 entries 、 keys 和 values 方法
只能用对象作为键
创建和使用这两个类主要是为了性能。 WeakSet 和 WeakMap 是弱化的（用对象作为键），没有强引用的键。这使得 JavaScript 的垃圾回收期可以从中清除整个入口。
另一个优点是，必须用键才可以去取出值。这些类没有 entries 、 keys 和 values 等迭代器方法，因此，除非知道键，否则没有办法取出值。
1
2
3
4
5
6
7
8
9
10
11
12
| var map = new WeakMap();
var ob1 = {name: 'Gandalf'},
ob2 = {name: 'John'},
ob3 = {name: 'Tyrion'};
map.set(ob1, '[email protected]');
map.set(ob2, '[email protected]');
map.set(ob3, '[email protected]');
console.log(map.has(ob1));
console.log(map.get(ob3));
map.delete(ob2);
|
同样的逻辑也适用于 WeakSet 类。