Repository navigation
Expand file tree
/
Copy pathDictionary.js
More file actions
147 lines (131 loc) · 3.62 KB
/
Copy pathDictionary.js
File metadata and controls
147 lines (131 loc) · 3.62 KB
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//字典
var Dictionary = function () {
var items = {};
this.has = function (key) {
return items.hasOwnProperty(key);
//方法二
//return key in items
}
this.set = function (key, value) {
items[key] = value;
}
this.delete = function (key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
}
//根据key获取值
this.get = function (key) {
if (this.has(key)) {
return items[key];
}
return undefined;
}
// size方法
Dictionay.prototype.size = function () {
return this.keys().length
}
// clear方法
Dictionay.prototype.clear = function () {
this.items = {}
}
this.getItems = function () {
return items;
}
}
//字典的应用：哈希表(散列表)
var HashTable = function () {
var items = [];
//散列函数=>number=>items[number]
//通过ascii码转换 a=>97
var loseloseHashCode = function (key, value) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();
}
// 这里除以素数37是为了降低计算出重复hash的概率（后续会处理hash重复的问题）
return hash % 37;
}
this.put=function(key,value){
var position=loseloseHashCode(key);
items[position]=value;
}
this.remove=function(key){
items[loseloseHashCode(key)]=undefined;
}
this.get=function(key){
return items[loseloseHashCode(key)];
}
this.getItems=function(){
return items;
}
}
var HashTable2=function(){
var table=[];
var loseloseHashCode = function (key, value) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();
}
// 这里除以素数37是为了降低计算出重复hash的概率（后续会处理hash重复的问题）
return hash % 37;
}
var Node=function(key,value){
this.key=key;
this.value=value;
}
this.put=function(key,value){
var position=loseloseHashCode(key);
if(table[position]){
table[position].append(new Node(key,value));
}else{
var l=new LinkedList();
table[position]=l;
table[position].append(new Node(key,value));
}
}
this.get=function(key){
var position=loseloseHashCode(key);
if(table[position]){
//链表属性查找
var current=table[position].getHead();
while(current){
if(current.item.key==key){
return current.item.value;
}
current=current.next;
}
}else{
return undefined;
}
}
this.remove=function(key){
var position=loseloseHashCode(key);
if(table[position]){
var previous=null;
var current=table[position].getHead();
while(current.next){
if(current.item.key==key){
table[position].remove(current.item)
return true;
}
current=current.next
}
if(current.item.key==key){
table[position].remove(current.item)
if(table[position].isEmpty()){
table[position]=undefined;
}
return true;
}
return false;
}else{
return false;
}
}
this.getTable=function(){
return table;
}
}