江苏龙网

  1. 主页 > 生活百科 > >

图解LinkedHashMap原理( 四 )

LinkedHashMa


后面调用了LinkedHashMap.Entry的recordAccess方法，上面分析过put过程中这个方法，其实就是在访问顺序的LinkedHashMap进行了get操作以后，重新排序，把get的Entry移动到双向链表的表尾 。
2.9 遍历方式取数据
我们先来看看HashMap使用遍历方式取数据的过程：

图解LinkedHashMap原理

文章插图
 
HashMap遍历.png
很明显，这样取出来的Entry顺序肯定跟插入顺序不同了，既然LinkedHashMap是有序的，那么它是怎么实现的呢？
先看看LinkedHashMap取遍历方式获取数据的代码：
Map<String, String> linkedHashMap = new LinkedHashMap<>(); linkedHashMap.put("name1", "josan1"); linkedHashMap.put("name2", "josan2"); linkedHashMap.put("name3", "josan3"); // LinkedHashMap没有重写该方法，调用的HashMap中的entrySet方法 Set<Entry<String, String>> set = linkedHashMap.entrySet(); Iterator<Entry<String, String>> iterator = set.iterator(); while(iterator.hasNext()) { Entry entry = iterator.next(); String key = (String) entry.getKey(); String value = https://www.isolves.com/it/cxkf/bk/2019-08-30/(String) entry.getValue(); System.out.println("key:" + key + ",value:" + value); }LinkedHashMap没有重写entrySet方法，我们先来看HashMap中的entrySet，如下：
public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } // 无关代码 ...... }可以看到，HashMap的entrySet方法，其实就是返回了一个EntrySet对象 。
我们得到EntrySet会调用它的iterator方法去得到迭代器Iterator，从上面的代码也可以看到，iterator方法中直接调用了newEntryIterator方法并返回，而LinkedHashMap重写了该方法
Iterator<Map.Entry<K,V>> newEntryIterator() {return new EntryIterator(); }这里直接返回了EntryIterator对象，这个和上一篇HashMap中的newEntryIterator方法中一模一样，都是返回了EntryIterator对象，其实他们返回的是各自的内部类 。我们来看看LinkedHashMap中EntryIterator的定义：
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() {return nextEntry(); } }该类是继承LinkedHashIterator，并重写了next方法；而HashMap中是继承HashIterator 。
我们再来看看LinkedHashIterator的定义：
private abstract class LinkedHashIterator<T> implements Iterator<T> { // 默认下一个返回的Entry为双向链表表头的下一个元素 Entry<K,V> nextEntry = header.after; Entry<K,V> lastReturned = null; public boolean hasNext() { return nextEntry != header; } Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (nextEntry == header) throw new NoSuchElementException(); Entry<K,V> e = lastReturned = nextEntry; nextEntry = e.after; return e; } // 不相关代码 ...... }我们先不看整个类的实现，只要知道在LinkedHashMap中，Iterator<Entry<String, String>> iterator = set.iterator()，这段代码会返回一个继承LinkedHashIterator的Iterator，它有着跟HashIterator不一样的遍历规则 。
接着，我们会用while(iterator.hasNext())去循环判断是否有下一个元素，LinkedHashMap中的EntryIterator没有重写该方法，所以还是调用LinkedHashIterator中的hasNext方法，如下：
public boolean hasNext() { // 下一个应该返回的Entry是否就是双向链表的头结点 // 有两种情况：1.LinkedHashMap中没有元素；2.遍历完双向链表回到头部 return nextEntry != header; }nextEntry表示下一个应该返回的Entry，默认值是header.after，即双向链表表头的下一个元素 。而上面介绍到，LinkedHashMap在初始化时，会调用init方法去初始化一个before和after都指向自身的Entry，但是put过程会把新增加的Entry加入到双向链表的表尾，所以只要LinkedHashMap中有元素，第一次调用hasNext肯定不会为false 。
然后我们会调用next方法去取出Entry，LinkedHashMap中的EntryIterator重写了该方法，如下：
public Map.Entry<K,V> next() {return nextEntry(); }而它自身又没有重写nextEntry方法，所以还是调用的LinkedHashIterator中的nextEntry方法：
Entry<K,V> nextEntry() { // 保存应该返回的Entry Entry<K,V> e = lastReturned = nextEntry; //把当前应该返回的Entry的after作为下一个应该返回的Entry nextEntry = e.after; // 返回当前应该返回的Entry return e; }


推荐阅读


上一篇：Linux系统CPU负载和CPU使用率

下一篇：go语言中关于字符串使用的总结