Java集合类详解三HashMap

Java集合类详解三HashMap

1.什么是HashMap

HashMap实现了Map接口，是一个用于存储键值对（key-value）的集合，每一个键值也叫做Entry，这些键值对分散存储在一个数组中，这个数组就是HashMap的主干，Jdk1.8后由数组+链表变为数组+链表+红黑树。

2.方法特性

2.1初始容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2.2最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

2.3默认加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

2.4链表转换为树的阙值

static final int TREEIFY_THRESHOLD = 8;

2.5树转化成链表的阙值

static final int UNTREEIFY_THRESHOLD = 6;

2.6键值对数量大于64才会发生转换

static final int MIN_TREEIFY_CAPACITY = 64;

2.7hash方法

//计算对应的位置，key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。
（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值
 高16位不变，这样做能减小hash冲突
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

举例：hashcode：十进制的3029737，二进制的101110001110101110 1001。

​ 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111

​ 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

为什么长度16：反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

2.8put方法

public V put(K key, V value) {
		//对key的hashCode做hash
        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;
        //判断是否为null或长度是否为0，否则需要初始化数组
        if ((tab = table) == null || (n = tab.length) == 0)
        	//得到数组长度16
            n = (tab = resize()).length;
        //如果通过hash值计算除的下标地方没元素，则根据key，value创建一个
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        	//如果hash冲突了
            Node<K,V> e; K k;
            //如果给定的hash和冲突下标中的hash值相等说明该key和已有的key相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //那么就在将存在的值赋值给上面的e
                e = p;
            //如果已存在的值是树类型的，则将给定的键值对和该值关联
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //如果key不相同，只是hash冲突，并且不是树，则是链表
            else {
            	//循环，知道某个链表中的某个结点为null，或者某个结点hash值和给定的hash值一致且key也相同，则停止循环
                for (int binCount = 0; ; ++binCount) {
                	//如果next熟悉是空
                    if ((e = p.next) == null) {
                    	//那么创建新的结点赋值给已有的next属性
                        p.next = newNode(hash, key, value, null);
                        // 如果树的阀值大于等于7，也就是，链表长度达到了8（从0开始）。
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	  // 如果链表长度达到了8，且数组长度小于64，那么就重新散列，如果大于64，则创建红黑树
                            treeifyBin(tab, hash);
                        //结束循环
                        break;
                    }
                    // 如果hash值和next的hash值相同且（key也相同）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 结束循环
                        break;
                     // 如果给定的hash值不同或者key不同。
                    // 将next 值赋给 p，为下次循环做铺垫
                    p = e;
                }
            }
            // 通过上面的逻辑，如果e不是null，表示：该元素存在了(也就是他们呢key相等)
            if (e != null) { // existing mapping for key
            	// 取出该元素的值
                V oldValue = e.value;
                // 如果 onlyIfAbsent 是 true，就不要改变已有的值，这里我们是false。
                // 如果是false，或者 value 是null
                if (!onlyIfAbsent || oldValue == null)
                	// 将新的值替换老的值
                    e.value = value;
                // HashMap 中什么都不做
                afterNodeAccess(e);
                // 返回之前的旧值
                return oldValue;
            }
        }
        // 如果e== null，需要增加 modeCount 变量，为迭代器服务
        ++modCount;
        // 如果数组长度大于了阀值
        if (++size > threshold)
        	// 重新散列
            resize();
        // HashMap 中什么都不做
        afterNodeInsertion(evict);
        // 返回null
        return null;
    }

步骤

1.判断数组是否为空，如果是空，则创建默认长度位 16 的数组。
2.通过与运算计算对应 hash 值的下标，如果对应下标的位置没有元素，则直接创建一个。
3.如果有元素，说明 hash 冲突了，则再次进行 3 种判断。
1.判断两个冲突的key是否相等，equals 方法的价值在这里体现了。如果相等，则将已经存在的值赋给变量e。最后更新e的value，也就是替换操作。
2.如果key不相等，则判断是否是红黑树类型，如果是红黑树，则交给红黑树追加此元素。
3.如果key既不相等，也不是红黑树，则是链表，那么就遍历链表中的每一个key和给定的key是否相等。如果，链表的长度大于等于8了，则将链表改为红黑树，这是Java8 的一个新的优化。
4.最后，如果这三个判断返回的 e 不为null，则说明key重复，则更新key对应的value的值。
5.对维护着迭代器的modCount 变量加一。

最后判断，如果当前数组的长度已经大于阙值了，则重新hash。

2.9get方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    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;
    }
    //还是先根据key获取hash值，其他没什么可说的，有值value，没有值返回null

3.扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果老的容量大于0
    if (oldCap > 0) {
        // 如果容量大于容器最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阀值设为int最大值
            threshold = Integer.MAX_VALUE;
            // 返回老的数组，不再扩充
            return oldTab;
        }// 如果老的容量*2 小于最大容量并且老的容量大于等于默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新的阀值也再老的阀值基础上*2
            newThr = oldThr << 1; // double threshold
    }// 如果老的阀值大于0
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量等于老阀值
        newCap = oldThr;
    else {  // 如果容量是0，阀值也是0，认为这是一个新的数组，使用默认的容量16和默认的阀值12           
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的阀值是0，重新计算阀值
    if (newThr == 0) {
        // 使用新的容量 * 负载因子（0.75）
        float ft = (float)newCap * loadFactor;
        // 如果新的容量小于最大容量 且 阀值小于最大 则新阀值等于刚刚计算的阀值，否则新阀值为 int 最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    } 
    // 将新阀值赋值给当前对象的阀值。
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        // 创建一个Node 数组，容量是新数组的容量（新容量要么是老的容量，要么是老容量*2，要么是16）
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 将新数组赋值给当前对象的数组属性
    table = newTab;
    // 如果老的数组不是null
    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;
                // 如果该节点是树
                else if (e instanceof TreeNode)
                    // 调用红黑树 的split 方法，传入当前对象，新数组，当前下标，老数组的容量，目的是将树的数据重新散列到数组中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 如果既不是树，next 节点也不为空，则是链表，注意，这里将优化链表重新散列（java 8 的改进）
                  // Java8 之前，这里曾是并发操作会出现环状链表的情况，但是Java8 优化了算法。此bug不再出现，但并发时仍然不建议HashMap
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 这里的判断需要引出一些东西：oldCap 假如是16，那么二进制为 10000，扩容变成 100000，也就是32.
                        // 当旧的hash值 与运算 10000，结果是0的话，那么hash值的右起第五位肯定也是0，那么该于元素的下标位置也就不变。
                        if ((e.hash & oldCap) == 0) {
                            // 第一次进来时给链头赋值
                            if (loTail == null)
                                loHead = e;
                            else
                                // 给链尾赋值
                                loTail.next = e;
                            // 重置该变量
                            loTail = e;
                        }
                        // 如果不是0，那么就是1，也就是说，如果原始容量是16，那么该元素新的下标就是：原下标 + 16（10000b）
                        else {
                            // 同上
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 理想情况下，可将原有的链表拆成2组，提高查询性能。
                    if (loTail != null) {
                        // 销毁实例，等待GC回收
                        loTail.next = null;
                        // 置入bucket中
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1.判断容量是否大于0，如果大于0，并且容量已将大于最大值，则设置阀值为 int 最大值，并返回，如果老的容量乘以 2 小于最大容量，且老的容量大于等于16，则更新阀值。也就是乘以2.
2.如果老的阀值大于0，则新的容量等于老的阀值。注意：这里很重要。还记的我们之前使用new 操作符的时候，会设置阀值为 2 的幂次方，那么这里就用上了那个计算出来的数字，也就是说，就算我们设置的不是2的幂次方，HashMap 也会自动将你的容量设置为2的幂次方。
3.如果老的阀值和容量都不大于0，则认为是一个新的数组，默认初始容量为16，阀值为 16 * 0.75f，也就是 12。
4.如果，新的阀值还是0，那么就使用我们刚刚设置的容量（HashMap 帮我们算的），通过乘以 0.75，得到一个阀值，然后判断算出的阀值是否合法：如果容量小于最大容量并且阀值小于最大容量，那么则使用该阀值，否则使用 int 最大值。
5.将刚刚的阀值设置打当前Map实例的阀值属性中。
6.将刚刚的数组设置到当前Map实例的数组属性中。

7.如果老的数组不是null，则将老数组中的值重新 散列到新数组中，如果是null，直接返回新数组

4.遍历方法

4.1采用keySet()+for循环

Map<String,String> map=new HashMap<String,String>();  
map.put("key1","value1"); 
map.put("key2","value2");  
map.put("key3","value3");  
for(String key:map.keySet())
{       
system.out.println("key:"+key);        
system.out.println("value:"+map.get(key));  
}

4.2采用EntrySet()+Iterator进行遍历

Iterator< Map.Entry<String,String>> 
it=map.EntrySet().iterator(); 
while(it.hasNext())
{       
Map.Entry<String,String> 
entry=it.next();       
system.out.println("key:"+entry.getKey());       system.out.println("value:"+entry.getValue()); 
}

4.3直接采用EntrySet+for增强进行遍历

for(Map.Entry<String,String> 
entry:map.entrySet())
{            
system.out.println("key:"+entry.getKey());       system.out.println("value:"+entry.getValue());  
}

4.4取出所有value的值，但是不能取出KEY值

for(String value:map.values())
{  
<pre name="code" class="html">     
system.out.println("value:"+value);  
}

5.总结

• 底层实现是 链表数组，JDK 8 后又加了 红黑树

• 实现了 Map 全部的方法

• key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类（一般是String）需要重写 hashCode 和 equals 方法

• 允许空键和空值（但空键只有一个，且放在第一位，知道就行）

• 元素是无序的，而且顺序会不定时改变每次扩容后，都会重新哈希，也就是key通过哈希函数计算后会得出与之前不同的哈希值，这就导致哈希表里的元素是没有顺序，会随时变化的，这是因为哈希函数与桶数组容量有关，每次结点到了临界值后，就会自动扩容，扩容后桶数组容量都会乘二，而key不变，那么哈希值一定会变

• 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置

• 遍历整个 Map 需要的时间与数组的长度成正比（因此初始化时 HashMap 的容量不宜太大）

• 两个关键因子：初始容量、加载因子

• HashMap不是同步，HashTable是同步的，但HashTable已经弃用，如果需要线程安全，可以用

参考链接：https://blog.csdn.net/qq_36711757/article/details/80394272

​ https://blog.csdn.net/qq_38182963/article/details/78942764