Hello小伙伴们大家好~~今天带来的是散列,这个其实是一个很重要然而很多人不是很理解的技术。散列是什么呢,是一种数据存储技术,能够达到经过散列后的数据可以快速地插入或取用,这种结构就是散列表。
HashTable的实现
在此处我们还是基于数组来实现,使用散列表存储数据时,通过一个散列函数将键映射为一个数字,每个键值映射为一个唯一的数组索引。还是原来的老步骤,一个散列表会需要什么呢?计算散列值、向散列中插入数据、从散列中读取数据,并显示散列表中数据分布的方法。
function HashTable() {
this.table = new Array(137);
this.simpleHash = simpleHash;
this.showDistro = showDistro;
this.put = put;
this.get = get;
}
// 散列函数的选择依赖于键值的数据类型。如果键是整型,最简单的散列函数就是以数组的长度对键取余
// 如果键是随机的整数,则散列函数应该更均匀地分布这些键。这种散列方式称为除留余数法
function simpleHash(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
return total % this.table.length;
}
function get(key) {
return this.table[this.betterHash(key)];
}
// 用来将数据存入散列表
function put(data) {
var pos = this.simpleHash(data);
this.table[pos] = data;
}
// 用来显示散列表中的数据
function showDistro() {
var n = 0;
for (var i = 0; i < this.table.length; ++i) {
if (this.table[i] != undefined) {
print(i + ": " + this.table[i]);
}
}
}
Tips:将两个键映射成为同一个值的可能性还是存在的,这叫做碰撞,当碰撞产生时,还是要解决的。那么我们要怎么解决呢?这里我们采用一个较小的质数来计算散列。
function betterHash(string, arr) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % arr.length;
return parseInt(total);
}
HashTable碰撞的处理
1)开链法:开链法是指实现散列表的底层数组中,每个数组 元素又是一个新的数据结构,比如另一个数组,这样就能存储多个键了。使用这种技术,即使两个键散列后的值相同,依然被保存在同样的位置,只不过它们在第二个数组中的位置不一样罢了。
2)线性探测法:线性探测法隶属于一种更一般化的散列技术:开放 寻址散列。当发生碰撞时,线性探测法检查散列表中的下一个位置是否为空。如果为空,就将数据存入该位置;如果不为空,则继续检查下一个位置,直到找到一个空的位置为止
今天的分享就到这里啦,喜欢兔妞的文章就请在看+关注吧,多多转发也是极好的,能够在后台告诉兔妞哪里需要改进就更好啦~~