目录
散列表是什么？
散列表英文名叫Hash Table，散列表用的是数组支持下标随机访问的数据特性，所以散列表其实就是数组的一种扩展，有数组演化而来。
散列表概念
散列表中的键(key)/关键字：就是用来标示一个指定的元素
对key进行hash的函数就是散列函数,就是hash(key)。函数的计算结果就是散列值,就是hash(key)的值.
散列表规律
-
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1),我们通过散列函数把元素的键值映射为数组下标.
-
数据存储:我们查找散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置.
-
数据查找:同样我们利用散列函数,将键值转化为数组下标,从对应的数组下标的位置获取数据.
散列函数基本要求
-
散列函数计算得到的散列值是一个非负整数.
-
如果key1=key2,那么hash(key1)==hash(key2).
-
如果key1!=key2,那么hash(key1)!=hash(key2).
上面列举的三点1,2点容易理解和实现,但是第3点有点问题,因为真实情况下,要找到一个不同的key对应的散列值不一样的散列函数,几乎是不可能的,像是著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突,而且数组的存储空间有限,也就加大散列冲突的概率.
散列冲突解决办法
开放寻址法
开放寻址法就是如果发生了散列冲突,就重新探测一个新的空闲位置,将数据插入其中,探测方法又有线性探测、二次探测、双重散列等方法
线性探测:
当我们进行散列表插入操作时，如果我们的某个数据经过散列后,存储的位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到位置,如下图,蓝色的是已经占用的位置，当hash(key)的是数组下标5的时候，由于位置已经被其他数据占了，所以从当前位置开始继续往后查找，遍历到尾部都没有找到空闲的位置，就继续从头查找，在位置2出找到空闲位置，将key放到数组中:
对于散列表的查找操作,类似与插入过程,通过散列值获取到数组中下标为散列值的元素,然后和我们要查找的元素对比,如果相等,则说明就是们要找的元素,如果不相等,就按顺序依次往后寻找,如果遍历到数组空闲的位置,则说明要查找的元素不再散列表中,如图:
对于删除操作就会有点问题了,我们不能直接删除散列值对应的数据,因为如下图中所示:
-
果我们第一次插入数据x,x的哈希值是数组下标是4的位置,但是数组下表4的位置已经被占用了，所以我们继续查找空闲位置，找到了下表是6的位置，然后我们插入数据x。
-
接着我们删除数组下标是5的数据。
-
然后我们再次查询数据x的时候，我们还是hash到下表是4的位置没然后开始查找，但是我们依次往后查找时发现下表是5的位置空闲，因为之前我们说过如果散列表中，按照线性探测依次查找如果找到了空闲位置还没有找到数据，就说明数据不存在散列表中，所以这个时候就返回数据x不在散列表中，这就产生了问题。
-
我们可以通过将删除的数据,特殊标记为deteled,当线性探测查找的时候,遇到标记deleted的空间,并不是停下来,而是继续探测：
当随着数据越来越多,散列冲突发生概率越来越大,空闲位置越来越少,线性探测的时间就会越来越久,极端情况下,可能需要探测整张表,所以最坏情况下时间复杂度是O(n),插入、删除操作也可能探测整张表.
开放寻址法除了线性探测外还有两个比较经典的探测方法,二次探测、双重探测。
二次探测
二次探测就是和线性探测类似,线性探测的每次步长是1,二次探测的步长是hash(key)+0、hash(key)+1^2、hash(key)+2^2。
双重散列
双重探测就是使用的是一组散列函数hash1(key)、hash2(key)、hash3(key)....我们现使用第一个散列函数,如果位置占用了,在使用第二个散列函数,依次类推.
不管使用那个探测方法,随着空闲位置越来越少,散列冲突的概率都会大大提高,所以为了保证散列表的操作效率,尽可能保证散列表中有一定比例的空闲位置,我们采用装载因子来表示空位的多少,装载因子的计算公式是:装载因子 = 填入的数据个数 / 散列表的长度,装载因子越大,说明空闲位置越少,散列冲突越大.
链表法
链表法是一种更加常用的散列冲突解决办法,在散列表中,每个“槽(slot)”位会对应一个链表,所有散列值相同的元素我们放到相同的槽位对应的链表中,如图:
通过链表法进行插入操作时,我们只需要计算出对应的散列槽位,然后将数据插入到对应的链表中就行了,所以插入的时间复杂度是O(1),删除和查找的操作是通过计算散列槽位,然后遍历槽位对应的链表进行操作,假设散列表的数据分布比较均匀,所以时间复杂度就是O(k),其中k=n/m,n表示散列表中的数据的个数,m表示散列表中槽的个数。
如何构造散列函数?
-
如果初始化的时候,大概知道了数据量的大小,可以初始化的时候创建合适大小的散列表,减少动态扩容的次数.
-
散列函数的设计不能太复杂,并且函数生成的值尽可能随机平均分配到各个槽点.
-
设置合适的装载因子,当装载因子超过预设值的时候,支持动态扩容,新的散列表的大小是原来的两倍空间.
动态扩容如果是一次性扩容那么是比较耗时的操作,因为需要将原来数组上的数据都搬迁到新的数组上,假如需要扩容的原散列表很大,那么这个扩容就会变得非常慢。
我们可以通过扩容后,并不直接将老数据全部搬迁到新数组中,而是每次执行插入操作的时候,将新数据插入到新数组中的时候,同时从老的散列表拿出一个数据放到新的散列表中,每次插入都执行这个操作,经过多次插入操作后,老的散列表的数据就全部搬迁到了新的散列表中,就避免了一次搬迁数据耗时的问题。
这期间的查询操作,可以先查询老散列表上的数据,老散列表没有在来新散列表上查找,因为散列表的查找时间复杂度是O(1),所以不会对查找效率造成太大的影响。
4. 选择合适的散列冲突解决方法。、
java中LinkedHashMap采用的是链表法解决散列冲突,而且LinkedHashMap当对链表还进行了改造,当链表长度达到一定值的时候就变成了红黑树数据结构,关于红黑树,我们后面再讲.ThreadLocalMap采用的是线性探测的开放寻址法来解决冲突,我们来对比一下这两个的优缺点。
开放寻址法优缺点
优点是可以有效的利用CPU的缓存加快查询速度,这里我解释一下:CPU在从内存读取数据的时候,会先把读取到的数据加载到CPU的缓存中.而CPU每次从内存读取数据并不是只读取那个特定要访问的地址,而是读取一个数据块,所以对于数组来说能充分利用CPU缓存加速。
缺点是容易产生数据堆积,不适于大规模的数据存储,插入时可能会出现很多次冲突的现象。
链表法优缺点
优点是链表法对内存的利用率比开放寻址法要高,处理冲突简单，且无堆积现象，平均查找长度短；链表中的结点是动态申请的，适合构造表不能确定长度的情况；相对而言，拉链法的指针域可以忽略不计，因此较开放地址法更加节省空间。
缺点是如果存储的对象较小,是比较消耗内存的,因为此时我们需要考虑上指针占用的内存了,而且因为链表中的节点在内存中是不连续的,所以对CPU缓存不友好.
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,比起开放寻址法,他更加灵活,支持更多的优化策略,就比如红黑树代替.
总结
好了，今天我们主要分享了数据结构中的散列表，希望读者通过本篇文章能对散列表这种数据结构有更加深入的认知，谢谢阅读，我们下期继续分享数据结构：树和堆！