首页 > 编程语言 > 详细

数据结构与算法之散列

时间:2019-06-15 13:04:55      阅读:133      评论:0      收藏:0      [点我收藏+]

散列

基于数组进行设计的数据结构

优点:可以快速插入,删除和取用数据

缺点:查找操作效率低下

在使用散列表存储数据时,通过一个散列函数将键映射为一个数字,这个数字的范围是0到散列表的长度。理想情况下从key到index应该是一一对应的,然而键的数量可以是无限的,而数组长度是有限的,因此一个更现实的目标是让散列函数尽量均匀地映射到数组中(即让两个或多个key对于1个index,这种现象称为碰撞)。

对数组大小常见的限制是: 数组长度应该是一个质数。也会有多种确定数组大小的策略, 所有的策
略都基于处理碰撞的技术。

散列函数

除留余数法:以数组的长度(质数)对键取余,取余数作为数组中的索引值。

比如对于字符串形式的数据可以计算每个字符ASCII码值的和:

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

但如果某两个字符串的ASCII码值的和相等的时候就会发生前面提到的碰撞问题,此时只会有一个数据被保存。为了改善这个问题,我们需要一个更好的散列函数。

  1. 为了避免碰撞, 首先要确保散列表中用来存储数据的数组其大小是个质数
  2. 数组的长度应该在 100 以上(137), 这是为了让数据在散列表中分布得更加均匀
  3. 采用霍纳算法,在每次求和时乘以一个质数(31)。
betterHash(string){
    const H = 31;  //这个质数的选择决定了是否会发生碰撞,发生时应及时调整
    var total = 0;
    for(var i = 0;i<string.length;i++){
        total += H * total + string.charCodeAt(i);
    }
    total = total % this.table.length;
    // if(total < 0){
    //     total += this.table.length - 1;
    // }
    return total;
},

总结上述:

function HashTable(){
    this.table = new Array(137);
}

HashTable.prototype = {
    constructor: HashTable,

    //简单,容易产生碰撞
    simpleHash(data){
        var total = 0;
        for(var i = 0;i<data.length;i++){
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    },

    //采用霍纳算法,避免碰撞
    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.table.length;
        // if(total < 0){
        //     total += this.table.length - 1;
        // }
        return total;
    },
    showDistro(){
        var n = 0;
        for(var i = 0;i<this.table.length;i++){
            if(this.table[i] !== undefined){
                console.log(i + ': ' + this.table[i]);
            }
        }
    },
    put(key, data){
        var pos = this.betterHash(key);
        this.table[pos] = data;
    },
    get(key){
        return this.table[this.betterHash(key)];
    }
}
碰撞处理

这里介绍开链法和线性探测法两种。这两种方法如何取舍?如果数组的大小是待存储数据个数的 1.5 倍,使用开链法;如果数组的大小是待存储数据的两倍及两倍以上时,那么使用线性探测法。也就是说存储数据使用的数组长度越大,越适合使用线性探测法。

开链法:指实现散列表的底层数组中, 每个数组元素又是一个新的数据结构, 比如另一个数组, 这样就能存储多个键了。

实现方法:在创建存储散列过的键值的数组时, 通过调用一个函数创建一个新的空数组, 然后将该数组赋给散列表里的每个数组元素。 这样就创建了一个二维数组。(注意get和put方法重写)

function HashTable(){
    this.table = new Array(137);
    this.buildChains();
}

HashTable.prototype = {
    constructor: HashTable,

    //采用霍纳算法,避免碰撞
    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.table.length;
        return total;
    },

    buildChains(){
        for(var i = 0;i<this.table.length;i++){
            this.table[i] = new Array();
        }
    },
    showDistro(){
        var n = 0;
        for(var i = 0;i<this.table.length;i++){
            if(this.table[i][0] !== undefined){
                console.log(i + ': ' + this.table[i]);
            }
        }
    },
    put(key, data){
        var pos = this.betterHash(key);
        var index = 0;
        while(this.table[pos][index] !== undefined){
            index++;
        }
        this.table[pos][index] = data;
    },
    get(key){
        var index = 0;
        var pos = this.betterHash(key);
        while(this.table[pos][index] !== key){
            var current = this.table[pos][index];
            if(current === undefined){
                return undefined;
            }else{
                index++;
            }
        }   
        return this.table[pos][index];
    },
}

线性探测法:隶属于一种更一般化的散列技术——开放寻址散列。当发生碰撞时,线性探测法检查散列表中的下一个位置是否为空。如果为空,就将数据存入该位置;如果不为空,则继续检查下一个位置,直到找到一个空的位置为止。

直接上代码(注意一下get方法的实现)。

function HashTable(){
    this.table = new Array(137);
    //与table并行存储,values存储值,table存储键
    this.values = [];
}

HashTable.prototype = {
    constructor: HashTable,

    //采用霍纳算法,避免碰撞
    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.table.length;
        return total;
    },

    showDistro(){
        var n = 0;
        for(var i = 0;i<this.values.length;i++){
            if(this.values[i] !== undefined){
                console.log(i + ': ' + this.values[i]);
            }
        }
    },
    put(key, data){
        var pos = this.betterHash(key);
        if(this.table[pos] === undefined){
            this.table[pos] = key;
            this.values[pos] = data;
        }else{
            while(this.table[pos] !== undefined){
                pos++;
            }
            this.table[pos] = key;
            this.values[pos] = data;
        }
    },
    get(key){
        var pos = this.betterHash(key);
        for(var i = pos;this.table[i] !== undefined;i++){
            if(this.table[pos] === key){
                return this.values[pos];
            }
        }
        return undefined;
    },
}

数据结构与算法之散列

原文:https://www.cnblogs.com/simpul/p/11027179.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!