《Javascript数据结构和算法》笔记-「字典和散列表」
《Javascript数据结构和算法》笔记-「字典和散列表」
集合、字典、散列表存储的都是「不重复」的数据结构
- 集合：我们更关注每一个元素的值，并把其作为主要元素
- 字典：我们用[键,值]的形式来存储数据
- 散列表： 跟字典类似，也会是用[键,值]的形式来存储数据
但是「字典」和「散列表」的实现方式略有不同。
字典
字典也称作映射。我觉得这种数据结构，其实在业务代码中的应用很常见。
与Set类似，ES6同样实现了一个Map类，即我们所说的字典
字典的大致骨架
function Dictionary(){
var items = {}
}
this.set = function(key,value){}
this.get = function(key){}
this.delete = function(key){}
this.has = function(key){}
this.clear = function(){}
this.size = function(){}
this.keys = function(){} // 将字典所包含的所有键，以一个数组返回
this.values = function(){} // 将字典所包含的所有值，以一个数组返回字典类的实现，十分简单就直接粘贴全部代码了。
我觉得在JS中，对象本身就可以作为字典来使用。我经常在业务代码中把数据处理成这种字典的数据结构
function Dictionary() {
var 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 ) {
if ( this.has( key ) ) {
return items[ key ]
} else {
return undefined
}
}
this.values = function(){
return Object.values(items)
}
this.keys = function(){
return Object.keys(items)
}
this.clear = function(){
this.items = {}
}
this.size = function(){
return this.keys().length
}
this.getItems = function(){ // 获取items的方法
return items
}
}
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(dictionary.getItems())哈希表
在学习了Dictionary类之后，我们会学习散列表，也就是哈希表。它是Dictionary类的另外一种实现方式
我在读到这里时，对于「字典」和「哈希表」2个慨念之间的区别还没弄清，当然书中也没有太多解释。
所以这里，我写记录一下自己查阅资料后的个人理解
「字典」指的是Key-Value这种存储数据的结构
那么哈希表也是字典，但是它是用另外的一种实现方式来做的。
那么我们我为什么要使用这种方式来实现「字典」呢，是不是字典存在某种缺点呢？
是的，比如说这样的一组字典数据
k1, k2, k3, k4, k4 .... v1, v2, v3, v4, v5 ....
当你输入key，命令电脑查询key对应的value时，电脑其实是没法立刻找到key所对应的value呢
看上去是直接根据key得到value，但实际上电脑还是需要遍历k1、k2、k3去比较kn是否等于key。如果是的话就取出对应的值
那么为了省去这个遍历的过程，才想到用哈希表来实现「字典」
哈希表利用数组实现「字典」这种数据结构，那么用数组来实现字典的话，用户传入的key对应哪个索引呢？所以我们需要一个「散列算法」
「散列算法」，可以求出这个key在数组里对应的位置，用哈希表实现的目的就是尽可能快地在字典中找到一个值。
function HashTable(){
let table = []
// 散列算法
var loseloseHashCode = function(key){
var hash = 0;
for(var i = 0 ; i<key.length ; i++){
hash += key.charCodeAt(i)
}
return hash % 37 // 这里37是个随意选择的数值，把余数作为将来存储在数组的索引
}
this.put = function(key,value){
var position = loseloseHashCode(key)
console.log(position + '-' + key)
table[position] = value
}
this.get = function(key){
var position = loseloseHashCode(key)
return table[position]
}
this.remove = function(key){
var position = loseloseHashCode(key)
table[position] = undefined
}
}哈希表的key值冲突
我们哈希表的散列算法，是为求出用户传入的key所对应的一个索引
那么这个索引是有可能重复的，一旦重复就会导致后面的值覆盖前面的值。
这种情况，叫做哈希表的冲突。所以我们了解2种处理冲突的方法原理
- 分离链接: 把数组的每一个元素都实例成链表结构。这样key相同的值，也可以用单链表的形式不断存储。不会覆盖
- 线性探查: 当用散列算法求出的这个索引index重复时，就index++，直到index不重复为止。
实现更好的散列函数
之前实现的'lose lose'散列函数，用来求值其实是非常容易产生key冲突的。
如果经常冲突的话，那么插入和查询一个元素的时间就会变慢(性能变差)
所以一个优秀的散列算法，应该是可以尽可能少出现冲突的
这里给出一个比较好的社区的实现。至于为什么这种算法,可以减少冲突我也不太理解，
可能是hash是质数，然后质数*33,最后在跟1013取模的话，不太会产生一样的余数，这个感觉是数学问题。
var djb2HashCode = function(key){
var hash = 5381
for(var i = 0 ; i < key.length ; i++){
hash = hash*33 + key.charCodeAt(i)
}
return hash % 1013
}简单回顾一下，集合、字典、哈希表吧
首先他们的元素都是不重复的
- 集合： 是无序的，[value value]的形式的一组数据结构
- 字典： 是由一对对 [key-value] 组成的数据结构
- 哈希表： 是字典的另外一种实现方式，优点在于可能更快的根据key取到value
记录一下书中没搞清楚的小疑问：
《javascript数据结构和算法》中多次提到「顺序数据结构」和「非顺序数据结构」的慨念，并表示 - 「顺序数据结构」：栈、队列、数组、链表、集合 - 「非顺序数据结构」: 散列表 、 树 可是我觉得链表、集合是无序的，数组是有序的呀 这个「顺序数据结构」似乎并不是指的在内存中存储形式。问题先记下，回头再查把