现在, 我们就给出哈希函数的实现:
function hashFunc(str, max) { // 1.初始化hashCode的值 var hashCode = 0 // 2.霍纳算法, 来计算hashCode的数值 for (var i = 0; i < str.length; i++) { hashCode = 37 * hashCode + str.charCodeAt(i) } // 3.取模运算 hashCode = hashCode % max return hashCode }
代码解析:
理解了前面所有的内容, 其实代码就非常简单了.
不再多做解释, 有不懂的可以留言或者查看前面的内容.
代码测试:
alert(hashFunc("abc", 7)) // 4 alert(hashFunc("cba", 7)) // 3 alert(hashFunc("nba", 7)) // 5 alert(hashFunc("mba", 7)) // 1 二. 哈希表经过前面那么多内容的学习, 我们现在可以真正实现自己的哈希表了.
可能你学到这里的时候, 已经感觉到数据结构的一些复杂性, 但是如果你仔细品味, 你也会发现它在设计时候的巧妙和优美, 当你爱上它的那一刻, 你也真正爱上了编程.
我们这里采用链地址法来实现哈希表:
实现的哈希表(基于storage的数组)每个index对应的是一个数组(bucket).(当然基于链表也可以.)
bucket中存放什么呢? 我们最好将key和value都放进去, 我们继续使用一个数组.(其实其他语言使用元组更好)
最终我们的哈希表的数据格式是这样: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ], [ [k,v] ] ]
创建哈希表
我们像封装其他数据结构一样, 先来创建一个哈希表的类: HashTable
// 创建HashTable构造函数 function HashTable() { // 定义属性 this.storage = [] this.count = 0 this.limit = 8 // 定义相关方法 // 哈希函数 HashTable.prototype.hashFunc = function(str, max) { // 1.初始化hashCode的值 var hashCode = 0 // 2.霍纳算法, 来计算hashCode的数值 for (var i = 0; i < str.length; i++) { hashCode = 37 * hashCode + str.charCodeAt(i) } // 3.取模运算 hashCode = hashCode % max return hashCode } }
代码解析:
我们定义了三个属性:
storage作为我们的数组, 数组中存放相关的元素.
count表示当前已经存在了多少数据.
limit用于标记数组中一共可以存放多少个元素.
另外, 我们直接将哈希函数定义在了HashTable中.
插入&修改数据
现在, 我们来做向哈希表中插入数据
// 插入数据方法 HashTable.prototype.put = function (key, value) { // 1.获取key对应的index var index = this.hashFunc(key, this.limit) // 2.取出数组(也可以使用链表) var bucket = this.storage[index] // 3.判断这个数组是否存在 if (bucket === undefined) { // 3.1创建桶 bucket = [] this.storage[index] = bucket } alert(bucket) // 4.判断是新增还是修改原来的值. var override = false for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] if (tuple[0] === key) { tuple[1] = value override = true } } // 5.如果是新增, 前一步没有覆盖 if (!override) { bucket.push([key, value]) this.count++ } }
代码解析:
步骤1: 根据传入的key获取对应的hashCode, 也就是数组的index
步骤2: 从哈希表的index位置中取出桶(另外一个数组)
步骤3: 查看上一步的bucket是否为null
为null, 表示之前在该位置没有放置过任何的内容, 那么就新建一个数组[]
步骤4: 查看是否之前已经放置过key对应的value
如果放置过, 那么就是依次替换操作, 而不是插入新的数据.
我们使用一个变量override来记录是否是修改操作
步骤5: 如果不是修改操作, 那么插入新的数据.
在bucket中push新的[key, value]即可.
注意: 这里需要将count+1, 因为数据增加了一项.
获取数据
有插入和修改数据, 就应该有根据key获取value
// 获取存放的数据 HashTable.prototype.get = function (key) { // 1.获取key对应的index var index = this.hashFunc(key, this.limit) // 2.获取对应的bucket var bucket = this.storage[index] // 3.如果bucket为null, 那么说明这个位置没有数据 if (bucket == null) { return null } // 4.有bucket, 判断是否有对应的key for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] if (tuple[0] === key) { return tuple[1] } } // 5.没有找到, return null return null }
代码解析:
步骤1: 根据key获取hashCode(也就是index)
步骤2: 根据index取出bucket.
步骤3: 因为如果bucket都是null, 那么说明这个位置之前并没有插入过数据.
步骤4: 有了bucket, 就遍历, 并且如果找到, 就将对应的value返回即可.
步骤5: 没有找到, 返回null
删除数据
我们根据对应的key, 删除对应的key/value
// 删除数据 HashTable.prototype.remove = function (key) { // 1.获取key对应的index var index = this.hashFunc(key, this.limit) // 2.获取对应的bucket var bucket = this.storage[index] // 3.判断同是否为null, 为null则说明没有对应的数据 if (bucket == null) { return null } // 4.遍历bucket, 寻找对应的数据 for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] if (tuple[0] === key) { bucket.splice(i, 1) this.count-- return tuple[1] } } // 5.来到该位置, 说明没有对应的数据, 那么返回null return null }
代码解析:
代码思路和查询基本一致, 不再给出解析过程. 也可以查看注释.
其他方法
判断哈希表是否为空: isEmpty
// isEmpty方法 HashTable.prototype.isEmpty = function () { return this.count == 0 }
获取哈希表中数据的个数
// size方法 HashTable.prototype.size = function () { return this.count }哈希表测试
我们来简单测试一下上面的代码
// 测试哈希表 // 1.创建哈希表 var ht = new HashTable() // 2.插入数据 ht.put("abc", "123") ht.put("cba", "321") ht.put("nba", "521") ht.put("mba", "520") // 3.获取数据 alert(ht.get("abc")) ht.put("abc", "111") alert(ht.get("abc")) // 4.删除数据 alert(ht.remove("abc")) alert(ht.get("abc")) 三. 哈希表扩容我们在来将讲一个哈希表的概念: 哈希表扩容.
哈希表扩容的思想
为什么需要扩容?
目前, 我们是将所有的数据项放在长度为8的数组中的.
因为我们使用的是链地址法, loadFactor可以大于1, 所以这个哈希表可以无限制的插入新数据.
但是, 随着数据量的增多, 每一个index对应的bucket会越来越长, 也就造成效率的降低.
所以, 在合适的情况对数组进行扩容. 比如扩容两倍.
如何进行扩容?
扩容可以简单的将容量增加大两倍(不是质数吗? 质数的问题后面再讨论)
但是这种情况下, 所有的数据项一定要同时进行修改(重新哈希化, 来获取到不同的位置)
比如hashCode=12的数据项, 在length=8的时候, index=4. 在长度为16的时候呢? index=12.
这是一个耗时的过程, 但是如果数组需要扩容, 那么这个过程是必要的.
什么情况下扩容呢?
比较常见的情况是loadFactor>0.75的时候进行扩容.
比如Java的哈希表就是在装填因子大于0.75的时候, 对哈希表进行扩容.
哈希表扩容的实现
我们来实现扩容函数
// 哈希表扩容 HashTable.prototype.resize = function (newLimit) { // 1.保存旧的数组内容 var oldStorage = this.storage // 2.重置属性 this.limit = newLimit this.count = 0 this.storage = [] // 3.遍历旧数组中的所有数据项, 并且重新插入到哈希表中 oldStorage.forEach(function (bucket) { // 1.bucket为null, 说明这里面没有数据 if (bucket == null) { return } // 2.bucket中有数据, 那么将里面的数据重新哈希化插入 for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] this.put(tuple[0], tuple[1]) } }.bind(this)) }
代码解析:
步骤1: 先将之前数组保存起来, 因为我们待会儿会将storeage = []
步骤2: 之前的属性值需要重置.
步骤3: 遍历所有的数据项, 重新插入到哈希表中.
在什么时候调用扩容方法呢?
在每次添加完新的数据时, 都进行判断. (也就是put方法中)
修改put方法
代码第5步中的内容
// 插入数据方法 HashTable.prototype.put = function (key, value) { // 1.获取key对应的index var index = this.hashFunc(key, this.limit) // 2.取出数组(也可以使用链表) // 数组中放置数据的方式: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ] [ [k,v] ] ] var bucket = this.storage[index] // 3.判断这个数组是否存在 if (bucket === undefined) { // 3.1创建桶 bucket = [] this.storage[index] = bucket } // 4.判断是新增还是修改原来的值. var override = false for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] if (tuple[0] === key) { tuple[1] = value override = true } } // 5.如果是新增, 前一步没有覆盖 if (!override) { bucket.push([key, value]) this.count++ // 数组扩容 if (this.count > this.limit * 0.75) { this.resize(this.limit * 2) } } }
如果我们不断的删除数据呢?
如果不断的删除数据, 当loadFactor < 0.25的时候, 最好将数量限制在一半.
修改remove方法
代码第4步中的内容
// 删除数据 HashTable.prototype.remove = function (key) { // 1.获取key对应的index var index = this.hashFunc(key, this.limit) // 2.获取对应的bucket var bucket = this.storage[index] // 3.判断同是否为null, 为null则说明没有对应的数据 if (bucket == null) { return null } // 4.遍历bucket, 寻找对应的数据 for (var i = 0; i < bucket.length; i++) { var tuple = bucket[i] if (tuple[0] === key) { bucket.splice(i, 1) this.count-- // 缩小数组的容量 if (this.limit > 8 && this.count < this.limit * 0.25) { this.resize(Math.floor(this.limit / 2)) } } return tuple[1] } // 5.来到该位置, 说明没有对应的数据, 那么返回null return null } 四. 容量质数我们前面提到过, 容量最好是质数.
虽然在链地址法中将容量设置为质数, 没有在开放地址法中重要, 但是其实链地址法中质数作为容量也更利于数据的均匀分布. 所以, 我们还是完成一下这个步骤.
判断质数
我们这里先讨论一个常见的面试题, 判断一个数是质数.
质数的特点:
质数也称为素数.
质数表示大于1的自然数中, 只能被1和自己整除的数.
OK, 了解了这个特点, 应该不难写出它的算法:
function isPrime(num) { for (var i = 2; i < num; i++) { if (num % i == 0) { return false } } return true } // 测试 alert(isPrime(3)) // true alert(isPrime(32)) // false alert(isPrime(37)) // true
但是, 这种做法的效率并不高. 为什么呢?
对于每个数n，其实并不需要从2判断到n-1
一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n).
比如16可以被分别. 那么是2*8, 2小于sqrt(16), 也就是4, 8大于4. 而4*4都是等于sqrt(n)
所以其实我们遍历到等于sqrt(n)即可
function isPrime(num) { // 1.获取平方根 var temp = parseInt(Math.sqrt(num)) // 2.循环判断 for (var i = 2; i <= temp; i++) { if (num % i == 0) { return false } } return true }扩容的质数
首先, 将初始的limit为8, 改成7
前面, 我们有对容量进行扩展, 方式是: 原来的容量 x 2
比如之前的容量是7, 那么扩容后就是14. 14还是一个质数吗?
显然不是, 所以我们还需要一个方法, 来实现一个新的容量为质数的算法.
那么我们可以封装获取新的容量的代码(质数)
// 判断是否是质数 HashTable.prototype.isPrime = function (num) { var temp = parseInt(Math.sqrt(num)) // 2.循环判断 for (var i = 2; i <= temp; i++) { if (num % i == 0) { return false } } return true } // 获取质数 HashTable.prototype.getPrime = function (num) { while (!isPrime(num)) { num++ } return num }
修改插入和删除的代码:
插入数据的代码:
// 扩容数组的数量 if (this.count > this.limit * 0.75) { var primeNum = this.getPrime(this.limit * 2) this.resize(primeNum) }
删除数据的代码:
// 缩小数组的容量 if (this.limit > 7 && this.count < this.limit * 0.25) { var primeNum = this.getPrime(Math.floor(this.limit / 2)) this.resize(primeNum) }
