Day17
学习内容：搞清楚下面三个例子。
1.案例一：LRU 缓存淘汰算法
(1)一个缓存（cache）系统主要包含下面这几个操作
往缓存中添加一个数据；
从缓存中删除一个数据；
在缓存中查找一个数据。
上面3个操作，都涉及查找。
(2)如何用链表实现LRU缓存淘汰算法？
时间复杂度O(n)
(3)如何使用散列表和链表实现LRU缓存淘汰算法？
时间复杂度O(1)
2.案例二：Redis 有序集合
在有序集合中，每个成员对象有两个重要的属性，key（键值）和 score（分值）。
Redis 有序集合的操作
添加一个成员对象；
按照键值来删除一个成员对象；
按照键值来查找一个成员对象；
按照分值区间查找数据，比如查找积分在 [100, 356] 之间的成员对象；
按照分值从小到大排序成员变量；
3.案例三：Java LinkedHashMap
LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。
LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。
为什么散列表和链表经常一块使用？
散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论