JAVA容器（一）HashMap（jdk1.8）

本文主要是介绍JAVA容器（一）HashMap（jdk1.8），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

HashMap位于java.util包下，实现Map接口。
键值对，每个键都唯一（插入重复键时，覆盖value值），只允许有一个空键。

结构：
数组+链表/红黑树，初始默认容量为16

基本元素：
size：hashmap中实际存在键值对的数量。
length：数组长度，必须为2的幂次方。
threshold：在此Load factor（负载因子，默认为0.75）和length对应下允许的最大元素数目，即与size相比较，size超过这个值就resize进行扩容。
modCount：用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。（内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。）

构造方法：

索引方法：
计算hash：key的hashCode值的高16位异或低16位
计算索引：hash值对数组长度length取模（&length-1）

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K, V>[] tab;   // 指向当前哈希数组
        Node<K, V> p;       // 指向待插入元素应当插入的位置
        ……
 // p指向hash所在的哈希槽（链）上的首个元素
        p = tab[i = (n - 1) & hash];
        ……
 }

同一哈希链/树下，key的hash值未必相同（对长度取模），key的hash值相同，hashcode也未必相同。

（图片来自美团技术团队https://tech.meituan.com/2016/06/24/java-hashmap.html）

对于(n - 1) & hash，n是数组长度，n是2的i次方，由上图可知，与n-1，索引结果就是hash值的低i位。

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;
        
        // 如果哈希数组还未初始化，或者容量无效，则需要初始化一个哈希数组
        if((tab = table) == null || (n = tab.length) == 0) {
            // 初始化哈希数组，或者对哈希数组扩容，返回新的哈希数组
            tab = resize();
            
            n = tab.length;
        }
        
        // p指向hash所在的哈希链/树上的首个元素
        p = tab[i = (n - 1) & hash];
        
        // 如果哈希槽为空，直接放置新节点存储键值对
        if(p == null) {
            tab[i] = newNode(hash, key, value, null);
            
            // 不为空，在后面链接更多的元素
        } else {
            Node<K, V> e;
            K k;
            
            /*
             * 对哈希槽中的首个元素进行判断
             *
             * 只有哈希值一致（还说明不了key是否一致），且key也相同（先判断key地址，不是同一个key再用equals()判断两个key是否值相同）时，
             * 这里才认定是存在同位元素（在HashMap中占据相同位置的元素）
             */
            if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                e = p;  //e指向哈希槽首个元素，覆盖value，具体对value值的覆盖在后面（修改e的value）
                
                // 如果是红黑树结点，调用红黑树的插入方法
            } else if(p instanceof TreeNode) {
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            } else {//当前是链表
                // 遍历（binCount统计的是插入新元素之前遍历过的元素数量）
                for(int binCount = 0; ; ++binCount) {
                    // 如果没有找到同位元素，则需要插入新元素
                    if((e = p.next) == null) {
                        // 插入一个普通结点
                        p.next = newNode(hash, key, value, null);
                        
                        // 插入结点后需进行判断，插入后有没有达到阈值（默认为8），若达到，即将链表转换为红黑树
                        if(binCount >= TREEIFY_THRESHOLD - 1) { // -1 for 1st
                            treeifyBin(tab, hash);
                        }
                        
                        break;
                    }
                    
                    /*
                     * 对哈希槽后面链接的其他元素进行判断
                     *
                     * 只有哈希值一致（还说明不了key是否一致），且key也相同（必要时需要用到equals()方法）时，
                     * 这里才认定是存在同位元素（在HashMap中占据相同位置的元素）
                     */
                    if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    
                    p = e;
                }
            }
            
            // 如果存在同位元素（在HashMap中占据相同位置的元素）
            if(e != null) { // existing mapping for key
                // 获取旧元素的值
                V oldValue = e.value;
                
                // 如果不需要维持原状（可以覆盖旧值），或者旧值为null
                if(!onlyIfAbsent || oldValue == null) {
                    // 更新旧值
                    e.value = value;
                }
                
                afterNodeAccess(e);
                
                // 返回覆盖前的旧值
                return oldValue;
            }
        }
        
        //不是覆盖情况，插入了新结点， HashMap的更改次数加一
        ++modCount;
        
        // 如果哈希数组的容量已超过阈值，则需要对哈希数组扩容
        if(++size>threshold) {
            // 初始化或扩容，返回新的哈希数组
            resize();
        }
        
        afterNodeInsertion(evict);
        
        // 插入新元素，返回null
        return null;
    }

**扩容**
如果是链表，将链表拆分

参考：
美团技术团队https://tech.meituan.com/2016/06/24/java-hashmap.html

这篇关于JAVA容器（一）HashMap（jdk1.8）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！