数据结构与算法–散列表

大家好，欢迎来到IT知识分享网。

前言

散列表也叫哈希表，是根据键值对（key，value）进行访问的一种数据结构。他是把一对（key，value）通过key的哈希值来映射到数组中的，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

一、什么是散列表

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

二、HashMap

三、散列表原理

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

四、散列函数的设计

如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

五、解决散列冲突的方法

1、开放寻址法

开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。
举个例子
哈希表中已经插入8、9元素，此时再插入14，下标2已经被8给占用了，出现哈希冲突。
线性探测会环形寻找next节点，先找到下标3，被9占用了，依然冲突，再找到下标4，没有被占用，即没有发生冲突，则将14放入下标4的节点中。

装在因子: 散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

2、链表法

优点

1. 内存利用率比开放寻址法要高，链表结点可以在需要的时候再创建
2. 对大装载因子容忍度更高，只要散列函数的值随机均匀，即使装载因子变成 10，也就是链表的长度变长了而已

缺点

1. 存储小对象需要额外的指针，比较耗内存，但对于大对象则可以忽略
2. 链表分散存储，无法利用 CPU 缓存

总结