数据结构学习笔记 - 散列表(Hash表)

冷不防 2022-12-27 02:26 101阅读 0赞

## 散列表(Hash表) ##

### 简介 ###

散列表依赖的是数组支持按下标随机访问数据的特性  
所以散列表是数组的一种扩展, 由数组演化而来, 如果没有数组就没有散列表  
时间复杂度O(1), 通过散列函数把元素的key映射为下标, 将数据存储在数组中对应下标的位置  
当按key查询元素时, 用同样的散列函数, 将key转化为下标, 从对应的数组下标位置取数据

### 设计散列表 ###

要可以应对各种异常情况的工业级

1.  散列函数的设计不能太复杂  
    散列函数设计的好坏直接决定散列表的性能  
    散列函数生成的值要尽可能随机且均匀分布  
    散列函数计算结果是非负整数, 因为数组下标从0开始  
    如果key1 = key2, 那么hash(key1)=hash(key2)
2.  选择解决冲突的办法  
    再好的散列函数也无法避免散列冲突, 所以常用的解决冲突方法有两类  
    (1)开放寻址法  
    核心思想就是, 如果出现了散列冲突, 就重新探测一个空闲位置, 那么如何探测  
    线性探测, 当前位置被占用, 就依次向后查找, 直到找到为止  
    二次探测, 类似线性探测, 不过步长每次移原来的二次方  
    双重散列, 使用一组散列函数, 一个位置被占用, 再使用第二个散列函数, 直到找到空闲位置  
    但问题是, 当散列表中空闲位置越少, 冲突概率就越大, 为保证效率, 一般会保证散列表中有一定比例的空闲位置, 用装载因子(填入元素个数/散列表长度)来表示  
    当数据量小, 装载因子小的时候适合  
    (2)链表法  
    更常用的解决冲突办法, 而且简单  
    数组每个下标里对应一条链表, 插入元素时, 通过散列函数, 确定链表, 将数据插入对应的链表中  
    时间复杂度和链表的长度成正比, O(k)  
    适合存储大对象, 大数据量的散列表, 支持更多的优化策略, 比如链表过长时用红黑树代替链表
3.  定义转载因子阈值, 设计动态扩容策略  
    避免低效扩容  
    当装载因子达到阈值, 申请新的空间, 每当有新数据插入, 将新数据插入到新散列表, 并从老散列表拿一个数据插入新散列表, 就可以逐渐全部转移且感受不到特别慢的扩容过程  
    当查询时, 先查新散列表, 没找到再查旧散列表

### Java中的HashMap ###

初始大小16  
装载因子0.75, 每次扩容至两倍  
冲突解决方法为链表法, 当链表长度超过8转换为红黑树  
散列函数

int hash(Object key) {  
        int h = key.hashCode()； 
        return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
    }

### 散列表碰撞攻击 ###

通过精心构造的数据使得所有数据经过hash函数以后都散列到一个槽里, 如果使用的基于链表的冲突解决方案, 散列表就会退化为链表,  
数据里极大时会导致查询消耗大量cpu和线程资源, 造成系统无法响应其他请求

### 散列表和链表常用组合场景 ###

*  LRU缓存淘汰算法  
    使用双向链表存储数据, 链表中每个结点包含数据(data), 前驱指针(prev), 后继指针(next), 和hnext  
    使用链表法解决的散列表, 包含两条链, 一条双向链表, 一条散列表的拉链  
    可实现O(1)时间复杂度内完成插入删除查找操作
 *  java LinkeHashMap  
    支持按照插入顺序遍历数据, 和按照访问顺序遍历数据  
    链表结合散列表, 原理和LRU一样, Linked指的是双向链表

两者结合, 散列表提供快速的插入删除查找, 链表提供有序

### 小结 ###

工业级散列表应该具有哪些特性  
支持快速查询, 插入, 删除操作  
内存占用合理, 不浪费过多的内存空间  
性能稳定, 极端情况下散列表的性能也不会退化到无法接受的情况

### 课后思考 ###

10w条url访问日志, 按照访问次数排序 (todo)  
两个10w条字符串的数组, 快速找出两个数组中相同的字符串 (todo)