数据结构之散列表

概念
散列表也叫作哈希表(hash table),这种数据结构提供了键(Key)和值(Value)的映射关系,只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1)。

存储原理
散列表在本质上是一个数组,散列表的key则是以字符串为主的,通过hash函数把key和数组下标进行转换,作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。

传统Hash与一致性Hash法
如hash函数:CRC16、CRC32、siphash、murmurHash、times33等
此种Hash计算方式为固定Hash方式,也称为传统Hash,该方式在数组固定时,可以快速检索,但当数组长度变化是,需要重新计算数组下标,此时根据key检索将出现问题,所以说传统Hash法虽然比较简单,但不利于扩展,因为扩容涉及到全部数据迁移,如果要扩展可以采用一致性Hash法

操作
写操作(put)
写操作就是在散列中插入新的键值对(在JDK中叫作Entry或Node)
第一步,通过哈希函数,把key转化成数组下标
第二步:如果数组下标对应的位置没有元素,就把这个Entry填充到数组下标的位置。

Hash冲突(碰撞)
由于数组的长度是有限的,当插入的Entry越来越多时,不同的key通过哈希函数获得的下标有可能是相同的,这种情况,就叫作哈希冲突。

解决哈希冲入的方法主要有两种:
开放寻址法
开放寻址法的原理是当一个key通过hash函数获得对应的数组下标已被占用时,就寻找下一个空档位置。
在Java中,
ThreadLocal所使用的就是开放寻址法

链表法
数组的每一个元素不仅是一个Entry对象,还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点,
当新来的Entry映射到与之冲突的数组位置时,只需要插入到对应的链表中即可,默认next指向null。
在Entry中保存key和值,以及next指针
Entry{
int key;
object value;
Entry next;
}
当根据key查找值的时候,在index=2的位置是一个单链表
遍历该单链表,再根据key即可取值

读操作(get)
读操作就是通过给定的key,在散列表中查找对应的Value
第一步,通过哈希函数,把key转化成数组下标
第二步,找到数组下标所对应的元素,如果key不正确,说明产生了hash冲突,则顺着头节点遍历该单链表,再根据key即可取值

Hash扩容(resize)
散列表是基于数组实现的,所以散列表需要扩容
当经过多次元素插入,散列表达到一定饱和度时,key映射位置发生冲突的概率会逐渐提高。这样一来,大量元素拥挤再相同的数组下标位置,形成很长的链表,对后续插入操作和查询操作的性能都有很大影响。
影响扩容的因素有两个:
Capacity:HashMap的当前长度
LoadFactor:HashMap的负载因子(阈值),默认是0.75f
当HashMap.Size >= Capacity*LoadFactor时,需要进行扩容

扩容的步骤:
1、扩容,创建一个新的Entry空数组,长度是原来数组的2倍
2、重新Hash,遍历原Entry数组,把所有的Entry重新Hash到新数组中

关于HashMap的实现,JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时,为了提升插入和查找的效率,HashMap会把Entry的链表转化为红黑树这种数据结构。

JDK1.8前再HashMap扩容时,会反序单链表,这样在高并发时会有死循环的可能。


版权声明:本文为weixin_43526092原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。