嘉兴论坛网站建设,网站名和域名能一样吗,教育机构在线咨询,wordpress js代码编辑器插件文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
7 散列表链表的应用
很多情况下散列表会和链表一起使用。散列表可以通过key查找value。链表可以按照value进行排序。这样就能通过value查找key#xff0c;也可以通…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
7 散列表链表的应用
很多情况下散列表会和链表一起使用。散列表可以通过key查找value。链表可以按照value进行排序。这样就能通过value查找key也可以通过查找value的区间范围查找key。
7.1 LRU 缓存淘汰算法
基本的LRU 单纯的LRU是维护了一个访问时间从大到小的有序链表。因为缓存大小有限当超过缓存的时候需要删除表头。 当要缓存一个数据的时候先查找数据在链表中是否存在。如果存在则删除插入到表尾。如果不存在则看空间是否充足。空间充足直接插入到表尾如果空间不足则删除表头插入到表尾。 LRU支持的操作有 1 插入数据 2 删除数据 3 查找数据 这三个操作都涉及查找操作。链表的查找操作时间复杂度是O(n)。散列表链表就可以将查找操作变为O(1)。 一个双向链表散列表。每个节点数据前驱指针后继指针hnext指针。hnext是为了把节点串在散列表中。前驱指针、后继指针是为了形成一个双向列表。 查找数据的过程。我们通过散列表查找数据时间复杂度O(1)。找到之后把它移动到双向链表的尾部。 删除数据的过程。我们通过散列表查找数据节点利用前驱后继指针删除这个节点。 插入数据的过程。需要先查找这个节点是不是存在。存在移动到双向链表的尾部。不存在需要插入到散列表对应的槽位和双向链表的尾部。如果超出缓存空间则把双向链表头部元素删除。 所有查询的操作通过散列表完成。这三个操作都可以在O(1)时间内完成。
7.2 Redis有序集合
有序集合中每个对象有两个重要属性key和value。 有序集合需要支持的操作有 1 添加一个成员对象。 2 按照key删除成员对象。 3 按照key查找成员对象。 4 按照value区间查找对象。 5 按照value从大到小排序对象。 在跳表我们可以实现按照value排序数据。散列表可以按照key组织数据。即可以在O(1)实现上述5种操作。 Redist还可以按照排名查找对象。这个功能在以后讲。
7.3 Java LinkedHashMap
Java的LinkedHashMap实际是一个LRU缓存的实现版本。是一个散列表双向列表。遍历Map中的元素遍历的顺序是按照访问时间从小到大输出。
7.4 散列表链表结构特点
散列表支持高效地插入、删除、查找操作。 双向链表按照某种顺序遍历数据。 两者结合在一起就可以实现按照某种顺序遍历散列表中的数据。
7.5 应用
假设猎聘网有 10 万名猎头每个猎头都可以通过做任务比如发布职位来积累积分然后通过积分来下载简历。假设你是猎聘网的一名工程师如何在内存中存储这 10 万个猎头 ID 和积分信息让它能够支持这样几个操作 根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息 查找积分在某个区间的猎头 ID 列表 查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。 以积分排序构建一个跳表按照ID做key构建一个散列表。 在散列表中根据ID查找、删除、插入积分信息。 在跳表查找积分区间内的ID。 最后一个操作以后实现目前做不到。
