HashMap

数组+链表 （jdk7及之前)

数组+链表+红黑树 （jdk 8)

JDK7

实现原理

1
2
3
4
HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");
  • 新建一个 HashMap，默认大小为 16；
  • 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。
  • 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。
  • 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，在用equals比较是否相同
    • 不相同，插在 <K2,V2> 前面。
    • 相同，用key,value替换。

应该注意到链表的插入是以头插法方式进行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在链表头部。

查找需要分成两步进行：

  • 计算键值对所在的桶；
  • 在链表上顺序查找，时间复杂度显然和链表的长度成正比

hash函数

移位运算

1
2
3
4
5
>>：带符号右移。正数右移高位补0，负数右移高位补1
>>>：无符号右移。无论是正数还是负数，高位通通补0。

以下代码可以判断两个数的符号是否相等
return ((a >> 31) ^ (b >> 31)) == 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

存储结构

1
Entry<K,V>存储

构造器

参数

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
 // 序列号
private static final long serialVersionUID = 362498820763181265L;    
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; 
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8; 
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table; 
// 存放具体元素的集 ，键值对缓存，如果外部操作导致key改变，还是可以通过这个找到映射关系
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;   
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 加载因子
final float loadFactor;

  • loadFactor加载因子

    loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。

    loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

    给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

  • threshold

    threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

空参构造器

1
2
3
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

带参构造器

1
2
3
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}

put 操作

1
2
3
4
5
6
7
8
9
10
简单来说：
	判断数组是否为空，空数组进行初始
	key为null，处理null值，程序结束
	计算hash值
	根据hash值定位要插入的位置
	循环遍历这个位置，判断是否存在hash相同 key也相同的元素存在，
		存在，把value替换返回旧的value,程序结束，
		不存在,则一直遍历到尾部。	O（n）的时间复杂度
	modCount++ 修改值加1
	头插法插入这个位置
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
//put方法是有返回值的，返回的的是：如果key相同覆盖的是之前key的value
public V put(K key, V value) {
    //判读数组是不是为空的，初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //key为null，hashmap可以为null
    if (key == null)
        return putForNullKey(value);
    //计算出hash
    int hash = hash(key);
    //根据hash和数组长度 计算出数组下标
    int i = indexFor(hash, table.length);
	//循环 从这个数组位置的链表头结点开始 ，直到他不为null
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //判断，这个hash相等或key值相等
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value; //获取
            e.value = value; //赋值新值
            e.recordAccess(this);  //这个方法在linkedHashMap实现
            return oldValue;//结束
        }
    }
	
    modCount++;
    //添加
    addEntry(hash, key, value, i);
    return null;
}

头插法效率不一定高。并且会导致一系列问题。

JDK8改为尾插法。

初始化
1
2
3
4
5
6
7
8
9
10
//初始化，为什么一定要一个2的幂次方数
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize 找到一个大于等于toSize的2的幂次方数
    int capacity = roundUpToPowerOf2(toSize);
	
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //初始化数组
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

为什么一定要一个2的幂次方数？

为了方便后面判断数组中存放位置进行&运行，效率更高。

找2幂次方数
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
10-16
6-16
1---0000 0001
2---0000 0010
4---0000 0100
返回二进制，判断是不是只有一位是1
Integer.highestOneBit(i)
    public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }
	假设这个数字
       	 	001* ****
        >>1	0001 ****
		|	0011 ****
        >>2 0000 11**
        |	0011 11**
        最终将最高位之后的数字变成1 在移位相减
        	0011 1111
        -	0001 1111 
这个函数调用。使用的第一感觉就是这个函数是干什么用的，通过查看文档得知，这个函数的作用是取 i 这个数的二进制形式最左边的最高一位且高位后面全部补零，最后返回int型的结果。找到小于等于的幂次方数
	10 - 8
	16 - 16
	6  - 4	
如果这个值为 0 返回1；
如果这个值不为0
        则判断他1的位数，只有1位，就直接返回这个数。
        多余一位就对rounded 左移，得到他2倍的数。
1
2
3
4
5
6
7
8
9
10
11
//找到一个大于等于toSize的2的幂次方数
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    int rounded = number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (rounded = Integer.highestOneBit(number)) != 0
            ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
            : 1;

    return rounded;
}
如果key为null

null值固定是存在第0个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private V putForNullKey(V value) {
    //遍历第0个位置
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    /*写死  hash 0
    	   	key null
    	   	value value 
    	   	位置 0
    */
    addEntry(0, null, value, 0);
    return null;
}
找到在数组中的位置

要平均。这个使用的是&操作，两个都为1，才是1，这个的效率比除法高。

1
2
3
4
5
h & (length-1)
h	0101 0101
15 	0000 1111
&	0000 0101
这个最后的取值结果是这个长度的低位

但是这个没有用到高位的hashcode，这样是不是没有用了？
不是这个h是根据hashcode移位算出的，最高位其实也参加了运算。

1
2
3
4
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}
存放
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//存放元素
void addEntry(int hash, K key, V value, int bucketIndex) {
    //判读是否超出阈值，这里还判断是否为null
    if ((size >= threshold) && (null != table[bucketIndex])) {		//进行扩容，后面会讲。
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
//获取这个位置原有的对象，然后创建对象，插入这个位置，头插法
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

扩容

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原的数据复制过来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//传入一个新的参数
void resize(int newCapacity) {
    Entry[] oldTable = table;//记录老数组
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {//判断老数组有没有大于阈值，最大就不在进行扩容。
        threshold = Integer.MAX_VALUE;
        return;
    }

    //创建新数组
    Entry[] newTable = new Entry[newCapacity];
    //转移
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//新数组，标记
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length; //取出长度
    for (Entry<K,V> e : table) { //将旧数组的元素存入新数组
        while(null != e) {
            Entry<K,V> next = e.next;
            //JDK8没有，从新生成hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);//得到新的数组下标
            //头插法
            e.next = newTable[i]; //这个元素的下一个节点
            newTable[i] = e; //把这个元素放入新的数组
            e = next;//下一个
        }
    }
}

这个方法会使链表的数据倒置

1
2
3
4
5
6
7
8
9
10
16 0101 0101
15 0000 1111
&  0000 0101
5
16 0101 0101
32 0001 1111
&  0001 0101   
5+16
1. 数组下标不发生变化
2. 数组下标发生变化 新的下标 = 旧的下标 + 旧数组长度

在多线程的情况下回出现循环链表，死锁

这是1.7的主要问题

  1. 两个线程都处于复制初始化阶段。

  2. 当第一个线程执行完复制操作之后.第二个线程刚开始复制这个这个位置的数指针的情况。

image-20200808195513024
  1. 第二个线程开始执行,执行完第一次赋值之后的情况。
image-20200808202810761
  1. 第二个线程第二次执行
image-20200808203259666
  1. 第二个线程第三次执行。此时形成循环链表

image-20200808203601057

原因：头插法导致数据顺序发生变化。

解决：

1.控制hashmap的阈值。防止他扩容

hash种子可能改变

1
2
3
4
5
6
7
8
9
10
11
12
final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

fail-fast机制

先看一段简单的代码

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
    HashMap<String,String> map = new HashMap();

    map.put("1","1");
    map.put("2","2");

    for (String key:map.keySet()){
        if (key=="2"){
            map.remove(key);//modcount++
        }
    }
}

会抛出异常

1
2
3
4
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextEntry(HashMap.java:926)
	at java.util.HashMap$KeyIterator.next(HashMap.java:960)
	at com.lq.offer.JZ13.main(JZ13.java:12)

就是防止在迭代的时候进行修改。容错机制。

如果2个线程，一个线程在遍历，另一个线程在删除，会出现并发的问题。

推荐使用迭代器的remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
    HashMap<String,String> map = new HashMap();

    map.put("1","1");
    map.put("2","2");
    Iterator<String> iterator = map.keySet().iterator();
    if (iterator.hasNext()){
        String key = iterator.next();
        if (key=="2"){
            iterator.remove(key);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
public void remove() {
    if (current == null)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    Object k = current.key;
    current = null;
    HashMap.this.removeEntryForKey(k);
    expectedModCount = modCount;//每次回重新赋值
}

JDK8

实现原理

  1. new HashMap():底层没创建一个长度为16的数组
  2. jdk 8底层的数组是：Node[],而非Entry[]
  3. 首次调用put()方法时，底层创建长度为16的数组
  4. jdk7底层结构只：数组+链表。jdk8中底层结构：数组+链表+红黑树。
    4.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
    4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

红黑树

由于链表在很长的时候查询效率会变低。所以jdk8中采用了红黑树来代替链表过长的情况。

定义

  1. 每个节点都是红色，或黑色
  2. 根节点是黑色
  3. 每个叶子节点是黑色
  4. 如果一个节点是红色，它儿子节点都是黑色
  5. 对每个节点，从该节点到子孙节点的所有路径上包含相同数目的黑节点

新节点为红色，在插入的过程中节点会进行变色。

插入新节点：

根节点之间插入

父节点是黑色不需要调整

父节点是红色

​ 1叔叔是空的或者为黑色，插入节点为左 ，旋转+变色。

​ 1.1插入左子树

img

​ 1.2插入右子树

img

​ 2.叔叔是红色，父节点+叔叔节点变黑色，祖父节点变为红色。

img

​ 3.叔叔是空的或者为黑色，插入节点为右，旋转+变色。与情况1类似

img img

hashmap中的实现

红黑树节点

1
2
3
4
5
6
7
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion 双向链表
    boolean red; //颜色
}

红黑树插入

image-20200810145906002

这个算法的左右旋对应的节点不相同

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
69
70
71
72
73
74
75
76
77
//根节点、要插入的数
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
    x.red = true;  //插入节点默认为红色
    /*
    xp:插入节点的父节点
    xpp:祖父节点
    xppl:xpp的左孩子节点，xppr表示右孩子节点
    */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //查看新节点的父节点是否为null,是不是第一个节点
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        //父节点是黑色 或者 他的父节点就是根节点
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
       	//插入节点的父节点等于 祖父节点的左节点
        if (xp == (xppl = xpp.left)) {
            //xpp的右节点不为null,并且为红色，这里针对第1个情况
            if ((xppr = xpp.right) != null && xppr.red) {
                //父节点和叔叔节点变黑，祖父节点变红
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                //然后将祖父节点变成要插入的节点，循环调整整颗子树
                x = xpp;
            }
            //如果没有叔叔节点 或者 叔叔节点是黑色 1情况
            else {
                //情况1
                //如果这个节点是 父节点的右孩子
                if (x == xp.right) {
                    //左旋，对xp进行左旋
                    root = rotateLeft(root, x = xp);
                    //对节点重新赋值，变成下面的那种情况
                    //相当于xp当成插入节点x,x当成xp，看图
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //右旋
                if (xp != null) {
                    //父节点先变色
                    xp.red = false;
                    if (xpp != null) {
                        //祖父节点不为空史，对xpp进行右旋
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //插入节点的父节点等于 祖父节点的右节点，情况3，与上面类似
        //左右旋传入的节点不同
        else {
            //xpp的左节点不为null,并且为红色，这里针对第1个情况
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

左旋

左旋时p必须存在右孩子节点

在r存在左孩子节点时（这里所有的root都是pp）

image-20200810161759635

当旋转节点的父节点为空时，r直接为根节点，进行旋转 情况1

旋转的节点是pp的左节点（rl节点和rr节点可以为null）情况2

image-20200810164354975

旋转的节点是pp的右节点（rl节点和rr节点可以为null）情况3

image-20200810164605813 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//这个方法是把p这个节点左转 ，传入节点为插入节点的父节点
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    //需要选择的节点不为null 并且右孩子节点不为空，左旋右孩子节点不能是空
    if (p != null && (r = p.right) != null) {
        //在r.left存在的情况下  给p.right重新赋值
        if ((rl = p.right = r.left) != null)
            rl.parent = p;//关系rl的父节点
        //在p的父节点为null时，直接旋转，相当于p就是根节点。
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        //p有父节点，并且p是pp的左节点
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        r.left = p;
        p.parent = r;
    }
    return root;
}

右旋

与左旋相同 ，右旋也是三种情况

当旋转节点的父节点为空时，r直接为根节点，进行旋转 情况1

旋转的节点是pp的右节点（ll节点和lr节点可以为null）情况2

image-20200810170657482

旋转的节点是pp的左节点（ll节点和lr节点可以为null）情况3

image-20200810170830334 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

Hash函数

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

jdk1.8底层采用红黑树，所以对数据散列性的需求并没有jdk1.7那么高，所以对hash函数进行了简化，但在数据的散列性上可能不如jdk1.7。

相比于jdk1.8 的 hash 方法 ，jdk1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

存储结构

内部包含了一个 实现Entry 的Node类型的数组 table。Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。

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
transient Node<K,V>[] table;

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

构造器

空参构造器

这里与jdk不同，没有创建一个默认大小的，而是创造了一个空的。

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    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);
}
//下面这个操作与jdk7中求容量类似，通过移位或运算
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;
}

put操作

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
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//evict在LinkHashMap中才有用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //jdk8在插入时才对table初始化，如果为空表示第一次使用
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//初始化
    //这个数组的位置没有放过
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//这个数组的位置已经存在，有3中情况 1.第一个一个元素 2.链表 3.红黑树
        Node<K,V> e; K k;
        //查看第一个节点的key是不是和要赋值的key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) //查看不是吧一个红黑树节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//链表
            //binCount阈值，是不是大于8,大于8转换成红黑树
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //没有这个节点，就创建一个新的节点插入链表尾部,尾插法
                    p.next = newNode(hash, key, value, null);
                    //是否要转红黑树，这里与是否加入新节点没有关系，只是遍历到8个节点就改变长度
                    //所以在转红黑树的时候链表上已经有9个节点了
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
               	//找到一个相等的key，直接跳出
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e已经存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //修改值+1
    ++modCount;
    //是否需要扩容
    if (++size > threshold)
        resize();
    //ListedHashMap才有用
    afterNodeInsertion(evict);
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
put流程：
1.检查数组是否为null,初始化数组
2.判断这个要插入的地方有没有值
	2.1没有节点，直接插入
	2.2有值，判断这个节点存在的可能性
		2.2.1这个节点的key等于了要插入的，break
		2.2.2如果这个节点是一颗树 ，插入一颗树的节点
		2.2.3这里是一个链表,遍历链表，不存在key相同的节点就尾插法插入节点，并且判断链表的长度是否为8
			大于等于8个元素，就对链表转换成红黑树。这里的长度与要插入的节点无关，只要到了8个就转。
		然后判断是否存在一样key的节点是否存在，存在就替换，并返回旧值
3.判断是否需要扩容

转换红黑树

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
69
70
71
72
73
74
75
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //数组是否为null，或数组的长度是否为64 对对数组进行扩容 ,对数组进行扩容会间接的减少链表上的值
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //遍历链表的每一个元素，把节点编程TreeNode，并生成双向链表。
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)//第一个节点不为null
            hd.treeify(tab);//把第一个节点传入
    }
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
//真正转换的方法
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //遍历链表，把每一个元素插入到红黑树中
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;//记录next
        x.left = x.right = null;
        if (root == null) { //第一个节点是黑色
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;  	//x表示要插入的节点
            int h = x.hash;
            Class<?> kc = null; //key的类型
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //比较hash值，判断是左右子树
                if ((ph = p.hash) > h)  //左边
                    dir = -1;
                else if (ph < h)  //右边
                    dir = 1;
                //这里是在hash值相同的时候判断key的大小，判断有没有实现类的比较器
                //实现了就去调用这个比较的方法区比较对象的大小
                else if ((kc == null &&
                          //返回key是否实现了Comparable接口
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                //如果方向的节点为null,就把节点放入
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //插入节点的过程，包括平衡。这个在上面有写。
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //把红黑树传入tab
    moveRootToFront(tab, root);
}
1
2
3
4
5
比较的方法：
hash值
compareto()方法
getClass().getName()类名
System.identityHashCode()获得没有被重写的hashcode值

转换红黑树之后的pre、next节点的值并没有发生变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//因为在转换红黑树时，第一个节点不一定是根节点，所以需要把根节点放到第一个节点
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        if (root != first) {  //根节点不等于第一个节点，这里把根节点放入双向链表的第一个位置
            Node<K,V> rn;
            tab[index] = root;
            TreeNode<K,V> rp = root.prev;
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        //这个地方是用于验证，需要控制台打开。
        assert checkInvariants(root);
    }
}

这里也就是为什么这个链表采用双向链表的原因。

resize方法

这里包括对数组的扩容和初始化、

扩容是一个特别耗性能的操作，所以当程序员在使用 HashMap，正确估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//数组是否为0
    int oldThr = threshold;
    int newCap, newThr = 0;
    //判断旧数组是否大于0
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //翻倍扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //？
            newThr = oldThr << 1; // double threshold
    }
    //初始化容量时有阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //使用默认
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { //新数组为0
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //这里是初始化和扩容
    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) //红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order   //链表
                    Node<K,V> loHead = null, loTail = null; //低头结点，低尾结点
                    Node<K,V> hiHead = null, hiTail = null; //高头结点，高尾结点
                    Node<K,V> next;
                    do {//遍历链表
                        next = e.next;
                         //扩容的地方只有2个要么是原位置，要么是原位置+原数组长度
                        //这里把原链表分成2个链表，在进行转移
                        if ((e.hash & oldCap) == 0) {//只于oldCap那一位有关，这里与7的代码类似
                           //低的
                            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
2
3
4
5
6
7
流程：
1.进行扩容或初始化的准备工作
2.初始化数组，或扩容数组
3.判断旧的数组是否为null，不为null就是扩容
	3.1只有一个元素，直接赋值
	3.2红黑树，进行红黑树的扩容方法
	3.3链表，遍历生成2个链表，在放入新的数组中

红黑树的扩容

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
//看红黑树的节点能否变成2个链表
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    //与链表类似
    TreeNode<K,V> loHead = null, loTail = null;  
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0; //统计两个链表的个数
    //这里节点去遍历链表，与前面类似
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc; 
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
	//如果链表的个数小于6，就把链表转换成红黑树
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            //把树节点变成链表节点
            tab[index] = loHead.untreeify(map);
        else {//还是一个红黑树
            tab[index] = loHead;
            //这里如果高位的链表是null，就说明只有一颗树，低位链表就是全部的节点，不需要重新生成红黑树
            if (hiHead != null) // (else is already treeified) 
                loHead.treeify(tab); //这个方法与put时的方法相同，是转换成红黑树的方法。
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//遍历链表，把treenode变成node 返回一个单向链表
final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

remove

移除的原理也是相同

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

在移除树节点的时候，需要判断这个树上的元素是不是小于等于6个，但是代码中并没有出现6个

1
2
3
4
5
6
7
8
9
//这里是判断转为链表的代码,这里说明了这棵树最多有6个
if (root == null
    || (movable
        && (root.right == null
            || (rl = root.left) == null
            || rl.left == null))) {
    tab[index] = first.untreeify(map);  // too small
    return;
}

常见面试题

底层数据结构

JDK7:数组+链表

JDK8：数组+链表+红黑树（在链表时期使用了单向链表，在红黑树，为了方便找到头结点，使用了双向链表,双向链表主要方便操作，在、插入，扩容、红黑树转链表，链表转红黑树的过程中都有操作链表）

为什么使用红黑树

在元素大于一个阈值时，元素的查询效率要低于红黑树，此阈值在JDK8中为8

什么时候转换成红黑树

当链表中元素的个数大于8之后，会判断一下当前的长度，如果数组小于64，就不会转换成红黑树，而是进行扩容到64，只有当前链表个数为8，并且数组元素大于等于64时才会将链表转换红黑树。

PUT操作流程

上面

GET操作流程

1.根据key生成hashcode
2.如果数组为空,则直接返回空
3.如果数组不为空，则利用hashcode和数组长度通过逻辑 与操作算出key所对应的数组下标i
4.如果数组的第i个位置上没有元素，则直接返回空
5.如果数组的第1个位上的元素的key等于get方法所传进来的key,则返回该元素，并获取该元素的value
6.如果不等于则判断该元素还有没有下一个元素，如果没有，返回空
7.如果有则判断该元素的类型是链表结点还是红黑树结点
a.如果是链表则遍历链表
b.如果是红黑树则遍历红黑树
8.找到即返回元素，没找到的则返回空

JDK7和JD8中的HashMap不同

  1. JDK8中使用了红黑树
  2. JDK7中链表的插入使用的头插法(扩容转移元素的时候也是使用的头插法，头插法速度更快，无需遍历链表，
    但是在多线程扩容的情况下使用头插法会出现循环链表的问题，导致CPU飙升)，JDK8中链表使用的尾插法
    (JDK8中反正要去计算链表当前结点的个数，反正要遍历的链表的，所以直接使用尾插法)
  3. JDK7的Hash算法比JDK8中的更复杂，Hash算法越复杂，生成的hashcode则更散列，那么hashmap中的元
    素则更散列，更散列则hashmap的查询性能更好，JDK7中没有红黑树,所以只能优化Hash算法使得元素更散
    列，而JDK8中增加了红黑树，查询性能得到了保障，所以可以简化-下Hash算法， 毕竟Hash算法越复杂就越
    消耗CPU
  4. 扩容的过程中JDK7中有可能会重新对key进行哈希(重新Hash跟哈希种子有关系)，而JDK8中没有这部分逻
    辑
  5. JDK8中扩容的条件和JDK7中不一样，除开判断size是否大于阈值之外, JDK7中还判断了tab[i]是否为空，不
    为空的时候才会进行扩容，而JDK8中则没有该条件了
  6. JDK8中还多了一个API: putIfAbsent(key,value)
  7. JDK7和JDK8扩容过程中转移元素的逻辑不一样, JDK7是每次转移-个元素，JDK8是先算出来当前位置上哪
    些元素在新数组的低位上，哪些在新数组的高位上，然后在- -次性转移

参考

红黑树https://www.jianshu.com/p/e136ec79235c