开发者

关于HashMap源码解读

目录
  • 一、概述
    • JDK1.7和JDK1.8的区别
  • 二、HashMap的数据结构
    • 三、迭代方式
      • 四、源码分析
        • 1、HashMap继承关系
        • 2、成员变量
        • 3、构造方法
          • ①HashMap()
          • ②HashMap(int initialCapacity)
          • ③HashMap(int initialCapacity, float loadFactor)
          • ④HashMap(Map<? extends K, ? extends V> m)
        • 4、成员方法
          • ①Node类
          • ②TreeNode类(Java新加的)
          • ③Hash方法
          • ④Get方法
          • ⑤Put方法
          • ⑥Resize方法
          • ⑦Remove方法
      • 五、扩展
        • 源码符号(位运算符)的解释
          • >>> 和 >> 的区别
          • ^ 和 & 的区别
      • 总结

        一、概述

        • HashMap 是基于哈希表实现的,每一个元素是一个 key-value 对,其内部通过单链表解决冲突问题,容量不足(超过了阈值)时,同样会自动增长。
        • HashMap 是非线程安全的,只是适用于单线程环境,多线程环境可以采用并发包下的concurrentHashMap
        • HashMap 实现了Serializable接口,支持序列化,实现了Cloneable接口,能被克隆
        • HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
        • Java8中又对此类底层实现进行了优化,比如引入了红黑树的结构以解决哈希碰撞

        JDK1.7和JDK1.8的区别

        比较HashMap1.7HashMap1.8
        数据结构数组+链表数组+链表+红黑树
        节点Entry(hash是可变的,因为有rehash的操作)Node TreeNode(为了转换红黑树、hash是final修饰,也就是说hash值一旦确定,就不会再重新计算hash值了)
        Hash算法较为复杂异或Hash右移16位
        对Null的处理单独写一个putForNull()方法处理作为以一个Hash值为0的普通节点处理
        初始化赋值给一个空数值,put时初始化没有赋值,懒加载,put时初始化
        扩容插入前扩容插入后,初始化,树化时扩容
        节点插入头插法尾插法

        什么是懒加载?

        • 即延迟加载(Lazyload)。
        • 简单的说就是只有当我们去调用到它时才会去做加载。

        二、HashMap的数据结构

        HashMap 底层采用数组+链表+红黑树的数据结构实现。

        数组是 HashMap 的主体,用于存储键值对;链表用于解决哈希冲突;红黑树是在链表长度超过一定阈值(默认为8)时,将链表转换为红黑树,以提高查找效率。

        关于HashMap源码解读

        三、迭代方式

        HashMap的迭代种类

        • 分别遍历Key和Value
        • 使用Iterator迭代器迭代
        • 通过get的方式(不建议使用)
        • Map接口中的默认方法(映射方式)JDK1.8
        public class HashMapExam {
            public static void main(String[] args) {
        
                Map<Integer, String> map = new HashMap<>();
                for (int i = 0; i < 15; i++) {
                    map.put(i, new String(new char[]{(char) ('A'+ i)}));
                }
        
        
                System.out.println("======Key和Value=======");
                for (Integer key:map.keySet()) {
                    System.out.println(key);
                }
                for (String value:map.values()) {
                    System.out.println(value);
                }
        
                System.out.println("======Iterator迭代器=======");
                Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
                while (iterator.hasNext()) {
                    Map.Entry<Integer, String> mapEntry = iterator.next();
                    System.out.println(mapEntry.getKey()+ "====" + mapEntry.getValue());
                }
        
                System.out.println("======Get的方式=======");
                Set<Integer> keySet = map.keySet();
                for (Integer key : keySet) {
                    System.out.println(key + "====" + map.get(key));
                }
                
                System.out.println("======forEach=======");
                map.forEach((key,value) -> System.out.println(key+ "----" + value));
            }
        }

        四、源码分析

        1、HashMap继承关系

        • Cloneable 空接口:表示可以克隆。创建并返回HashMap对象的一个副本;
        • Serializable 序列化接口:属于标记性接口。HashMap 对象可以倍序列化和反序列化。
        • AbstractMap:父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

        HashMap 继承关系如下图所示:

        关于HashMap源码解读

        补充:通过上述继承关系我们发现一个很奇怪的现象, 就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口,那为什么HashMap还要在实现Map接口呢?同样在ArrayList中LinkedList中都是这种结构。

        据 java 集合框架的创始人Josh Bloch描述,这样的写法是一个失误。在java集合框架中,类似这样的写法很多,最开始写java集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。

        2、成员变量

        // 序列化版本号
        private static final long serialVersionUID = 362498820763181265L;
        
        // 默认的初始容量是16 --> 1<<4 相当于 1*2的4次方也就是16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
        
        // 最大容量(传入容量过大将被这个替换)
        static final int MAXIMUM_CAPACITY = 1 << 30;
        
        // 默认加载因子为0.75,通过这个来算出临界值
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        
        // 当桶(bucket)上的结点数大于这个值时会转换成红黑树
        static final int TREEIFY_THRESHOLD = 8;
        
        // 当桶(bucket)上的结点数小于这个值时树转链表
        static final int UNTREEIFY_THRESHOLD = 6;
        
        // 桶中结构转化为红黑树对应的数组长度最小的值 
        static final int MIN_TREEIFY_CAPACITY = 64;
        
        //存储元素的数组 
        transient Node<K,V>[] table;
        
        //存放具体元素的集合
        transient Set<Map.Entry<K,V>> entrySet;
        
        //存放元素的个数,注意这个不等于数组的长度。
         transient int size;
        
        // 每次扩容和更改map结构的计数器
         transient int modCount;  
        
        // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
        int threshold;
        
        // 负载因子实际大小
        final float loadFactor;

        3、构造方法

        ①HashMap()

        public HashMap() {
           this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的加载因子0.75赋值给loadFactor,并没有创建数组
        }

        ②HashMap(int initialCapacity)

        // 指定“容量大小”的构造函数
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

        ③HashMap(int initialCapacity, float loadFactor)

        public HashMap(int initialCapacity, float loadFactor) {
            //判断初始化容量initialCapacity是否小于0
            if (initialCapacity < 0)
                //如果小于0,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                    initialCapacity);
            //判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
            if (initialCapacity > MAXIMUM_CAPACITY)
                //如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
            //判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                //如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " +
                                                    loadFactor);
             //将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;
            /*
            	tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂,如果不是那么会变为比指			定初始化容量大的最小的2的n次幂。这点上述已经讲解过。
            	但是www.devze.com注意,在tableSizeFor方法体内部将计算后的数据返回给调用这里了,并且直接赋值给threshold边			界值了。有些人会觉得这里是一个bug,应该这样书写:
            	this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
            	这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)。
        		但是,请注意,在jdk8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推			 迟到了put方法中,在put方法中会对threshold重新计算,put方法的具体实现我们下面会进行讲解
            */
            this.threshold = tableSizeFor(initialCapacity);
        }
        最后调用了tableSizeFor,来看一下方法实现:
        /**
         * Returns a power of two size for the given target capacity.
           返回比指定初始化容量大的最小的2的n次幂
         */
        static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

        ④HashMap(Map<? extends K, ? extends V> m)

        //构造一个映射关系与指定 Map 相同的新 HashMap。
        public HashMap(Map<? extends K, ? extends V> m) {
            //负载因子loadFactor变为默认的负载因子0.75
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
        // 最后调用了putMapEntries,来看一下方法实现:
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
            //获取参数集合的长度
            int s = m.size();
            if (s > 0)
            {
                //判断参数集合的长度是否大于0,说明大于0
                if (table == null)  // 判断table是否已经初始化
                { // pre-size
                        // 未初始化,s为m的实际元素个数
                        float ft = ((float)s / loadFactor) + 1.0F;
                        int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                                (int)ft : MAXIMUM_CAPACITY);
                        // 计算得到的t大于阈值,则初始化阈值
                        if (t > threshold)
                            threshold = tableSizeFor(t);
                }
                // 已初始化,并且m元素个数大于阈值,进行扩容处理
                else if (s > threshold)
                    resize();
                // 将m中的所有元素添加至HashMap中
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }

        4、成员方法

        ①Node类

        Node 类是 HashMap 中的静态内部类,实现Map·Entry 接口,定义了 key 键、value 值、next 节点,也就是说元素之间构成单向链表。

        static class Node<K,V> implements Map.Entry<K,V> {
            
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
        
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
        
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
        
                
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
        
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
        
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

        ②TreeNode类(Java新加的)

        红黑树结构包含前、后、左、右节点,以及标志是否为红黑树的字段

        static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
            TreeNode<K,V> parent;  
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;   
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
        
            final TreeNode<K,V> root() {
                for (TreeNode<K,V> r = this, p;;) {
                    if ((p = r.parent) == null)
                        return r;
                    r = p;
                }
            }
        
            static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
                ....
            }
        
            final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
                ....
            }
        
            final TreeNode<K,V> getTreeNode(int h, Object k) {
                return ((parent != null) ? root() : this).find(h, k, null);
            }
        
            static int tieBreakOrder(Object a, Object b) {
                ....
            }
        
            final void treeify(Node<K,V>[] tab) {
                ....
            }
        
            final Node<K,V> untreeify(HashMap<K,V> map) {
                ....
            }
        
            final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                               int h, K k, V v) {
                ....
            }
        
            final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                          boolean movable) {
                ....
            }
        
            final void swww.devze.complit(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
                ....
            }
        
            static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                                      TreeNode<K,V> p) {
                ....
            }
        
            static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                                       TreeNode<K,V> p) {
                ....
            }
        
            static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                            TreeNode<K,V> x) {
                ....
            }
        
            static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                           TreeNode<K,V> x) {
                ....
            }
        
            static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
                ....
            }
        }

        ③Hash方法

        在JDK1.8及之后对Hash算法进行了改良,使用较为复杂 异或Hash右移16位。

        static final int hash(Object key) {
            int h;
            // (h = key.hashCode()) ^ (h >>> 16):异或Hash右移16位算法
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

        ④Get方法

        下面是JDK1.8中HashMap的Get方法的简要实现过程:

        1. 首先,需要计算键的哈希值,并通过哈希值计算出在数组中的索引位置。
        2. 如果该位置上的元素为空,说明没有找到对应的键值对,直接返回null。
        3. 如果该位置上的元素不为空,遍历该位置上的元素,如果找到了与当前键相等的键值对,那么返回该键值对的值,否则返回null。
        public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

        get方法看起来很简单,就是通过同样的 hash 得到 key 的 hash 值。重点看下 getNode 方法:

        final Node<K,V> getNode(int hash, Object key) {
            // 当前 HashMap 的散列表的引用
            Node<K,V>[] tab; 
            // first:桶头元素
            // e:用于存储临时元素
            Node<K,V> first, e;
            // n:table 数组的长度
            int n; 
            // 元素中的 k
            K k;
            // 将 table 赋值给 tab,不等于 null 说明有数据,(n = table.length)> 0 同理说明 table 中有值
            if ((tab = table) != null && (n = tab.length) > 0 &&
                // 同时将 该位置的元素赋值为 first
                (first = tab[(n - 1) & hash]) != null) {
                // 定位到了桶的到的位置就是想要获取的 key 对应的,直接返回该元素
                if (first.hash == hash && 
                    ((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);
                }
            }
            // 遍历不到返回null
            return null;
        }

        ⑤Put方法

        下面是 JDK 1.8 中 HashMap 的 put 方法的简要实现过程:

        1. 首先,put 方法会计算键的哈希值(通过调用 hash 方法),并通过哈希值计算出在数组中的索引的位置。
        2. 如果该位置上的元素为空,那么直接将键值对存储在该位置上。
        3. 如果该位置上的元素不为空,那么遍历该位置上的元素,如果找到了与当前键相等的键值对,那么将该键值对的值更新为当前值,并返回旧值。
        4. 如果该位置上的元素不为空,但没有与当前键相等的键值对,那么将键值对插入到链表或红黑树中(如果该位置上的元素数量超过一个阈值,就会将链表转化为红黑树来提高效率)。
        5. 如果插入成功,返回被替换的值;如果插入失败,返回null。
        6. 插入成功后,如果需要扩容,那么就进行一次扩容操作。
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }

        核心其实是通过putValue方法实现的,在传给putValue的参数中,先调用hash获取了一个hashCode。

        putValue 方法主要实现如下,给大家增加了注释:

        /**
             * Implements Map.put and related methods.
             *
             * @param hash		key 的 hash 值
             * @param key 		key 值
             * @param value 	value 值
             * @param onlyIfAbsent true:如果某个 key 已经存在那么就不插了;false 存在则替换,没有则新增。这里为 false
             * @param evict 	不用管理。我也不认识
             * @return previous value, or null if none
             */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                           boolean evict) {
            // tab 表示当前 hash 散列表的引用
            Node<K,V>[] tab; 
            // 表示具体的散列表中的元素
            Node<K,V> p; 
            // n:表示散列表数组的长度
            // i:表示路由寻址的结果
            int n, i;
            // 将 table 赋值发给 tab,如果 tab == null,说明 table 还没有被初始化。则此时是需要去创建 table 的
            // 为什么这个时候才去创建散列表,因为可能创建了 HashMap 时候可能并没有存放数据,如果在初始化 HashMap 的时候创建散列表,势必会造成空间的浪费
            // 这里也就是延迟初始化的逻辑
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            // 如果 p == null,说明寻址到的桶没有元素。那么就将 key-value 封装到 Node 中,并放到寻址到的下标为 i 的位置
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            // 到这里说明 该位置已经有数据了,且此时可能是链表结构,也可能是树结构
            else {
                // e 表示找到了一个与当前要插入的 key-value 一致的元素
                Node<K,V> e; 
                // 临时的 key
                K k;
                // p 的值就是上一步 if 中的结果即:此时的(p = tab[i = (n - 1) & hash])不等于 null
                // p 是原来的已经在 i 的位置的元素,且新插入的 key 是等于 p 中的 key
                // 说明找到了和当前需要插入的元素相同的元素(其实就是需要替换而且)
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // 将 p 的值赋值给 e
                    e = p;
                // 说明已经树化,红黑树会有单独的文章介绍,本文不再阐述
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V&ghttp://www.devze.comt;)p).putTreeVal(this, tab, hash, key, v编程客栈alue);
                else {
                    // 如果 p.next == null 说明 p 是最后一个元素,说明,该元素在链表中也没有重复的
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            // 直接将 key-value 封装到 Node 中并且添加到 p 的后面
                            p.next = newNode(hash, key, value, null);
                            // 当元素已经是 7 了,再来一个就是 8 个了,那么就需要进行树化
                            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;
                        // 将e(即p.next)赋值给e,这就是为了继续遍历链表的下一个元素(没啥好说的)下面的有张图帮助大家理解
                        p = e;
                    }
                }
                // 如果条件成立,说明找到了需要替换的数据
                if (e != null) {
                    // 这里不就是使用新的值赋值为旧的值嘛
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    // 这个方法没用,里面啥都没有
                    afterNodeAccess(e);
                    // HashMap put 方法的返回值是原来位置的元素值
                    return oldValue;
                }
            }
            // 上面说过,对于散列表 结构修改次数,那么就修改 modCount 的次数
            ++modCount;
            // size 即散列表中的元素个数,添加后需要自增,如果自增后的值大于扩容的阈值,那么就触发扩容操作
            if (++size > threshold)
                resize();
            // 啥也没干
            afterNodeInsertion(evict);
            // 原来位置没有值,那么就返回 null 呗
            return null;
        }

        ⑥Resize方法

        什么情况下会扩容(扩原来的2倍):

        • 容器初始化的时候
        • 元素个数大于临界值的时候
        • 桶中的个数大于8时,并且数量小于64时

          HashMap的扩容是什么:

        • 首先会新建一个比原来大于2倍的哈希表
        • 遍历旧哈希表的每个桶,重新计算桶的元素的新位置(rehash方式)
          • 如果高位新增1,则 原位置+旧容器
          • 如果高位没有新增1,则 原位置
        • 将计算出新位置的元素放进新哈希表中,
        • 并且将旧哈希表中对应的元素设置为null,方便后面GC回收

        关于HashMap源码解读

        final Node<K,V>[] resize() {
            //得到当前数组
            Node<K,V>[] oldTab = table;
            //如果当前数组等于null长度返回0,否则返回当前数组的长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //当前阀值点 默认是12(16*0.75)
            int oldThr = threshold;
            int newCap, newThr = 0;
            //如果老的数组长度大于0
            //开始计算扩容后的大小
            if (oldCap > 0) {
                // 超过最大值就不再扩充了,就只好随你碰撞去吧
                if (oldCap >= MAXIMUM_CAPACITY) {
                    //修改阈值为int的最大值
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                /*
                	没超过最大值,就扩充为原来的2倍
                	1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量
                	2)oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16
                */
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //阈值扩大一倍
                    newThr = oldThr << 1; // double threshold
            }
            //老阈值点大于0 直接赋值
            else if (oldThr > 0) // 老阈值赋值给新的数组长度
                newCap = oldThr;
            else {// 直接使用默认值
                newCap = DEFAULT_INITIAL_CAPACITY;//16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            // 计算新的resize最大上限
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            //新的阀值 默认原来是12 乘以2之后变为24
            threshold = newThr;
            //创建新的哈希表
            @SuppressWarnings({"rawtypes","unchecked"})
            //newCap是新的数组长度--》32
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            //判断旧数组是否等于空
            if (oldTab != null) {
                // 把每个bucket都移动到新的buckets中
                //遍历旧的哈希表的每个桶,重新计算桶里元素的新位置
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        //原来的数据赋值为null 便于GC回收
                        oldTab[j] = null;
                        //判断数组是否有下一个引用
                        if (e.next == null)
                            //没有下一个引用,说明不是链表,当前桶上只有一个键值对,直接插入
                            newTab[e.hash & (newCap - 1)] = e;
                        //判断是否是红黑树
                        else if (e instanceof TreeNode)
                            //说明是红黑树来处理冲突的,则调用相关方法把树分开
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // 采用链表处理冲突
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            //通过上述讲解的原理来计算节点的新位置
                            do {
                                // 原索引
                                next = e.next;
                             	//这里来判断如果等于true e这个节点在resize之后不需要移动位置
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                // 原索引+oldCap
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            // 原索引放到bucket里
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            // 原索引+oldCap放到bucket里
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        } 

        流程图:

        关于HashMap源码解读

        ⑦Remove方法

        final Node<K,V> removeNode(int hash, Object key, Object value,
                                       boolean matchValue, boolean movable) {
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // index 元素只有一个元素
                    node = p;
                else if ((e = p.next) != null) {
                    if (p instanceof TreeNode)
                        // index处是一个红黑树
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else {
                        // index处是一个链表,遍历链表返回node
                        do {
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                    (key != null && key.equals(k)))) {
                    ZeZsqqjsiI            node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                // 分不同情形删除节点
                if (node != null && (!matchValue || (v = node.value) == value ||
                                        (value != null && value.equals(v)))) {
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

        五、扩展

        源码符号(位运算符)的解释

        >>> 和 >> 的区别

        无符号右移运算符。它将操作数的二进制表示向右移动指定的位数。

        • >>>:它在右移时,无论正数还负数,高位都补 0。
        • >>:它在右移时,正数高位补 0,负数高位都补 1。

        例子如下:

        n = n >>> 2;
        // 假设n等于-15
        00000000 00000000 00000000 00001111  // 15
        0000000000 00000000 00000000 00001111  //15的二进制从高位右移2位
        -------------------------------------------------
        00000000 00000000 00000000 00000011 //15右移之后3
        
        n = n >> 2;
        // 假设n等于-15
        00000000 00000000 00000000 00001111  // -15
        11000000 00000000 00000000 0000001111  //-15的二进制从高位右移2位
        -------------------------------------------------
        11000000 00000000 00000000 00000011 //-15右移之后3

        ^ 和 & 的区别

        • ^(按位与运算):运算规则:相同的二进制数位上,都是1的时候,结果为 1,否则为 0。
        • &(按位异或运算):运算规则:相同的二进制数位上,数字相同,结果为 0,不同为 1。

        例子如下:

        n = i^j
        // 假设i等于10,j 等于15
        00000000 00000000 00000000 00001000  // i=10
        00000000 00000000 00000000 00001100  // j=15
        ------------------------------------------------- 
        00000000 00000000 00000000 00001000  // n=10
        
        n = i&j
        // 假设i等于10,j 等于15
        00000000 00000000 00000000 00001000  // i=10
        00000000 00000000 00000000 00001100  // j=15
        -------------------------------------------------
        00000000 00000000 00000000 00000100  // n=5

        总结

        以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程客栈(www.devze.com)。

        0

        上一篇:

        下一篇:

        精彩评论

        暂无评论...
        验证码 换一张
        取 消

        最新开发

        开发排行榜