数据结构-字典

前言

日常生活中我们经常会遇到查询的问题,在前面我们用到的大都是线性结构的数据结构存储数据,我们是否需要遍历线性结构来达到查找目的,这样显然是很不合理的。想必都用过字典,我们查找字得时候,只需要根据索引来查找,又快又准,我们依照字典创建一个索引结构,只需要根据关键字key来找到对应的内容(一一映射的关系),我们称之为字典。

字典特征

是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。哈希表的实现主要需要解决两个问题,哈希函数和冲突解决。

代码实现

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
var Dictionary = function(){
let 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 items[key]
}
this.keys = function(){
return Object.keys(items)
}
this.getItems = function(){
return items;
}
}

此结构的实现比较简单,就不一一介绍了。接下来介绍和字典相关散列表(又称哈希表)是怎么一回事。

散列表(哈希表)

何为哈希表?先举个例子,比如电话谱保存姓名,我们需要将姓名保存在字典里,键值对的key如何设置,让key呈现一定规律,方便比较,利于查询,同时不能重复。这里就得用到哈希算法,通过 ascii 码 计算不同的hash值(也称为散列值,一个16进制的数)来设置不同key.而这样的一个表就是所谓的哈希表。

哈希算法

哈希算法有两种实现方式。

  • loseloseHashCode算法(宽松算法)
  • djb2HashCode算法
    loseloseHashCode算法:
    1
    2
    3
    4
    5
    6
    7
    var loseloseHashCode = function(key){
    let hash = 0;
    for(let i=0; i< key.length; i++){
    hash += key[i].charCodeAt();
    }
    return hash%37;
    }

此算法说白了就是所有字符的 ascii 码的和取余,这个算法简单明了,但是不可避免出现哈希值相同的问题(例如Donie和Ana就一样),会造成值覆盖,这就是所谓的散列冲突,如何解决这个问题,这里有两种解决方案。

1、分离链式法:

在相同哈希值地址,创建一个链表,将hash值相同的数值依次存放在链表中,这样,查找的顺序就分两步,先找到哈希地址,然后在链表中查询信息。这样就能避免值覆盖的问题了。
缺点: 查询的效率并不是很高。

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
/**
* 分离链接法
* 缺点:牺牲了查找的便捷性
*/
var HashTable_L = function(){
var table = [];
var Node = function(key, value){
this.key = key;
this.value = value;
}
var loseloseHashCode = function(key){
let hash = 0;
for(let i=0; i< key.length; i++){
hash += key[i].charCodeAt();
}
return hash%37;
}

this.put = function(key, value){
let position = loseloseHashCode(key);
if(table[position]){
table[position].append(new Node(key, value));
}else{
let l = new LinkedList();
table[position] = l;
table[position].append(new Node(key, value));
}
}
// 查找
this.get = function(key){
let position = loseloseHashCode(key);
if(table[position]){
let current = table[position].getHead();
// 链表遍历
while(current){
if(current.element.key == key){
return current.element.value
}
current = current.next;
}
}else{
return undefined;
}
}
this.remove = function(key){
let position = loseloseHashCode(key);
if(table[position]){
let 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;
}
}else{
return false;
}
}
}

2、线性探测:
当出现哈希地址相同的情况,后面出现的在原有hash值上加1,能够避免hash不重复。
缺点:添加很麻烦,每次都得比较,比如多个相同hash值的字符,就得不断的往后查询加1.

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
/**
* 线性探查法
*/
var HashTable_X = function(){
var table = [];
var Node = function(key, value){
this.key = key;
this.value = value;
}
var loseloseHashCode = function(key){
let hash = 0;
for(let i=0; i< key.length; i++){
hash += key[i].charCodeAt();
}
return hash%37;
}
this.put = function(){
let position = loseloseHashCode(key);
if(table[position] == undefined){
table[position] = new Node(key, value);
}else{
// 这个位置已经被占据
let index = position+1;
while(table[index] !== undefined){
index++;
}
table[index] = new Node(key, value);
}
}

this.get = function(key){
return items[loseloseHashCode(key)].element.value;
}
}

上面两种方法,都有不尽人意的地方,有没有更好的方式,一步到位,不同的字符的hash码一定不相同,下面djb2HashCode算法就是解决这个问题的。

1
2
3
4
5
6
7
8
9
10
/**
* djb2HashCode函数彻底解决冲突,hash数不重复
*/
var djb2HashCode = function(key){
var hash = 5381;
for(let i = 0; i < key.length; i++){
hash = hash*33 + key[i].charCodeAt();
}
return hash % 1013;
}

至于这个算法的具体参数怎么来的,请参考地址,有兴趣看看。

坚持原创技术分享,您的支持将鼓励我继续创作!