Fork me on GitHub

散列

algorithm/hash/banner

散列是一种常用的数据存储技术,散列后的数据可以进行快速地插入或取用。散列使用的数据结构叫做散列表(hash table, 也叫哈希表)。在散列表中插入、删除和取用数据都非常快,但是对于查找操作来说却效率低下,比如查找一组数据中的最大或者最小值。

散列算法的作用是尽可能快地在数据结构中找到一个值。在前面几个博文中提到的数据结构,我门如果在数据结构中获取一个值(使用get方法),需要遍历整个数据库来找到它。如果使用散列函数,就知道值的具体位置,因此你能够快速检索到该值。散列函数的作用是给定一个键值,然后返回值在表中的地址。

见下图的例子(散列函数这里取ascii值相加-电子邮件地址薄):

algorithm/hash/email-demo

创建一个散列表

搭建散列表类如下:

1
2
3
4

function HashTable() {
var table = [];
}

简单的散列函数如下(取上图的ascii值):

1
2
3
4
5
6
7
8

var loseloseHashCode = function(key) {
var hash = 0;
for(var i = 0; i < key.length; i++){
hash += key.charCodeAt(i);
}
return hash % 37;
}

基本完整代码

hash表的简单demo的基本完整代码如下:

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

var loseloseHashCode = function(key) {
var hash = 0;
for(var i = 0; i < key.length; i++){
hash += key.charCodeAt(i);
}
return hash % 37;
}

function HashTable() {
var table = [];

// 向散列表中增加一个新的项(也能更新散列表)
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;
}
}

上面的简单的完整代码中,展示了hash的思想,但是,发生冲突,又该怎么解决呢?

处理冲突

介绍处理数据位置相同,覆盖之前数据方法。这里用到之前学习的数据结构,感兴趣的人儿请自动前翻。

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。他是解决冲突的最简单的方法,但是它在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
// 我们需要一个辅助类来表示将要加入LinkedList实例的元素,这里我们称ValuePair
var ValuePair = function(key,value){
this.key = key;
this.value = value;
this.toString = function(){
return `[${this.key} - ${this.value}]`;
}
}

//put 方法
this.put = function(key,value){
var position = loseloseHashCode(key);
if(table[position] == undefined){
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key,value));
}

// get 方法
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;
}

// remove 方法
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;
}

线性探查

当想向表中某个位置加入一个新元素的时候,如果索引为index的位置被占据了,就尝试index+1的位置。如果index+1的位置也被占用了,就尝试index+2的位置,以此类推。

相关的方法如下:

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
// put 方法
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[index]!=undefined){
index++;
}
table[index] = new ValuePair(key,value);
}
}

// get 方法
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 方法
this.remove = function(key){
var position = loseloseHashCode(key);
if(table[position] !== undefined){
if(table[position].key === key){
table[index] = undefined;
}else {
var index = ++position;
while(table[index] === undefined || table[index].key !== key){
index++;
}
if(table[index].key === key){
table[index] = undefined;
}
}
}
return undefined;
}

备注:详细内容请前往《javascript数据结构与算法》

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)