Java源码系列-LinkedHashMap,高薪面试必学
2020-05-06 16:28:40来源:博客园 阅读 ()
Java源码系列-LinkedHashMap,高薪面试必学
面试题
- LinkedHashMap如何实现有序的
- 如何用LinkedHashMap实现LRU
源码解析
LinkedHashMap在Map的基础上进行了扩展,提供了按序访问的能力。这个顺序通过accessOrder控制,可以是结点的插入顺序,也可以是结点的访问时间顺序。
LinkedHashMap还提供了removeEldestEntry方法,可以用来删除最老访问结点。
这里要注意:找工作看的是项目经验:Java架构项目经验永远是核心,如果你没有最新JAVA架构实战教程及大厂30k+面试宝典,可以去小编的Java架构学习.裙 :七吧伞吧零而衣零伞 (数字的谐音)转换下可以找到了,里面很多新JAVA架构项目教程,还可以跟老司机交流讨教!
通过accessOrder和removeEldestEntry可以用来实现LRU缓存。
如图所示,LinkedHashMap实现顺序访问的方法比较简单,在HashMap实现之外,还维护了一个双向链表。每当插入结点时,不仅要在Map中维护,还需要在链表中进行维护。HashMap中的put, get等方法都提供了一些钩子方法,如afterNodeAccess
、afterNodeInsertion
和afterNodeRemoval
等。通过这些方法,LinkedHashMap可以对这些结点进行一些特性化的维护。
当遍历LinkedHashMap时通过遍历链表代替遍历Map中的各个槽,从而实现按序访问。
底层数据结构
/**
* LinkedHashMap普通的链表结点,继承了HashMap的Node,在此基础上
* 对每个Node添加了before和after指针。LinkedHashMap在HashMap的
* 基础上,还维护了一个双向链表,链表中的结点就是Map中的每个结点,
* 通过此链表,LinkedHashMap就实现了维护结点顺序的目的
*/
static class Entry<K, V> extends HashMap.Node<K, V> {
Entry<K, V> before, after;
Entry(int hash, K key, V value, Node<K, V> next) {
super(hash, key, value, next);
}
}
/**
* 双向链表的头结点
*/
transient LinkedHashMap.Entry<K, V> head;
/**
* 双向链表的尾结点
*/
transient LinkedHashMap.Entry<K, V> tail;
/**
* true-按访问顺序(最早操作过的结点靠前)
* false-按插入顺序遍历(最早插入的结点靠前)
*
* @serial
*/
final boolean accessOrder;
复制代码
Node结点
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
LinkedHashMap.Entry<K, V> p =
new LinkedHashMap.Entry<K, V>(hash, key, value, e);
// 创建一个key-value对时,不仅要放入map中,还有放入LinkedHashMap
// 内置的双向链表中,用来维护插入顺序
linkNodeLast(p);
return p;
}
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
LinkedHashMap.Entry<K, V> q = (LinkedHashMap.Entry<K, V>) p;
LinkedHashMap.Entry<K, V> t =
new LinkedHashMap.Entry<K, V>(q.hash, q.key, q.value, next);
// 用t结点代替q结点在双向链表中的位置
transferLinks(q, t);
return t;
}
TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
TreeNode<K, V> p = new TreeNode<K, V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
LinkedHashMap.Entry<K, V> q = (LinkedHashMap.Entry<K, V>) p;
TreeNode<K, V> t = new TreeNode<K, V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
复制代码
工具方法
// 在双向链表尾部添加结点
private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
LinkedHashMap.Entry<K, V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
// 使用dst结点覆盖src结点在双向链表中的位置
private void transferLinks(LinkedHashMap.Entry<K, V> src,
LinkedHashMap.Entry<K, V> dst) {
LinkedHashMap.Entry<K, V> b = dst.before = src.before;
LinkedHashMap.Entry<K, V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
/**
* 每次插入新Node时,是否需要删除最老的结点。
*
* @return true-删除最老结点,false-不删除
*/
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return false;
}
复制代码
构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* 可以指定遍历结点的顺序
*
* @param accessOrder true-按访问顺序(最早操作过的结点靠前)
* false-按插入顺序遍历(最早插入的结点靠前)
*/
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
复制代码
钩子方法
// 重写HashMap中提供给LinkedHashMap的钩子方法
/**
* HashMap 调用remove方法后,会调用这个钩子方法,e为删除的结点
*/
void afterNodeRemoval(Node<K, V> e) {
// p = e; b = p.before; a = p.after;
LinkedHashMap.Entry<K, V> p =
(LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
// 从双向链表中删除p结点
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
/**
* HashMap 调用put等方法后,会调用这个钩子方法
*
* @param evict false-table处于创建模式(即通过构造方法调用)
*/
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K, V> first;
// 如果map中存在元素,且需要删除eldest元素,则从链表和Map中
// 删除双向链表头结点。removeEldestEntry在LinkedHashMap默认返回
// false。该方法可以用来实现LRU缓存
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
/**
* HashMap 调用put, get等方法后,会调用这个钩子方法,更改最新访问时间。
* 可以用来实现LRU缓存
*
* @param e 最近操作过的结点
*/
void afterNodeAccess(Node<K, V> e) {
LinkedHashMap.Entry<K, V> last;
// 如果accessOrder为true,代表按最新遍历时间维护链表
// 则将e移至链表尾部
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K, V> p =
(LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
复制代码
其他
public boolean containsValue(Object value) {
// 因为LinkedHashMap中使用双向链表维护了所有Node,所以只需要遍历
// 双向链表即可遍历所有Node。而不用遍历Map。
for (LinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
public V get(Object key) {
Node<K, V> e;
// 寻找key对应结点
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果需要按访问时间排序,则更新结点在双向链表中的位置
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K, V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public void clear() {
super.clear();
head = tail = null;
}
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
// 覆写了遍历方法,用遍历双向链表代替遍历map,从而实现了按序遍历。
for (LinkedHashMap.Entry<K, V> e = head; e != null; e = e.after)
action.accept(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
复制代码
迭代器
abstract class LinkedHashIterator {
// 下一个要遍历的结点
LinkedHashMap.Entry<K, V> next;
// 上一个遍历过的结点
LinkedHashMap.Entry<K, V> current;
// 版本号
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K, V> nextNode() {
LinkedHashMap.Entry<K, V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// 遍历双向链表的下一个结点
next = e.after;
return e;
}
public final void remove() {
Node<K, V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
复制代码
面试题解答
-
LinkedHashMap如何实现有序的
LinkedHashMap在HashMap的基础上,还将每个key-value对应的Node维护在了一个额外的双向链表中。
LinkedHashMap通过accessOrder可以支持按插入的顺序访问,或者按遍历的顺序访问
accessOrder
- false: 按插入顺序排序,map中每插入一个结点时,将这个结点同时放置在双向链表的结尾
- true: 按访问顺序排序,当操作map中的一个结点时,通过HashMap提供的钩子方法(
afterNodeAccess
、afterNodeInsertion
和afterNodeRemoval
)找到这个结点在链表中的位置,并移动到链表结尾。这样链表的头结点就是链表最久没有访问过的结点
遍历的时候,通过便利双向链表代替遍历map的每个槽,来实现顺序访问。
-
如何用LinkedHashMap实现LRU
首先分析LRU算法有哪些特性
- 新数据插入到链表尾部(代表最新访问);
- 每当缓存命中(即缓存数据被访问)则将数据移到链表尾部(代表最新访问);
- 当链表满的时候,将链表头部的数据丢弃(删除最久未访问结点);
在LinkedHashMap保证结点有序的情况下,通过设置accessOrder为true,采用按遍历顺序维护结点。
- put方法将结点插入到双向链表尾部实现LRU特性 1;
- 钩子方法
afterNodeAccess
实现LRU特性 2; - 实现removeEldestEntry方法,删除最久未访问结点。实现LRU特性 3;
最后注意:光理论是不够的,记住:Java架构项目经验永远是核心,如果你没有最新JAVA架构实战教程及大厂30k+面试宝典,可以去小编的Java架构学习.裙 :七吧伞吧零而衣零伞 (数字的谐音)转换下可以找到了,里面很多新JAVA架构项目教程,还可以跟老司机交流讨教!
本文的文字及图片来源于网络加上自己的想法,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理
原文链接:https://www.cnblogs.com/chengxuyuanaa/p/12836713.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- Spring系列.ApplicationContext接口 2020-06-11
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash