Skip to content

Latest commit

 

History

History
155 lines (148 loc) · 5.76 KB

散列.md

File metadata and controls

155 lines (148 loc) · 5.76 KB

散列(哈希)的介绍

散列是一种常用的数据存储基数，散列后的数据可以快速的插入和取用。散列使用的数据结构叫做散列表。但是～查找操作～效率会比较低。 哈希表是基于键值对的一种数据存储结构，key值不可以重复，value可以重复，后面添加的重复的key值的时候，会把之前key值对应的value给覆盖掉。 key 值重复,这种现象成为碰撞。首先哈希表需要初始化一个一定长度的数组，数组的长度应该是一个质数，然后当快要存储满的时候可以“动态扩容”，存储的时候让散列函数尽量将键均匀的映射到数组中。

    function HashTable(){
        this.table = new Array(137)
        this.simpleHash  = simpleHash
        this.put = put
        this.showDistro = showDistro
    }
定义一个散列函数。

散列函数的选择依赖于键值的数据类型。如果建是整型，最简单的散列函数就是以数组的长度对建取余。但是在一些情况下，比如数组的长度是10 ，而键值都是10的倍数，就不推荐这种方式了。 在很多应用中，键是字符串类型，选择针对字符串类型的散列函数是很难。

将字符串的ASCII码相加，是一个不错的散列函数，这样的散列值就是ASCII码值的和除以数组长度的余数

    function simpleHash(data){
        var total = 0;
        for(var i = 0; i<data.length; i++){
            total+=data.charCodeAt(i)
        }
        return total% this.table.length
    }

为HashTable增加两个方法，put 和showDistro ，一个用来将数据存入散列表，一个用来显示散列表的数据。

    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){
                console.log(i+':'+this.table[i])
            }
        }
    }

使用一个例子测试散列函数

    var hTable = new HashTable()
    var someNames = ["David", "Jennifer", "Donnie", "Raymond","Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
    for(var  i =0; i< someNames.length;i++){
        hTable.put(someNames[i])
    }
    hTable.showDistro()
    ### 结果
    35:Cynthia
    45:Clayton
    57:Donnie
    77:David
    95:Danny
    116:Mike
    132:Jennifer
    134:Jonathan

可以看到数据并不是均匀分布的，人名想数据的两端集中，还有另外一个严重的问题， 就是数据没有展示完全，在simpleHash中添加一个语句，分析原因

    function  simpleHash(data){
        var total = 0;
        for(var i = 0; i<data.length; i++){
            total+=data.charCodeAt(i)
        }
        console.log('hash value--',data,'->',total)
        return total% this.table.length
    }
    #### 结果
    hash value-- David -> 488
    hash value-- Jennifer -> 817
    hash value-- Donnie -> 605
    hash value-- Raymond -> 730
    hash value-- Cynthia -> 720
    hash value-- Mike -> 390
    hash value-- Clayton -> 730
    hash value-- Danny -> 506
    hash value-- Jonathan -> 819
    35:Cynthia
    45:Clayton
    57:Donnie
    77:David
    95:Danny
    116:Mike
    132:Jennifer
    134:Jonathan

可以看到字符串Clayton 和Raymond的散列值是一样的，Clayton 将 Raymond覆盖了， 发生了碰撞，只将Clayton存入了散列表中。为了处理碰撞，首先要确保散列表中用来存数据的数组其大小是一个质数，这点很关键，这和计算散列值时使用的取余运算有关 这里定义了一个常量 H = 37; 这个质数37是一个比较好的数字适合我们的哈希算法来参与哈希键值运算，并且使生成的键值在哈希表中均匀分布。

    function betterHash(string){
        const H = 37;
        var total = 0;
        for(var i= 0; i<string.length;i++){
            total+=H*total+string.charCodeAt(i)
        }
        total = total%this.stable.length
        if(total<0){
            total += this.table.length-1;
        }
        return parseInt(total)
    }

对散列表排序、从中取值

    function get(key){
        return this.table(this.betterHash(key))
    }

碰撞处理

当散列函数对于多个输入产生同样的输出时，就产生了碰撞， 有两种方法处理:开链法和线性探测法

开链法

开链法 是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，这样就能存储多个键了。使用这种技术，即使两个散列后的值相同， 依然被保存在同样的位置，只不过他们在第二个数组中的位置不一样罢了。 如图所示 开链法

实现方法：在创建存储散列过的数值的数组时，通过调用一个函数创建一个新的空数组，然后将该书组的赋给散列表里的每个数组元素。定义buildChains方法创建二维数组

    function buildChins(){
        for(var i = 0; i<this.table.length;i++){
            this.table[i] =  new Array()
        }
    }

需要修改下showDistro()方法

    function showDistro(){
        for(var i = 0;i<this.table.length;i++){
            if(this.table[i][0]!=undefined){
                console.log(i+":"+this.table[i])
            }
        }
    }

测试使用开链法

    var hTable = new HashTable()
    hTable.buildChains();
     var someNames = ["David", "Jennifer", "Donnie", "Raymond",
                      "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
     for (var i = 0; i < someNames.length; ++i) {
        hTable.put(someNames[i]);
     }
     hTable.showDistro();

对应的put()和get()方法需要重新定义。

    function put(key,){

    }