散列表

散列表(HashTable)

散列表本质:
散列表 将数组下标扩展为 被称为 键(key) 的其他形式使其能储存更多信息,
且通过 散列函数映射 使得 键 不丢失原本的数据位置信息.

散列表优势:
散列表 利用了 数组支持 按照下标访问数据的特性,以空间换时间,提升存取效率.

散列表原理:
用数组储存数据,通过 数组下标 标记 数据位置
要获取数据位置,需传入 键(key) (或称 关键字)
散列函数 将key转换为数组下标,从而将key映射到真正的数组中数据位置,
散列函数 计算得到的值(数组下标)就叫做 散列值 或称 Hash值

散列函数本质是:
一个位置计算算法,已知key,通过 散列函数计算 生成数据位置(数组下标),
外部不需要关注数据位置.

散列函数

散列函数 在 散列表 中起着非常关键得作用, 数组下标 = hash(key)

散列函数 设计基本要求:

1. 计算返回值是一个非负整数
2. 需要是一个纯函数(不同输入,必然不同输出;相同输入,必然相同输出;不产生额外影响)

如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2),不同输入 完全 不同输出
实际上是 输入值,最后给这个值计算出的位置已经给之前的值给过了
实际 几乎无法做到,且散列预设数组越小,越容易产生撞车,称为散列冲突.

散列冲突

解决散列冲突 有两种方法

开放寻址法

开放寻址法 的核心思想是 如果出现了 散列冲突,就重新探测一个位置插入.

线性探测:
当往 散列表 中插入数据时,如果储存位置已被占用,
则依次向后寻找 知道找到空余位置为止

线性探测的删除操作:
线性探测的删除操作 不能直接把元素置为空,
因为 一旦把某个位置置为空 则在查找时,通过线性探测原则,
一找到空闲位置就会认定散列表不存在此元素.
解决办法是 将删除的元素 标记为delete,当线性探测查找时,遇到delete继续探测.

线性探测的缺点:
当列表中插入的数据越来越多,散列表冲突发生的可能性越来越大,探测时间越来越久
极端情况下 甚至需要线性探测整个标,则存取时间复杂度变为 O(n)

二次探测(Quadratic probing):
二次探测 就是线性探测 步长的二次方,不是一步步向后找空位,而是1²步,2²步

双重散列(Double hashing)
双重散列 就是使用 一组散列函数 先使用第一个散列函数 重复则 再使用第二个散列函数

当表中空闲位置不多时,散列冲突概率大大提高.
需要尽可能保证散列中有一定比例的空闲空间,因此使用装载来表示空位多少.
装载因子(Load Factor) = 填入表中的元素个数/散列表的长度

链表法

每个数组位置对应一个链表,所有 散列值 相同的元素 都放在相同槽位对应的列表中

当数据量小,装载因子小时,适合使用开放寻址法.(Java中的ThreadLocalMap)
当数据量大,数据为大对象时,适合使用链表法,甚至使用红黑树代替链表

/*
最基本的散列表
*/

class HashTable {
    constructor() {
        this.table=[];
    }
    //散列函数
    loseHashCode(key){
        var hash=0;
        //从ASCII表中查到的ASCII值加到hash中
        for (var i=0;i<key.length;i++){
            hash+=key.charCodeAt(i);
        }
        //为了得到比较小的数值，我们会用hash和任意数除余
        return hash%37;
    }
    //向散列表增加一个新的项
    put(key,value){
        var position=this.loseHashCode(key);
        console.log(position+'-'+key);
        this.table[position]=value;
    }
    //根据键从散列表删除值
    remove(key){
        this.table[this.loseHashCode(key)]=undefined;
    }
    //返回根据键值检索到的特定的值
    get(key){
        console.log(this.table[this.loseHashCode(key)])
    }
    print(){
        for (var i=0;i<this.table.length;++i){
            if (this.table[i]!==undefined){
                console.log(i+':'+this.table[i]);
            }
        }
    }
}
var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.remove('Gandalf')
hash.get('Gandalf')
hash.get('Tyrion')
hash.print()

一个工业化散列表

散列函数不能太复杂 (过多计算浪费性能)
散列函数生成的值要尽可能随机且均匀分布
装载因子过大时 动态扩容
使用 开放寻址法 或 链表法 解决散列冲突

散列表将LRU缓存淘汰算法时间复杂度降为O(1)

LRU缓存淘汰算法 需要维护一个 按访问瞬间从大到小的 有序链表结构
当缓存空间不够时 就从链表头删除结点
当要添加某个数据时，先在链表中查找该数据，没找到就插入到尾部，找到了移到尾部

查找链表的时间复杂度很高为O(n)
添加/删除/查找 都需要查找链表

现在在 缓存数据的双向链表 的基础上 加上 链表法解决冲突的散列表

把缓存数据的位置计算交给 散列表,散列表标记数据位置

查找时利用散列表,直接定位数据,时间复杂度为O(1)

删除时利用散列表,直接定位数据,删除结点(注意原本双向链表删除节点的链计算)

添加时 和以前没有不同.

散列表 和 链表结合使用

散列表支持 非常高效的 数据插入 删除 查找操作,
但数据都是无规律储存的,无法支持按某种顺序快速遍历数据
如果想 顺序遍历,需要把数据 拷贝到数组中 然后排序,然后遍历
为了解决这个问题,将 散列表与链表结合使用,在增删时 同时保持 顺序
(如:按插入顺序排序)

其他

数组占据随机访问的优势，却有需要连续内存的缺点。

链表具有可不连续存储的优势，但访问查找是线性的。

散列表和链表、跳表的混合使用，是为了结合数组和链表的优势，规避它们的不足。

我们可以得出数据结构和算法的重要性排行榜：连续空间 > 时间 > 碎片空间