- 浏览: 25361 次
- 性别:
文章分类
最新评论
LinkedHashMap源码分析
hashMap源码分析:hashMap源码分析
版本说明:jdk1.7.0_79
LinkedHashMap继承于HashMap,是一个有序的Map接口的实现。有序指的是元素可以按照一定的顺序排列,比如元素的插入顺序,或元素被访问的顺序。
LinkedHashMap的工作原理
说明:该图来源于其它博客,本人较懒,信手拈来,感谢!
LinkedHashMap在存储数据时,和HashMap一样,也是先通过比较key的hashCode来定位数组中的位置,定位后,如果不存在冲突,则将元素插入到链表的尾部。只是,此时的链表是双向链表。
HashMap中Entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
LinkedHashMap中的Entry
private static class Entry<K,V> extends HashMap.Entry<K,V> {
//before和after指针(用于双向列表的迭代遍历)
Entry<K,V> before, after;
属性
除了继承自HashMap的属性外,LinkedHashMap还有自己特有的几个属性。
/**
* The head of the doubly linked list.
* 双向链表的头结点。整个LinkedHashMap中只有一个header, 它将哈希表中所有的Entry贯穿起来。header中不保存K-V对,只保存前后节点指针。
*/
private transient Entry<K,V> header;
/**
*
* 双向链表中元素排序规则的标志位。
* true:按访问顺序排序
* false:按插入顺序排序(默认)
*/
private final boolean accessOrder;
构造方法
比HashMap多了一个重载的构造器,可以手动指定元素的排列顺序。
public LinkedHashMap(int initialCapacity,
float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其它方法
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
* ??被父类的构造器和伪构造(clone,readObject)调用,当有元素插入之前掉用??(??不会翻译??)
* 作用:初始化一个空的双向循环链表(头结点中不保存数据)
*/
@Override
void init() {
//初始化头节点。(不保存数据。所以,k=v=null,hash=-1表示不存在,next指针为null)
header = new Entry<>(-1, null, null, null);
//此时,将向前和向后的指针都指向头节点。
header.before = header.after = header;
}
/**
* Transfers all entries to new table array. This method is called
* by superclass resize. It is overridden for performance, as it is
* faster to iterate using our linked list.
*
* 覆写了父类的transfer方法,被父类的resize方法调用。
* 扩容后,将k-v键值对重新映射到新的newTable中
* 覆写该方法的目的是为了提高复制的效率(这里充分利用双向循环链表的特点进行迭代,不用对底层的数组进行for循环。
*/
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*
* 覆写HashMap中的containsValue方法,
* 覆写该方法的目的同样是为了提高查询的效率,
* 利用双向循环链表的特点进行查询,少了对数组的外层for循环
*/
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
/**
* 覆写HashMap中的get方法,通过getEntry方法获取Entry对象。
*
* 注意这里的recordAccess方法,
* 如果链表中元素的排序规则是按照插入的先后顺序排序的话,该方法什么也不做,
* 如果链表中元素的排序规则是按照访问的先后顺序排序的话,则将e移到链表的末尾处。
*/
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
/**
* 清空双向列表 ,并将其还原为只有头结点的空链表
*/
public void clear() {
super.clear();
//前向指针和后向指针都指向头节点
header.before = header.after = header;
}
/**
* LinkedHashMap中的Entry
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
//前向和后向指针(用于双向列表的元素查找)
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
/**
* 双向循环链表中,删除当前的Entry
*/
private void remove() {
//当前节点的上一个节点的after指针指向下一个节点
before.after = after;
//下一个节点的before指针指向当前节点的上一个节点
after.before = before;
}
/**
* 双向循环立链表中,将当前的Entry插入到existingEntry的前面
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*
* 覆写HashMap中的recordAccess方法(HashMap中该方法为空),
* 当调用父类的put方法,在发现插入的key已经存在时,会调用该方法,
* 调用LinkedHashmap覆写的get方法时,也会调用到该方法,
*
* 该方法提供了LRU算法的实现,它将最近使用的Entry放到双向循环链表的尾部,
* accessOrder为true时,get方法会调用recordAccess方法
* put方法在覆盖key-value对时也会调用recordAccess方法
* 它们导致Entry最近使用,因此将其移到双向链表的末尾
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果设置的是按访问顺序来存储元素
if (lm.accessOrder) {
lm.modCount++;
//删除当前Entry
remove();
//并将当前Entry添加到双向链表末尾
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
/**
* 双向列表用到的迭代器
*/
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
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;
}
}
/**
* key迭代器
*/
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
/**
* value迭代器
*/
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
/**
* Entry迭代器
*/
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*
* 覆写HashMap中的addEntry方法,LinkedHashmap并没有覆写HashMap中的put方法,
* 而是覆写了put方法所调用的addEntry方法和recordAccess方法,
* put方法在插入的key已存在时,会调用recordAccess方法,否则调用addEntry插入新的Entry
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
// 双向链表的第一个有效节点(header后的那个节点)为近期最少使用的节点
Entry<K,V> eldest = header.after;
// 删除掉该近期最少使用的节点
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
//创建新的Entry,并将其插入到数组对应槽的单链表的头结点处,这点与HashMap中相同
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//每次插入Entry时,都将其移到双向链表的尾部,
//这便会按照Entry插入LinkedHashMap的先后顺序来迭代元素,
//同时,新put进来的Entry是最近访问的Entry,把其放在链表末尾 ,符合LRU算法的实现
e.addBefore(header);
size++;
}
/*
*
* 该方法是用来被覆写的,一般如果用LinkedHashmap实现LRU算法,就要覆写该方法,
* 比如可以将该方法覆写为如果设定的内存已满,则返回true,这样当再次向LinkedHashMap中put
* Entry时,在调用的addEntry方法中便会将近期最少使用的节点删除掉(header后的那个节点)。
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
总结:
1.LinkedHashMap继承于HashMap。底层实现是使用数组+双向链表。
2.默认是按照元素添加的顺序来存储元素的。
如果accessOrder=true(按照元素被访问的方式来存储元素),则会使用LRU(Less Recent Used:最少最近被使用)算法,每次插入的元素都会插入到双向链表的尾部。因为插入元素就相当于访问了该元素。
3.LinkedHashMap同样是非线程安全的,只在单线程环境下使用。如果要多线程使用请使用Collections.synchronizedMap(new LinkedHashMap(…));
4.LinkedHashMap跟HashMap一样,允许key和value都为null。
相关推荐
Java集合系列之LinkedHashMap源码分析 Java集合系列之LinkedHashMap源码分析是Java集合框架中的一部分,主要对LinkedHashMap的源码进行了详细的分析。LinkedHashMap是继承自HashMap的,它重新写了一个Entry,在原来...
Java集合框架源码分析之LinkedHashMap详解 Java集合框架中的LinkedHashMap是HashMap的子类,它继承了HashMap的存储结构,但引入了一个双向链表的头结点,将所有put到LinkedHashMap的节点连接成一个双向循环链表,...
ArrayList核心源码+扩容机制分析LinkedList核心源码分析HashMap核心源码+底层数据结构分析ConcurrentHashMap核心源码+底层数据结构分析LinkedHashMap核心源码分析CopyOnWriteArrayList核心源码分析...
项目相关 项目介绍 使用建议 贡献指南 常见问题 Java 基础 知识点/面试题总结 : (必看 ): Java 基础常见知识点&面试题总结(上) ...LinkedHashMap 核心源码分析 CopyOnWriteArrayList 核心源码分析
本文将深入剖析Java集合的源码,探讨其内部实现机制,并结合常见面试题,帮助你更好地理解和应用这些知识。 首先,我们从基础开始,Java集合框架主要分为两大类:List(列表)和Set(集合)。List接口包括ArrayList...
这篇源码分析将深入探讨HashMap的工作原理和内部实现。 在HashMap中,每个键值对被封装在一个Entry对象中,这些Entry对象存储在一个数组中。当插入新的键值对时,HashMap会根据键的哈希值计算出数组的索引位置。...
集合源码分析 编程笔记 学习、总结、记录 ! —— since 2018/20 :bar_chart: :hot_beverage: :mobile_phone: :laptop: :floppy_disk: :pager: :globe_with_meridians: :file_cabinet: :books: :bar_chart: 算法和...
计算机后端-Java-Java核心基础-第25章 集合02 12. HashMap在JDK8中的源码分析.avi
JDK1.8源码分析 相关的原始码分析结果会以注解的形式体现到原始码中 已完成部分: ReentrantLock CountDownLatch Semaphore HashMap TreeMap LinkedHashMap ConcurrentHashMap 执行器 ...
总的来说,Java集合框架源码分析可以帮助我们掌握集合操作的底层原理,提高代码性能,增强对并发编程的理解,并且有助于我们设计出更高效、更安全的Java程序。通过对Collections类的深入学习,我们可以更好地利用...
Java集合专题总结:HashMap和HashTable源码...本文总结了HashMap和HashTable的源码学习和面试总结,涵盖了它们的存储结构、构造方法、get和put方法的源码分析、Hash表的特点和缺点、HashTable和HashMap的区别等内容。
通过以上分析,我们可以看到Java 1.8 HashMap的put方法在处理哈希冲突时,不仅使用了链表,还在节点数量达到一定阈值时切换为红黑树,有效提高了数据结构的性能。同时,通过扩容机制,HashMap能够保持较低的哈希冲突...
源码分析:LinkedHashMap 集合框架 (第 14 篇) 源码分析:TreeMap 集合框架 (第 15 篇) 源码分析:Set 集合 集合框架 (第 16 篇) 源码分析:BlockingQueue 接口 集合框架 (第 17 篇) 源码分析:...
本篇文章将主要围绕这些Map的主要实现类进行源码分析,探讨其内部工作原理。 一、HashMap HashMap是最常用的Map实现类,它的核心原理是基于哈希表。HashMap使用一个Entry数组存储键值对,其中Entry是一个内部类,...
2. **源码分析** - **容器实现**:这些类的实现通常包括一个内部存储结构(如数组或链表)和一些基本操作,如添加、删除、查找等。例如,ArrayList的`add()`方法会检查容量并根据需要进行扩容,LinkedList的`remove...
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
2. **桶(Bucket)结构**:分析HashMap如何通过哈希值将元素分配到不同的桶中,以及桶内的链表或红黑树结构。 3. **扩容机制**:研究HashMap如何动态调整容量,以及在扩容过程中如何迁移元素。 4. **链表转红黑树**...
Java集合框架是Java编程中非常重要的部分,它提供了一种高效、灵活的数据组织方式。本文主要探讨了几个关键...通过对源码的深入分析,我们可以更好地掌握Java集合框架的工作原理,并根据实际需求选择最适合的数据结构。
源码分析是理解这些数据结构工作原理的关键,可以帮助开发者提升程序性能和代码质量。以下是一些关于Java数据结构的核心知识点: 1. 数组:数组是最基本的数据结构,它在内存中分配连续的空间来存储相同类型的数据...