java集合：HashMap

太过爱你忘了你带给我的痛 2022-04-11 04:54 333阅读 0赞

# 1.HashMap #

*  HashMap的底层结构为**数组＋链表/红黑树**的形式，保存的数据为Node
 *  HashMap中保存的entry，Key唯一并可为null，Value不唯一并可以为null。

**问题思考：**

1.  HashMap的底层为数组+链表/红黑树，那如何定位一个数据在HashMap中位置？
2.  在定位位置，如果出现哈希碰撞，如何去处理？

# 2.源码解析 #

1.  成员变量

// 存储链表的数组
    	transient Node<K,V>[] table;
    	// 保存entrySet()方法的缓存
    	transient Set<Map.Entry<K,V>> entrySet;
    	// 键值对的个数
    	transient int size;
    	// HsahMap结构的修改次数，用于fail-fast机制
    	transient int modCount;
    	// 下一次resize的阈值大小 = HashMap容量 * 负载因子
    	int threshold;
    	//哈希表的负载因子
    	final float loadFactor;

**结点：** HashMap保存的数据类型

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;
            }
            ...
        }

1.  静态变量

// HashMap初始化容量的默认大小16
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    	// 最大容量：，传入容量过大将被这个值替换
    	static final int MAXIMUM_CAPACITY = 1 << 30;
    	// HashMap初始化时的默认负载因子
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
    	// 将链表转为红黑树的阈值，当一个元素在被添加时，如果链表中的元素个数已经达到8个，则将链表转为红黑树形式
    	static final int TREEIFY_THRESHOLD = 8;
    	// 将红黑树转为链表的阈值
    	static final int UNTREEIFY_THRESHOLD = 6;
    	// 链表被转化为红黑树时，哈希表最小的容量。为了避免冲突，该值至少为4 * TREEIFY_THRESHOLD
    	static final int MIN_TREEIFY_CAPACITY = 64;

1.  构造器

HashMap的构造器共有4个，HashMap构造的主要参数有两个：

*  初始容量：initialCapacity，默认初始化大小为16
 *  加载因子：loadFactor，默认为0.75，数据的有效存储空间 = 容量大小\*加载因子。

static final float DEFAULT_LOAD_FACTOR = 0.75f;
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16

//指定容量大小和加载因子的构造器
      public HashMap(int initialCapacity, float loadFactor) { 
      		//指定容量小于0，报错
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            //指定容量大于最大值，则容量为最大值
            //MAXIMUM_CAPACITY = 1 << 30,2的30次方 
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            //验证加载因子
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            //看下这里
            this.threshold = tableSizeFor(initialCapacity);
        }
        
        /** * Returns a power of two size for the given target capacity. */
        //作用：将cap的二进制序列从第一位1开始，后面的0都替换为1。
        //例如：27：0001 1011→0001 1111
        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;
        }
       //指定容量的构造器 
       public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
       //默认构造器
       public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
        }
       //参数为Map集合的构造 
       public HashMap(Map<? extends K, ? extends V> m) { 
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            //复制数据到HashMap
            putMapEntries(m, false);
        }

1.  添加方法

//添加entry(K,V)，并返回V
        public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }
        
        static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

继续看一下put操作

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //如果table为空或者长度为0，则通过resize来初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //(n - 1) & hash]将会存放的数组下标，若为空，则tab[i]新建复制
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
                Node<K,V> e; K k;
                //如果p节点的key与参数key相同，则e=p
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //如果p结果已经转化为TreeNode节点，则用putTreeVal方法来进行添加节点
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                //现在Key的hashcode相同，值不同而且还是以链表的形式存储
                //遍历链表在链表尾部添加节点
                    for (int binCount = 0; ; ++binCount) { 
                        if ((e = p.next) == null) { 
                            p.next = newNode(hash, key, value, null);
                 //如果添加节点后，达到了红黑树的阀值，则转化为红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                treeifyBin(tab, hash);
                            break;
                        }
                  //在遍历链表的过程中，碰到相同的Key，则停止寻找
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //在找到key相同时候，更新Key的Value值
                if (e != null) { 
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //修改次数加一
            ++modCount;
            //如果添加数据成功后大于加载因子*容量，则扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

现在来看一下扩容操作

//扩容操作
        final Node<K,V>[] resize() { 
        	
            Node<K,V>[] oldTab = table;
            //table为null，则容量为0否则为table的length
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            //如果table有容量
            if (oldCap > 0) { 
            	//若果大于最大容量，则赋值integer的最大值
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //2倍扩容后还小于最大容量且老的容量大于初始值，则阀值也扩容两倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; 
            }
            //如果阀值大于0，table的容量为0，则新容量等于旧阀值
            else if (oldThr > 0) 
                newCap = oldThr;
            else {     
            //如果阀值，容量都为0，容量赋值默认值，阀值赋值容量*加载因子 
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //如果新阀值为0
            if (newThr == 0) { 
            	//计算ft
                float ft = (float)newCap * loadFactor;
                //计算新阀值
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            //更新阀值
            threshold = newThr;
            @SuppressWarnings({ "rawtypes","unchecked"})
            //新建table
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            //更新table
            table = newTab;
            //如果旧table不为空，则copy table到新table
            if (oldTab != null) { 
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    //节点不为空
                    if ((e = oldTab[j]) != null) { 
                        oldTab[j] = null;
                        //只有一个节点
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        //如果为红黑树节点，则将节点重构到新table里
                        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;
                        //进行rehash，运用e.hash & oldCap为不为0分为两条链表
                        //为0的坐标不变，不为0的坐标变为j + oldCap
                            do { 
                                next = e.next;
                                if ((e.hash & oldCap) == 0) { 
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else { 
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

1.  get方法

//调用getNode返回节点，为null则返回null否则返回value
        public V get(Object key) { 
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

//传入hash值和Key
    final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            //table不为空，table的长度不为0，(n - 1) & hash的节点不为空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (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);
                }
            }
            return null;
        }

1.  remove方法

//调用removeNode方法
        public V remove(Object key) { 
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

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;
            //table不为空，table的长度不为0，(n - 1) & hash的节点不为空
            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;
                //和首节点的key相同
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) { 
                	//如果为红黑树
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else { 
                   	//为链表
                        do { 
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) { 
                                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;
        }

# 3.HashMap总结 #

*  HashMap的底层是**数组+链表/红黑树**的形式
 *  成员变量：容量，负载因子，实际可容量大小=负载因子\*容量，当达到实际可容量大小的时候，会进行2倍扩容
 *  默认初始化容量为16，负载因子为0.75

1.  确认数据在哈希桶中的位置

涉及方法：

//方法一
        static final int hash(Object key) { 
            int h;
            //1.获取key的hashCode()
            //2.将h的高16加入运算，与h的低16进行或与运算
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
       //方法二 
       //将上面方法的hash值与数组length-1进行与操作 
        n = tab.length;
       (n - 1) & hash]

[解释说明直通车][Link 1]

1.  put方法的运行过程  
    盗个图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70]

[Link 1]: https://www.cnblogs.com/yuexiaoyun/p/12158914.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70]: /images/20220411/c888adf6eb174431906a7e640662fe09.png