JAVA7/8中的HashMap

ゝ一世哀愁。 2022-05-25 02:28 114阅读 0赞

Java7 HashMap

HashMap 是最简单的，一来我们非常熟悉，二来就是它不支持并发操作，所以源码也非常简单。

首先，我们用下面这张图来介绍 HashMap 的结构。

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1][]

如图，HashMap 里面是一个数组，数组中每个元素是一个单向链表，每个元素对应一个Entry，通过next指向下一个Entry。

put 过程分析

public V put(K var1, V var2) {
        
            // 当插入第一个元素的时候，需要先初始化数组大小
            if(this.table == EMPTY_TABLE) {
        
                this.inflateTable(this.threshold);
            }
    
            if(var1 == null) {
         //key 是null时执行 最终会放到table[0]中
                return this.putForNullKey(var2);
            } else {
        
                int var3 = this.hash(var1);//对key进行hash获取hash值
                int var4 = indexFor(var3, this.table.length);//通过hash值获取将要放到table的下标index
    
                for(HashMap.Entry var5 = this.table[var4]; var5 != null; var5 = var5.next) {
        //遍历当前下标的entry链 如果key已存在 则set新的value 并将旧的value返回
                    if(var5.hash == var3) {
        
                        Object var6 = var5.key;
                        if(var5.key == var1 || var1.equals(var6)) {
        
                            Object var7 = var5.value;
                            var5.value = var2;
                            var5.recordAccess(this);
                            return var7;
                        }
                    }
                }
    
                ++this.modCount;
                this.addEntry(var3, var1, var2, var4);//key不存在添加新的entry到链表中
                return null;
            }
        }

获取key的hash及计算下标的代码此处不贴，主要看下对key是null值的处理，其最终会放到table\[0\]处

private V putForNullKey(V var1) {
        
            for(HashMap.Entry var2 = this.table[0]; var2 != null; var2 = var2.next) {
        //key相同 直接替换 并返回旧值 所以key是null的entry只能有一个！
                if(var2.key == null) {
        
                    Object var3 = var2.value;
                    var2.value = var1;
                    var2.recordAccess(this);
                    return var3;
                }
            }
    
            ++this.modCount;
            this.addEntry(0, (Object)null, var1, 0);//table中不存在key 则添加新的Entry
            return null;
        }

添加Entry的方法，先判断是否须要扩容，这里也可以很清晰的看到新的Entry会放到链表的头部

void addEntry(int var1, K var2, V var3, int var4) {
        
            if(this.size >= this.threshold && null != this.table[var4]) {
         // 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
                this.resize(2 * this.table.length);
                var1 = null != var2?this.hash(var2):0;
                var4 = indexFor(var1, this.table.length);
            }
    
            this.createEntry(var1, var2, var3, var4);//添加新的entry
        }
    
        void createEntry(int var1, K var2, V var3, int var4) {
        
            HashMap.Entry var5 = this.table[var4];//原位置被新的entry替换，旧的entry作为其next 形成新的链表结构
            this.table[var4] = new HashMap.Entry(var1, var2, var3, var5);
            ++this.size;
        }

get 过程分析

public V get(Object var1) {
        
            if(var1 == null) {
        
                return this.getForNullKey();
            } else {
        
                HashMap.Entry var2 = this.getEntry(var1);
                return null == var2?null:var2.getValue();
            }
        }
    
    final HashMap.Entry<K, V> getEntry(Object var1) {
        
            if(this.size == 0) {
        
                return null;
            } else {
        
                int var2 = var1 == null?0:this.hash(var1);
    	    // 找到对应下标的链表，key相同时返回值
                for(HashMap.Entry var3 = this.table[indexFor(var2, this.table.length)]; var3 != null; var3 = var3.next) {
        
                    if(var3.hash == var2) {
        
                        Object var4 = var3.key;
                        if(var3.key == var1 || var1 != null && var1.equals(var4)) {
        
                            return var3;
                        }
                    }
                }
    
                return null;
            }
        }

JDK8中的HashMap

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。

put 过程分析

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    
     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
             // 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
        // 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
                 // 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
        // 数组该位置有数据
                Node<K,V> e; K k;
                 // 首先，判断该位置的第一个数据和我们要插入的数据，key 是不是"相等"，如果是，取出这个节点
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                     // 如果该节点是代表红黑树的节点，调用红黑树的插值方法，本文不展开说红黑树
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                 // 到这里，说明数组该位置上是一个链表
                    for (int binCount = 0; ; ++binCount) {
        
                     // 插入到链表的最后面(Java7 是插入到链表的最前面)
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 9 个
                        // 会触发下面的 treeifyBin，也就是将链表转换为红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                         // 如果在该链表中找到了"相等"的 key(== 或 equals)
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;  // 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
                        p = e;
                    }
                }
                 // e!=null 说明存在旧值的key与要插入的key"相等"
            // 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)  //onlyIfAbsent为true的时候如果key存在则不替换存在的旧值 默认为false
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
             // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            re

总的来说，单就PUT而言 ，JAVA8对HashMap的调整在两个方面，一是当链表中的元素超过了 8 个以后，会将链表转换为红黑树

二是新的键值对会插入到链表尾部而不是头部。

参考[这是一个链接][Link 1]

[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220525/0917b794743d4756a3fcd96f6ebf4033.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MjM5NzMyMjAwMA==&mid=2651480660&idx=1&sn=eb44f0f242227ff45e584714f58dc103&chksm=bd250e2b8a52873d373aadb2041e05b61b1a5b6247758319d44a599b51b07a66b3d4eb2a608f&mpshare=1&scene=23&srcid=03140636z0ILjTm5isHfgT6T#rd