java学习-HashMap剖析

太过爱你忘了你带给我的痛 2023-10-02 21:34 3阅读 0赞

#### 文章目录 ####

*  一、HashMap
 *   *  1.数据结构(数组+链表或红黑树)
     *  2.put(k,v)插入元素方法
     *  3.get(k)方法
     *  4.HashMap为什么线程不安全？
     *   *  4.1 JDK1.7中的线程不安全
         *  4.1 JDK1.8中的线程不安全
 *  总结

--------------------

## 一、HashMap ##

### 1.数据结构(数组+链表或红黑树) ###

![在这里插入图片描述][1158b6a389a54e3d987fd1b662ddc2f1.png]

1.  数组  
    存储区间连续，占用内存严重，空间复杂大，时间复杂为o(1)。  
    **优点：是随机读取效率很高，原因数组是连续（随机访问性强，查找速度快）。**  
    **缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中要往后移的，且大小固定不易动态扩展。**
2.  链表  
    存储区间离散，占用内存宽松，空间复杂度小，时间复杂度o(N)。  
    **优点：插入删除速度快，内存利用率高，没有大小固定，扩展灵活。  
    缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低)。**
3.  红黑树  
    特点：  
    a.**节点不是黑色，就是红色（非黑即红）。**  
    b.**根节点为黑色。**  
    c.**叶节点为黑色（叶节点是指末梢的空节点 Nil或Null）。**  
    d.**一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）。**  
    e.**每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）。**  
    以上特效保证了红黑树的大致平衡：**根到叶子的所有路径中，最长路径不会超过最短路径的2倍。**  
    红黑树示例如下：  
    ![在这里插入图片描述][188d40fa194c4a9abd6a7e52078c793b.png]

### 2.put(k,v)插入元素方法 ###

流程图大致如下：  
![在这里插入图片描述][521d8c1e024e42dcbadd6cd4c45a88ad.png_pic_center]

1.  首先判断map是否有数据或为null，如果为true，则执行resize()方法。

if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;

1.  根据key的hash值查看当前位置是否存在元素，如果不存在，则将键值对封装成Node对象放入当前位置。

if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

1.  根据key的hash值查看当前位置是否存在元素，如果不存在则直接放入，如果存在则判断当前节点类型是否TreeNode类型，如果是则执行putTreeVal方法。

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

4.如果存在则判断当前节点类型不是TreeNode类型,则遍历当前链表的数据。完成数据的插入后可能会执行 treeifyBin()方法即是否转变为红黑树。

else {
        
            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;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }

说明：  
1.HashMap的初始容量为16，加载因子为0.75。加载因子为0.75的原因:**0.75是经过多重计算检验得到的可靠值，可以最大成都的减少rehash的次数，避免性能消耗。**  
2.链表转变为红黑树的条件：数组长度大于64且链表长度大于8。  
为什么数组长度大于64，链表才会进化为红黑树？  
数组长度小于64时，搜索速度相对较快。  
为什么链表节点个数大于8才转为红黑树？  
**树节点占用空间是普通Node的两倍**，如果链表结点不够多就转变为红黑树会消耗大量空间资源。随机hash算法下的所有bin节点分布频率遵从泊松分布，**链表长度达到8的概率只有0.00000006**，几乎是不可能事件，所以8的计算是经过重重科学考量的。  
•从**平均查找长度**来看，红黑树的平均查找长度是logn，如果长度为8，则logn=3，而链表的平均  
查找长度为n/4，长度为8时，n/2=4，所以阈值8能大大提高搜索速度。  
•当长度为6时红黑树退化为链表是因为logn=log6约等于2.6，而n/2=6/2=3，两者相差不大，而**红黑树节点古用更多的内存空间**，所以此时转换最为友好。

### 3.get(k)方法 ###

1.  先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
2.  通过数组下标快速定位到某个位置上。如果该位置没有元素，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。如果该位置有红黑树，则遍历树节点。

### 4.HashMap为什么线程不安全？ ###

#### 4.1 JDK1.7中的线程不安全 ####

HashMap的线程不安全主要是发生在扩容方法transfer中，JDK1.7中HashMap的transfer函数如下：

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;
                    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.7中hashmap先扩容，再**头插法**进行元素的插入。头插法会将原有链表元素的顺序翻转，**多线程操作的时候可能会出现死循环和数据丢失**。

#### 4.1 JDK1.8中的线程不安全 ####

1.8中采用尾插法、resize解决了1.7中的死循环和数据丢失的问题，但是还是存在**数据覆盖**的问题。发生在putVal函数中，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;
            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 {
                Node<K,V> e; K k;
                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 {
                    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;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)//此处对size的++操作线程不安全
                resize();
            afterNodeInsertion(evict);
            return null;
        }

第一种情况：A、B线程需要插入的值，key根据hash函数计算后相等。A线程在执行下面这段代码后挂起。

if ((p = tab[i = (n - 1) & hash]) == null)

**B线程正常插入值后，A线程被唤醒重新执行，A之前已经进行了hash冲突的判断，所以会直接在之前算好的位置插入，就会覆盖B线程插入的值。所以线程不安全**。  
第二种情况：if (++size > threshold)中，假设size为16，A线程获取size后线程挂起。此时B完成正常操作  
size变为11写入主内存。**A线程被唤醒，A线程中的size还是10，进行++变为11,写入主内存。但是实际上插入了两个元素，size却只增加了1。所以线程不安全。**

--------------------

## 总结 ##

以上为个人学习过程中对java的一些学习总结，如有错误，欢迎各位批评指导，如有侵权，请联系本人删除，谢谢！

[1158b6a389a54e3d987fd1b662ddc2f1.png]: https://img-blog.csdnimg.cn/1158b6a389a54e3d987fd1b662ddc2f1.png
[188d40fa194c4a9abd6a7e52078c793b.png]: https://img-blog.csdnimg.cn/188d40fa194c4a9abd6a7e52078c793b.png
[521d8c1e024e42dcbadd6cd4c45a88ad.png_pic_center]: https://img-blog.csdnimg.cn/521d8c1e024e42dcbadd6cd4c45a88ad.png#pic_center