算法 - 查找 (Find)

1. 二分查找

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

局限性：

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

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

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

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

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

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

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

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

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

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

3. 散列表

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

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

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

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

chaining (链表法)

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

散列表碰撞攻击

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

如何设计散列表

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

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

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

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

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

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

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

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

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

Redis的有序集合

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