散列表(哈希表)

[hubvue]

散列表

散列表又称为哈希表，专注于存储数据的结构，散列表类似于key-value的结构存储数据，插入、删除和取用速度非常的快(时间复杂度O(1))，但是如果在散列表中查询最大值和最小值，效率就很低了。

JavaScript散列表基于数组设计，理想情况散列函数会将每一个键值映射为唯一索引，数组长度有限制，更现实的策略是将键均匀分布。

数据长度是预先设定的，可以随时增加，所有元素根据和该元素对应的键，保存数组特定位置。

即时使用高效的散列函数，仍然存在连个键值相同的情况，这种现象称为碰撞。

解决碰撞的方法

1.让散列表的长度为质数

由于散列函数一般是对一个数取余，如果不是质数可能会多次得到相同的key值，碰撞次数增大，如果是质数，极大的减少得到相同的key值减少碰撞次数。

2.开链法

当存储数据出现相同的key值的时候，在key的位置开辟一个链表结构用于存储数据，这种方式就叫做开链法。

3.线性探测法

线性探测法是一种开放寻址散列，当存储数据散列的时候反向得到的key值已经有了数据，那么存储数据的key值就+1，直到找到key值没有数据存储再把当前数据存进去。这种方式必须要保证散列表的长度必须要大于数据的数量。

代码实现

第一种方式就是使用数组长度为质数的方式，使用除留余数法找出数据对应的key值。

class HashTable {
        constructor(){
            this.table = new Array(137);
        }
        //质数法
        simpleHash(data) {
            //除留余数法
            let total = 0;
            for(let str of data) {
                total += str.charCodeAt(str);
            }
            return total % this.table.length;
        }
        put(data){
            let pos = this.simpleHash(data);
             this.table[pos][index] = data;
        }
        get(key){
            return this.table[key];
        }
        showDistro(){
            for(let i = 0; i < this.table.length; i ++) {
                if(this.table[i] !== undefined){
                    console.log('key->' + i + "  value->" + this.table[i]);
                }
            }
        }
    }

这种方式质数的方式还是不怎么好，key分配的不均匀，可以使用换那算法让key值分配的均匀一些

betterHash(data) {
            //换那算法
            // 在每次得到total的时候乘上一个质数，这样就会使拿到的键稍微均匀一些。
            const H = 31;
            let total = 0;
            for(let str of data) {
                total +=H * total + str.charCodeAt(str);
            }
            if(total < 0){
                total += this.table.length;
            }
            return total % this.table.length;
        }

更为使用的方式是开链法，如果有key发生碰撞，则开辟一个链表，把key值相同的数据存放在链表里面。

首先开辟链表

buildChians(){
    for(let i = 0, len = this.table.length; i < len; i ++) {
        this.table[i] = new Array();
    }
}

修改一下put方法

let pos = this.simpleHash(data);
let index = 0;  //链表的索引
if(this.table[pos][index] === undefined) {  //判断当前位置是否有值，没有就插入，有就找到没有为止
    this.table[pos][index] = data;  
} else {
    while(this.table[pos][index] !== undefined){
        ++index;
    }
    this.table[pos][index] = data;
}

线性探测法主要适用于散列表的长度大于数据的数量。当数据的key存在数据的时候就让key++，直到找到key没有数据，把当前数据存放进去。

 let pos = this.simpleHash(data);
//线性探测法
if(this.table[pos] === undefined) {
    this.table[pos] = data;
} else {
    while(this.table[pos] !== undefined){
        pos++;
    }
    this.table[pos] = data;
}