美文网首页Anmdroid难点解答
Java HashMap,LinkedHashMap 实现原理分

Java HashMap,LinkedHashMap 实现原理分

作者: 詹徐照 | 来源:发表于2018-04-01 17:11 被阅读84次

    相关类继承结构

    image.png
    @startuml
    interface Map {
      interface Entry
    
      int size()
      boolean containersKey()
      boolean containersValue()
      V get(Object)
      V put(K,V)
      V remove(Object)
      boolean remove(K, V)
      boolean replace(K,V,V)
      V replace<K,V)
      void putAll(Map<? extends K, ? extends V>
      void clear()
      Set<K> keySet()
      Collection<V> values()
      Set<Entry<K,V>> entrySet()
    }
    
    class HashMap {
      static class Node
      static final class TreeNode
    
      Node[] table
      int size
      int modCound
      int threshold
      loadFactor
    
      void afterNodeAccess()
      void afterNodeInsertion()
      void afterNodeRemoval()
    }
    
    class LinkedHashMap {
      static class LinkedHashMapEntry
    
      LinkedHashMapEntry head
      LinkedHashMapEntry tail
      boolean accessOrder
    
      void afterNodeAccess()
      void afterNodeInsertion()
      void afterNodeRemoval()
    }
    
    interface Map.Entry {
      K getKey()
      V getValue()
      V setValue()
      boolean equals
      int hashCode()
      Comparator comparintByKey()
      Comparator comparintByValue()
    }
    
    class HashMap.Node{
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    }
    
    class HashMap.TreeNode {
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
    }
    
    class LinkedHashMap.LinkedHashMapEntry{
      LinkedHashMapEntry<K,V> before;
      LinkedHashMapEntry<K,V> after;
    }
    
    Map <|.. HashMap
    HashMap <|-- LinkedHashMap
    
    Map.Entry <|.. HashMap.Node
    HashMap.Node <|-- LinkedHashMap.LinkedHashMapEntry
    LinkedHashMap.LinkedHashMapEntry <|-- HashMap.TreeNode
    @enduml
    

    HashMap原理概述

    • JDK1.8之前:HashMap内部是由数组+单向链表实现的,如图HashMap Internal Structure before JDK1.8。
    • JDK1.8以后: HashMap内部是由数组+单向链表+红黑树实现的,如图HashMap Internal Structure after JDK1.8。
    • 数组和链表存放的都是HashMap.Node对象,Node是一个单链结构,具有hash, key, value, next四个field。
    • 具有相同hash值的Node放在同一个链表中,该链表的头放在在table中。
    HashMap Internal Structure before JDK1.8
    图片出处:How HashMap Works Internally In Java? HashMap Internal Structure after JDK1.8
    图片出处:深入分析hashmap

    HashMap源码分析

    put(K key, V value)
    put方法的大体流程可以概括为:

    1. 根据key计算hash值;
    2. 根据hash值在table中找对应的Node:
      没有,直接new一个Node,放到table对应的位置上;
      有,看key是否equal,equal就给Node赋值新的value,不equal就遍历Node所在链表,找到equal的Node的话就赋值新的value,找不到就new一个Node放到链表末尾。如果链表长度超过阈值,将其转化为红黑树。
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        /**
         * Implements Map.put and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            // Node<K,V>[] tab即是Map中的table
            // Node p 为table中与hash值对应的Node
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 如果table为空,初始化table
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            // 以i = (n - 1) & hash值为index从table中取出Node,赋值给p
            // 如果p为空,则以hash、key、value等入参new出Node对象,赋值给table[i]
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                // Node e可以理解为Map中key与入参中的key相等的Node
                Node<K,V> e; K k;
                // p的key与入参的key相等
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                // p的key与入参的key不相等,LinkedHashMap会走下面这个分支,因为LinkedHashMap覆写了newNode(),它的Node是TreeNode
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                // p的key与入参的key不相等,HashMap会走这个分支
                else {
                    // 遍历以p开头的链表
                    // 如果找到key与入参相等的节点,结束循环;
                    // 如果循环结束还没找到key相同的,则new一个Node放到链表的尾部。
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            // 当链表深度达到阈值时,将链表转化为红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                // 如果e != null(Map中存在key与传入参数相等的Node),直接将入参的value赋值到该Node上,return旧的value
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            // 往table中新增了new出来的p会走到这里
            // 根据现在的table的size判断是否要resize
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    

    为了方便理解,下面是put(key, value)执行的伪代码

    put(key,value);
    int hash = hash(key);
    putVal(hash, key, value, ...);
    if (Node[] table is Empty?) {
      init table
    }
    int index = (n - 1) & hash;
    Node p = table[index];
    if (p == null) {
      table[index] = new Node(hash, key, value, null);
    }else {
      Node e;
      if (p.key equals key) {
        e = p;
      } else if(is LinkedHashMap?) {
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      } else {
        // literate linked list
        for (int binCount = 0; true ; ++binCount) {
            e = p.next;
            if (e == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1){
                    treeifyBin(tab, hash);
                }
                break;
            }
            if (e.key equals key)
                break;
            p = e;
        }
      }
      if (e != null) {
        oldValue = e.value;
        e.value = value;
        return oldValue;
      }
    }
    if (++size > threshold) {
      resize();
    }
    return null;
    

    get(key)
    get过程:

    1. 根据key计算hash值;
    2. 根据hash值在table中找对应的Node:
      没有,return null
      有,看key是否equal,equal,返回Node的value,不equal,再遍历链表,看链表中是否有equal的node,没有返回null,有返回Node的value;
        public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
        /**
         * Implements Map.get and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @return the node, or null if none
         */
        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                        ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    

    LinkedHashMap原理概述

    LinkedHashMap是在HashMap的基础上演化来的,主要区别在于LinkedHashMap的Node是LinkedHashMapEntry,是双向链表。

    image.png
    图片出处:https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

    LinkedHashMap 特点

    1. Node是有序的,顺序由insert的顺序决定;
    2. 可以设置AccessOrder,最近被访问的节点会被移到链表末尾,非常适合做LRUCache;
     * This implementation differs from
     * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
     * all of its entries.  This linked list defines the iteration ordering,
     * which is normally the order in which keys were inserted into the map
     * (<i>insertion-order</i>).
    
     * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
     * provided to create a linked hash map whose order of iteration is the order
     * in which its entries were last accessed, from least-recently accessed to
     * most-recently (<i>access-order</i>).  This kind of map is well-suited to
     * building LRU caches.  Invoking the {@code put}, {@code putIfAbsent},
     * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent},
     * {@code computeIfPresent}, or {@code merge} methods results
     * in an access to the corresponding entry (assuming it exists after the
     * invocation completes). 
    

    LinkedHashMap 源码分析

    image.png

    从类图可以看出,LinkedHashMap与HashMap相比,区别主要在于:

    1. Node是LinkedHashMapEntry(双向链表结构);
    2. 多了3个field:head,tail,accessOrder。
    3. 重写了HashMap的三个空实现方法:afterNodeAccess、afterNodeInsertion、afterNodeRemoval;

    当访问过某个节点后,该节点会被放置到链表的末尾。

        void afterNodeAccess(Node<K,V> e) { // move node to last
            LinkedHashMapEntry<K,V> last;
            if (accessOrder && (last = tail) != e) {
                LinkedHashMapEntry<K,V> p =
                    (LinkedHashMapEntry<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;
            }
        }
    

    参考资料:
    Java HashMap工作原理及实现 by 杨文杰
    Java HashMap工作原理及实现 by Yikun
    Java LinkedHashMap工作原理及实现
    深入分析hashmap

    相关文章

      网友评论

        本文标题:Java HashMap,LinkedHashMap 实现原理分

        本文链接:https://www.haomeiwen.com/subject/hddocftx.html