JS数据结构 之 散列表

散列、散列函数、散列表

• 散列 是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据结构叫做散列表（哈希表-Hash Table）。

• 散列表 ，是根据键（Key）直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数（散列函数），将所需查询的数据映射到表（散列表）中一个位置来访问记录。在散列表上插入、删除和取用数据都非常快。👇
  

• 散列表的作用

  • 用于快速查找
  • 防止重复
  • 用作缓存

• 下面的散列表是基于数组进行设计的，数组的长度是预先设定的，如有需要，可以随时增加(一旦填装因子超过0.7，就该调整散列表的长度)。所有元素根据和该元素对应的键，保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是0到散列表的长度。

  散列函数会将每个键值映射为一个 唯一的 数组索引。然而，键的数量是无限的，数组的长度是有限的，一个更现实的目标是让散列函数尽量将键 均匀地 映射到数组中。

  填装因子：散列表包含的元素数 ➗ 位置总数

  

• 碰撞（collision）

  即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为碰撞（collision），当碰撞发生时，我们需要利用一定的方法去解决碰撞。(开链法 & 线性探测法)

• 对数组大小常见的限制是：数组长度应该是一个质数。

HashTable类

使用 HashTable 类来表示散列表，该类包含计算散列值的方法（散列函数）、向散列中插入数据的方法(put)、 从散列表中读取数据的方法(get)、显示散列表中数据分布等方法(showDistor)。

class HashTable{
    this.table = new Array([容量])
    this.simpleHash = simpleHash		//选择散列函数==>计算散列值的方法
    this.showDistor = showDistor		//显示数据分布
    this.put = put						//向散列表中插入数据
    this.get = get						//读取数据
    this.buildChains = buildChains		//冲突处理==collision
    this.values = []					//❗ 使用线性探测法时 需要创建一个新数组用来存放 data 对应 table 中的 key
}

散列函数

1处理整数：

散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余，这种散列方式称为除留余数法。

• 有一个集合U，里面分别是1000，10，152，9733，1555，997，1168
• 右侧是一个10个插槽的列表（散列表），我们需要把集合U中的整数存放到这个列表中
• 怎么存放，分别存在哪个槽里？这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数，我们对应这图来看
  • 1000%10=0，10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中
  • 152%10=2那么就存放到2的槽中
  • 9733%10=3 存放在编号为3的槽中

通过上面简单的例子，应该会对以下几点有大致的理解

• 集合U，就是可能会出现在散列表中的键
• 散列函数，就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中的方法，如例中的-取余数
• 散列表中存放的是通过计算后得到的键

接下来如何取值呢？

比如我们存储一个key为1000，value为’张三’ ==> {key:1000,value:‘张三’}
从我们上述的解释，它是不是应该存放在1000%10的这个插槽里。
当我们通过key想要找到value张三，是不是到key%10这个插槽里找就可以了呢？到了这里你可以停下来思考一下。

选择针对字符串类型的散列函数比较困难：

2针对字符串类型的散列函数

①simpleHash：简单的散列函数

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

//put() 和 showDistro()，一个用来将数据存入散列表， 一个用来显示散列表中的数据
function put(data){			//只接收数据值的put()方法
    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){
            document.write(i+':'+this.table[i])
        }
    }
}

使用简单的散列函数 simpleHash() 时数据并不是均匀分布的，而是向数组的两端集中，并且数据很大概率将会产生碰撞而不会全部显示出来。

②betterHash：更好的散列函数

霍纳算法是一种比较好的散列函数算法，计算时仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。

1为了避免碰撞，首先要确保散列表中用来存储数据的数组 其大小是个质数。这一点和计算散列值时使用的取余运算有关。【❗】

this.table = new Array('这里应该是一个质数')

2数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀。

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)
}

使用更好的散列函数: put()方法 和 get() 方法

function put(key, data){			//接收键和值作为参数
    var pos = this.betterHash(key)
    this.table[pos] = data
}

function get(key){					//获取储存在散列表中的数据
    return this.table[this.betterHash(key)]
}

散列的一些术语

据 例1：

• 散列表中所有可能出现的键称作全集U
• 用M表示槽的数量
• 给定一个键，由散列函数计算它应该出现在哪个槽中，上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。
• 1000和10都被存到了编号0的这个槽中，这种情况称之为碰撞（collision

看到这里不知道你是否大致理解了散列函数是什么。通过例子，再通过你的思考，你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了，那么我估计你应该是懂了。

碰撞处理（冲突处理（collision

当散列函数对于不同的输入产生同样的散列值时，就产生了碰撞。下面是两种碰撞解决办法：开链法和线性探测法

当存储数据使用的数组特别大时，选择线性探测法要比开链法好。如果数组的大小是待存储数据个数的 1.5 倍， 那就使用开链法

如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法

1开链法

当碰撞发生时，仍然将键存储到通过散列算法产生的索引位置上，但实际上，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了（即用 二维数组 实现）

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

使用了开链法后，要重新定义 put() 和 get() 方法:

//新的put()方法将键值散列 散列后的值对应数组的一个位置 若该位置上数组第一位已有数据 put()会搜索下一个位置 直到找到位置并储存
function put(key, data){
    var pos = this.betterHash(key)
    var index = 0
    if(this.table[pos][index]==undefined){		//此时 this.table[pos] 对应一个数组结构
        //该方法使用链中两个连续的单元格，第一个用来保存键值，第二个用来保存数据。
        this.table[pos][index] = key
        this.table[pos][index+1] = data
    }else{
        //循环
        while(this.table[pos][index]!=undefined){
            ++index
        }
        this.table[pos][index] = key
        this.table[pos][index+1] = data
    }
}


//新的 get() 方法先对键值散列 根据散列后的值找到散列表中相应的位置 然后搜索该位置上的链 直到找到键值 如果找到 就将紧跟在键值后面的数据返回 如果没找到 就返回 undefined
function get(key){
    var pos = this.betterHash(key)
    var index = 0
    if(this.table[pos][index]==key){
        return this.this.table[pos][index+1]
    }else{
        while(this.table[pos][index]!=key){
            index += 2
        }
        return this.table[pos][index+1]
    }
    return undefined			//散列表里没有此项
}

2线性探测法

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

使用线性探测法需要为 HashTable 类增加一个新的数组 → this.values = [] 用来存储数据。数组 table 和 values 并行工作，当将一个键值保存到数组 table 中时，将数据存入数组 values 中相应的 位置上。

使用了线性探测法后，要重新定义 put() 和 get() 方法:

//重写put() get()方法
function put(key, data){
    var pos = this.betterHash(key)
    if(this.table[pos]==undefined){
        this.table[pos] = key
        this.value[pos] = data
    }else{
        while(this.table[pos]!=undefined){
            pos++
        }
        this.table[pos] = key
        this.value[pos] = data
    }
}

function get(key){
    var hash = this.betterHash(key)
    for(var i=hash; this.table[hash]!=undefined; i++){
        if(this.table[hash] == key){
            return this.value[hash]
        }
    }
}

结尾补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。

来源 👉 JS中数据结构之散列表

​ 👉 js数据结构-散列表(哈希表)

​ 👉《算法图解》[美] Aditya Bhargava