数据结构-字典和散列表

集合、字典和散列表可以存储不重复的值。在集合中,我们感兴趣的是每个值本身,并把它当做主要元素。在字典中,我们用[键,值]的形式来存储数据。在散列表中也是一样(也是以[键,值]对的形式来存储数据)。但是两种数据结构的实现方式略有不同。

字典

与Set类相似,ECMAScript 6 同样包含了一个Map类的实现,即我们所说的字典。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
function Dictionary() {
var items = {};
// 如果某个键值存在于这个字典中,则返回true,反之则返回false
this.has = function(key) {
return key in items;
};
// 向字典中添加新元素
this.set = function(key, value) {
items[key] = value;
};
// 通过使用键值来从字典中移除键值对应的数据值。
this.remove = 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.values = function() {
var values = [];
for (var k in items) {
if (this.hasOwnProperty(k)) {
values.push(items[k]);
}
}
return values;
};
// 将字典所包含的所有数据的key以数组形式返回
this.keys = function() {
var values = [];
for (var k in items) {
if (this.hasOwnProperty(k)) {
values.push(k);
}
}
return values;
};
// 移除字典中的所有项
this.clear = function(){
items = {};
};
// 返回字典中包含的元素数量
this.size = function(){
return Object.keys(items).length;
};
// 获取字典
this.getItem = function() {
return items;
};
}

散列表

散列算法的作用是尽可能快地在数据结构中找到一个值。使用散列函数,就知道值地具体位置,因此能够快速检索到该值。散列函数地作用是给定一个键值,然后返回值在表中地地址。

创建一个散列表

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
26
27
28
29
function HashTable(){
var table = [];
// 散列函数
var loseHashCode = function(key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
// 向散列表增加一个新地项(也能更新散列表)
this.put = function(key, value) {
var position = loseHashCode(key);
console.log(position + ' - ' + key);
taable[position] = value;
};
// 返回根据键值检索到地特定地值
this.get = function(key) {
return table[loseHashCode(key)];
};
// 根据键值从散列表中移除值
this.remove = function(key) {
table[loseHashCode(key)] = undefined;
};
}

处理散列表中地冲突

有时候,一些键会有相同地散列值。不同地值在散列表中对应相同位置地时候,我们称其为冲突。当这种情况发生时我们需要取解决它。处理冲突有几种方法:分离链接、线性探查和双散列发。

分离链接

分离链接法包括为散列表地每一个位置创建一个链表并将元素存储在里面。他是解决冲突最简单地方法,但是它在HashTable实例之外还需要额外地存储空间。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
function HashTable(){
var table = [];
// 散列函数
var djb2HashCode = function(key) {
var hash = 5381;
for (var i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i);
}
return hash % 1013;
};
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].append(new ValuePair(key, value));
};
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;
}
};
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;
};
}

更好的散列函数

一个表现良好的散列函数是由几个方面构成的:插入和检索元素的时间(即性能),当然也包括较低的冲突的可能性。前面实现的散列函数并不是一个表现良好的散列函数,因为它会产生太多的冲突。我们可以实现一个更好的散列函数:

1
2
3
4
5
6
7
var djb2HashCode = function(key){
var hash = 5381;
for (var i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i);
}
return hash % 1013;
};