集合—Map接口实现类-HashMap

本次博客带领大家学习集合中的Map接口实现类-HashMap。

HashMap小结

1. Map接口的常用实现类：HashMap、Hashtable和Properties。

2. HashMap是Map接口使用频率最高的实现类。

3. HashMap 是以 key-val 对的方式来存储数据(HashMap$Node类型)。

4. key 不能重复，但是值可以重复，允许使用null键和null值。

5. 如果添加相同的key，则会覆盖原来的key-val，等同于修改。

6. 与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。(jdk8的hashMap 底层是数组+链表+红黑树)

7. HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized。

HashMap底层机制及源码分析

1. (k,v)是一个Node实现了Map.Entry，查看HashMap的源码可以看到。
2. jdk7.0的hashmap的底层实现[数组+链表]，jdk8.0底层[数组+链表+红黑树]。

扩容机制[和HashSet相同]

1. HashMap底层维护了Node类型的数组table,默认为null。
2. 当创建对象时，将加载因子(loadfactor)初始化为0.75。
3. 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key是否和准备加入的key是否相等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
4. 第1次添加，则需要扩容table容量为16，临界值(threshold)为12。
5. 以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍，即24，以此类推。
6. 在Java8中，如果一条链表的元素个数达到 TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)。

添加元素的源码分析

1.执行构造器 new HashMap()
  初始化加载因子 loadfactor =0.75
  HashMap$Node[] table = null
2.执行put 调用hash方法，计算key 的hash值  （h = key.hashCode()) ^ (h >>> 16）s
    public V put(K key, V value) { //K="java",value=10
        return putVal(hash(key), key, value, false, true);
    }
3.执行 putVal
    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 数组为null，或者 length=0 ，就扩容到16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //取出hash值对应的table表的索引位置的Node，如果为null，就直接把加入的k-v，
            //创建成一个Node，加入该位置即可。

            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;//辅助变量
                //如果table的索引位置的key的hash相同和新的key的hash值相同，
                //并 满足(table现有的节点的key和准备添加的key是同一个对象 || equals返回真)
                //就认为不能加入新的k-v
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按红黑树的方式加入
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //如果找到的节点，后面是链表，就循环比较
                    for (int binCount = 0; ; ++binCount) { //死循环
                        if ((e = p.next) == null) {//如果整个链表，没有和他相同，就加到该链表的最后
                            p.next = newNode(hash, key, value, null);
                            //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                            //就调用 treeifyBin 方法红黑树的转换
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash && //如果在循环比较过程中，发现有相同，就break，就只是替换
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;//替换，key对应value值
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount; //每增加一个Node，就size++
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

   5. 关于树化(转成红黑树)
   //如果 table 为null，或者大小还没有到 64，暂时不树化，而是进行扩容。
   //否则才会真正的树化 -> 简枝
   final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

扩容树化的触发

public class HashMapSource2 {
    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        for (int i = 1; i<=12;i++){
            hashMap.put(new A(i),"hello");
        }
        
        System.out.println("hashMap="+hashMap); //12个 k-v
    }
}

class A{
    private  int num;

    public A(int num) {
        this.num = num;
    }

    //所有的A对象的hashCode都是100
    @Override
    public int hashCode() {
        return 100;
    }

    @Override
    public String toString() {
        return "\nA{" +
                "num=" + num +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31