目录

算法 - 查找 (Find)

1. 二分查找

二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想,每次通过跟区间的中间元素对比,讲待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。

局限性:

二分查找依赖顺序表结构,简单电说就是数组。

二分查找针对的数据是有序的。

数据量太小不适合二分查找

数据量太大也不适合二分查找,因为无法申请到连续的内存空间。

写一个正确的二分查找是比较困难的,坑比较多。

2. 利用跳表数据结构,来实现链表的快速查找。

对链表添加多级索引,通过索引来查找来提高链表的查找效率,这种数据结构叫做跳表 (Skip list)。

跳表查询的时间复杂度: O(logn)

跳表的空间复杂度: O(n)

Redis 中的有序集合中使用到了跳表数据结构。

3. 散列表

散列表来源于数组,借助散列函数对数组这种数据结构进行拓展,利用的是数组支持按照下标随机访问元素的特性。

散列表的两个核心问题是:散列函数设计散列冲突解决

再好的hash函数也无法避免散列冲突,当出现散列冲突的时候,该如何处理?

open addressing (开放寻址法)(冲突往下找空闲位置插入数据)

chaining (链表法)

当数据量比较小、装载因子小的时候,适合采用开放寻址法。当数据量比较大,存储的是大对象,适合采用链表法,而且链表法更加灵活,支持更多的优化策略,比如可以把链表转化为一个红黑树。

散列表碰撞攻击

恶意攻击者,通过设计特殊的数据结构,使得所有的数据经过散列函数后,散列到同一个槽中,导致散列表退化成链表。从而达到拒绝服务攻击(DoS)的目的。

如何设计散列表

散列函数的设计不能太复杂

散列函数生成的值要尽可能随机并且均匀发分布

工业级的散列表有哪些要求?

支持快速的查询、插入、删除操作。

内存占用合理,不能浪费过多的内存空间。

性能稳定,极端情况下,散列表的性能也不能退化到无法接受的情况。

为什么散列表和链表会经常放在一起使用?

因为散列表是动态数据结构,不停的有数据插入和删除,所以当我们希望进行顺序遍历散列表中的数据的时候,都需要先进行排序,那么效率是很低的。为了解决这个问题,我们将散列表和链表(或跳表)结合在一起使用。其次查找数据需要遍历链表,时间复杂度很高,O(n)。

LRU缓存淘汰算法(把数据放在散列表上,然后用双向链表串连起数据来。)

Redis的有序集合

LinkedHashMap也是通过双向链表和散列表连中数据结构来实现的,Linked 指的是双向链表。