`

LinkedHashMap

阅读更多

今天有个需求,要求把某个公司和这个公司的有序产品放到map中存储,同时放入这个map中的公司时有顺序要求的——什么顺序放进去,什么顺序拿出来!
用普通的HashMap解决这个需求就不合适了。jdk提供的集合框架中的LinkedHashMap比较适合这个需求。那么他又是怎么实现这个功能的呢?一起来看看源码吧。

  • LinkedHashMap的接口定义如下:

 

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>


这里可以看出,LinkedHashMap就是HashMap的一个子类。

  • Entry的关键区别:
  •  
    • HashMap的Entry定义片段:
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        final int hash;
        Entry<K,V> next;
  •  
    • LinkedHashMap的Entry定义片段:
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // 可以看到在HashMap.Entry基础上,增加了下面两个属性!
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
  • 再来看看HashMap的put方法
    public V put(K key, V value) {
        //从这里可以看出,HashMap是允许以null为key的存储的!
	if (key == null)
	    return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //LinkedHashMap override了下面这个方法!
        addEntry(hash, key, value, i);
        return null;
    }

 

  • 那么put时,两个方法最大的区别就是上面的这个addEntry方法了,分别看一下:
    //HashMap中的方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        //这里可以看出,如果hash不均匀的话,会造成table中的某些entry元素比较庞大(因为里面会嵌套N层的子entry)
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

    //LinkedHashMap中的方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);
        
        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        //这里LinkedHashMap本身的removeEldestEntry方法是直接返回false的,但他的N个子类可能会采用不用的淘汰老元素的策略。
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold) 
                resize(2 * table.length);
        }
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        //注意:这里将新创建的元素插入到连表里header的前面(也就是Map的put方法中将entry加入双向链表的地方)
        e.addBefore(header);
        size++;
    } 
  • 剩下就是看LinkedHashMap是如何实现这个按插入的顺序展示entrySet中的元素了:
//HashMap中的EntryIterator中的nextEntry方法
        Entry<K,V> nextEntry() { 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null) 
                throw new NoSuchElementException();
                
            Entry<K,V> n = e.next;
            Entry[] t = table;
            int i = index;
            while (n == null && i > 0)
                n = t[--i];
            index = i;
            next = n;
            return current = e;
        }

//LinkedHashMap重新定义了自己的内部类EntryIterator(当然其实HashMap中的EntryIterator也是private的),这里关键的不同就在这个nextEntry方法了
	Entry<K,V> nextEntry() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            //关键在这里,会将nextEntry指向当前元素的下一个元素!
            nextEntry = e.after;
            return e;
	}

 好了,关键原理找到了,其实其中还有很多细节,不过对理解原理不重要,可以暂时忽略!

     

    分享到:
    评论

    相关推荐

      java中HashMap,LinkedHashMap,TreeMap,HashTable的区别

      ### Java中HashMap, LinkedHashMap, TreeMap,HashTable的区别 在Java编程语言中,`Map`接口是集合框架中的一个重要组成部分,用于存储键值对。本文将详细分析四种常用的`Map`实现类:`HashMap`, `LinkedHashMap`, ...

      HashMap,HashTable,LinkedHashMap,TreeMap的区别

      HashMap, HashTable, LinkedHashMap, TreeMap 的区别 在 Java 中,Map 是一个非常重要的集合类,用于存储键值对。其中,HashMap, HashTable, LinkedHashMap, TreeMap 是四种常用的 Map 实现类,每种类都有其特点和...

      LinkedHashmap的使用

      **HashMap与LinkedHashMap的区别** HashMap是Java集合框架中的一员,它是基于哈希表实现的,提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。然而,HashMap不保证元素的顺序,迭代时元素的顺序可能与插入...

      一文搞懂Java的LinkedHashMap.docx

      《深入解析Java的LinkedHashMap》 HashMap作为Java中常用的键值对存储结构,以其高效的查找速度赢得了广大开发者们的青睐。然而,HashMap的无序性在某些特定场景下却显得力不从心,例如当我们需要按照插入顺序来...

      JavaLinkedHashMap源码解析Java开发Ja

      Java LinkedHashMap 是一个根据插入顺序或者访问顺序来维护元素顺序的哈希表与链表相结合的数据结构。在 Java 集合框架中,它继承自 HashMap 类,并实现了 Map 接口。LinkedHashMap 的特点在于,它不仅仅是一个哈希...

      Java集合系列(LinkedHashMap+LinkedList+ArrayList)

      Java 集合系列(LinkedHashMap+LinkedList+ArrayList) Java 集合系列是 Java 语言中的一种数据结构,用于存储和操作数据。今天,我们将介绍 Java 集合系列中的三个重要成员:LinkedHashMap、LinkedList 和 ArrayList...

      java软件技术文档-深入java8的集合4:LinkedHashMap的实现原理.pdf

      K,V&gt; p) { } 这些方法是 HashMap 为 LinkedHashMap 提供的回调接口,用于在插入、访问和删除节点后执行特定的操作。LinkedHashMap 利用这些回调方法来维护其内部链表的顺序。 1. **afterNodeAccess(Node,V&gt; p)**: ...

      java HashMap,TreeMap与LinkedHashMap的详解

      在Java编程语言中,`HashMap`、`TreeMap`和`LinkedHashMap`都是`java.util.Map`接口的实现,它们提供了不同的数据存储和访问策略。本文将深入探讨这三种数据结构的特点、工作原理以及适用场景。 1. **HashMap** `...

      java集合-LinkedHashMap的使用

      LinkedHashMap是Java中的一种特殊类型的HashMap,它保留了插入顺序,即按照元素插入的先后顺序进行排序

      Java集合框架源码分析之LinkedHashMap详解

      Java集合框架源码分析之LinkedHashMap详解 Java集合框架中的LinkedHashMap是HashMap的子类,它继承了HashMap的存储结构,但引入了一个双向链表的头结点,将所有put到LinkedHashMap的节点连接成一个双向循环链表,...

      Java集合系列之LinkedHashMap源码分析

      Java集合系列之LinkedHashMap源码分析 Java集合系列之LinkedHashMap源码分析是Java集合框架中的一部分,主要对LinkedHashMap的源码进行了详细的分析。LinkedHashMap是继承自HashMap的,它重新写了一个Entry,在原来...

      Java使用LinkedHashMap进行分数排序

      Java使用LinkedHashMap进行分数排序 Java中进行分数排序是非常重要的,特别是在学生成绩统计的问题中。传统的排序方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在...

      set:使用LinkedHashMap在Go(Golang)中简单的Set数据结构实现

      Set是使用LinkedHashMap在Go(Golang)中简单的Set数据结构实现。 该库允许您获取一组int64或string而没有重复的项目。 用法 package main import ( "fmt" "github.com/StudioSol/set" ) func main () { ...

      Java LinkedHashMap工作原理及实现

       在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:  LinkedHashMap&lt;String&gt; lmap = new LinkedHashMap();  lmap.put(语文, 1)...

      HashMap遍历

      ### HashMap遍历详解 在Java编程中,`HashMap`是一种常用的数据结构,它实现了`Map`接口,提供了基于哈希表的存储方式,...同时,对于不允许null值的情况,可以选择`LinkedHashMap`或`TreeMap`等其他类型的地图实现。

    Global site tag (gtag.js) - Google Analytics