算法 - 查找 (Find)
1. 二分查找
二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想,每次通过跟区间的中间元素对比,讲待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
局限性:
二分查找依赖顺序表结构,简单电说就是数组。
二分查找针对的数据是有序的。
数据量太小不适合二分查找
数据量太大也不适合二分查找,因为无法申请到连续的内存空间。
写一个正确的二分查找是比较困难的,坑比较多。
2. 利用跳表数据结构,来实现链表的快速查找。
对链表添加多级索引,通过索引来查找来提高链表的查找效率,这种数据结构叫做跳表 (Skip list)。
跳表查询的时间复杂度: O(logn)
跳表的空间复杂度: O(n)
Redis 中的有序集合中使用到了跳表数据结构。
3. 散列表
散列表来源于数组,借助散列函数对数组这种数据结构进行拓展,利用的是数组支持按照下标随机访问元素的特性。
散列表的两个核心问题是:散列函数设计 和 散列冲突解决。
再好的hash函数也无法避免散列冲突,当出现散列冲突的时候,该如何处理?
open addressing (开放寻址法)(冲突往下找空闲位置插入数据)
chaining (链表法)
当数据量比较小、装载因子小的时候,适合采用开放寻址法。当数据量比较大,存储的是大对象,适合采用链表法,而且链表法更加灵活,支持更多的优化策略,比如可以把链表转化为一个红黑树。
散列表碰撞攻击
恶意攻击者,通过设计特殊的数据结构,使得所有的数据经过散列函数后,散列到同一个槽中,导致散列表退化成链表。从而达到拒绝服务攻击(DoS)的目的。
如何设计散列表
散列函数的设计不能太复杂
散列函数生成的值要尽可能随机并且均匀发分布
工业级的散列表有哪些要求?
支持快速的查询、插入、删除操作。
内存占用合理,不能浪费过多的内存空间。
性能稳定,极端情况下,散列表的性能也不能退化到无法接受的情况。
为什么散列表和链表会经常放在一起使用?
因为散列表是动态数据结构,不停的有数据插入和删除,所以当我们希望进行顺序遍历散列表中的数据的时候,都需要先进行排序,那么效率是很低的。为了解决这个问题,我们将散列表和链表(或跳表)结合在一起使用。其次查找数据需要遍历链表,时间复杂度很高,O(n)。
LRU缓存淘汰算法(把数据放在散列表上,然后用双向链表串连起数据来。)
Redis的有序集合
LinkedHashMap也是通过双向链表和散列表连中数据结构来实现的,Linked 指的是双向链表。