HashMap详解

HashMap相关介绍

HashMap是Java中的比较常见的集合，主要存放的是键值对，以key-value的形式存储，不是线程安全的。它里面的存储的key和value可以为null值，但是key只允许有一个null值。HashMap是无序的，无法保证里面存储的键值对的有序性。jdk1.8之前的版本底层采用的是数组+链表的方式组成，jdk1.8之后采用的是数组+链表+红黑树的方式。数组具有查询效率高、插入、删除效率低，链表具有查询效率低，但是插入、删除效率高，HashMap采用这两种方式的结构，可以保证查询、插入、删除效率都得到保证。

HashMap数据结构

jdk1.8之后的版本使用数据+链表+红黑树的方式作为底层的数据结构，在链表长度大于阈值8之后，如果数组长度大于64时，才会转换成红黑树进行存储。阈值默认是8。下面我们介绍一下HashMap的设值过程：

我们在调用HashMap的put设值时，首先会对值进行hash操作。

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

判断索引的数组位置是否为空，如果为空，则进行初始化，分配空间，进行扩容。
```
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);

如果这个位置有值，则需要解决冲突
- 首先判断链表的头，代码中的p，先判断hash值是否和我们的相同，如果hash值相同的话，在判断具体数值，如果相同，则先记录该位置，也就是代码中的e。
```
Node<K,V> e; K k;
if (p.hash == hash &&
  ((k = p.key) == key || (key != null && key.equals(k))))
  e = p;
```
- 如果不同，那就需要遍历链表，jdk1.8之后的做了优化，链表太长时，会转换成红黑树，如果是TreeNode,则调用TreeNode的方法进行插入，此时就是采用的红黑树作为数据结构。
```
else if (p instanceof TreeNode)
  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
```
- 如果不是TreeNode,则是用循环的方式遍历链表，如果有相同的链表节点，则记录该节点,代码中的e，如果没有相同的链表节点，则e为null,此时会创建一个新的Node，插入在链表最后。
```
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}
```
- 最后判断e是不是null,e代表的是是否存在相同的值，存在，则记录的位置，不存在，则为null,如果存在，则会直接更新e记录的位置的值。
```
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
```
- 在循环遍历链表时，如果该节点是个新的节点，插入在链表最后，此时会判断链表的长度是否大于TREEIFY_THRESHOLD - 1,默认是8，如果大于8,则会调用转换成红黑树的方法，但是，方法里面还会判断数组长度是否大于MIN_TREEIFY_CAPACITY,默认是64,如果大于，则转换成红黑树。
```
if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}
```
```
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
```

关注微信公众号「平哥技术站」, 每日更新，在手机上阅读所有教程，随时随地都能学习。

觉得写的还不错的小伙伴，请作者喝杯咖啡☕ ,支持一下。😊

如有侵权请立即与我们联系，我们将及时处理，联系邮箱:865934097@qq.com。

目录CONTENT

HashMap详解

HashMap详解

HashMap相关介绍

HashMap数据结构

评论区