彻底理解 HashMap 及 LinkedHashMap,面试官请随便问!(3)

简介: 彻底理解 HashMap 及 LinkedHashMap,面试官请随便问!

1.7 HashMap的线程不安全

所有人都知道HashMap是线程不安全的,我们应该使用ConcurrentHashMap。但是为什么HashMap是线程不安全的呢?


首先需要强调一点,HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在JDK1.7中出现的问题,在JDK1.8中已经得到解决,然而1.8中仍会有数据覆盖的问题,即在并发执行HashMap的put操作时会发生数据覆盖的情况。


首先扩容会造成HashMap的线程不安全,根源就在JDK1.7的transfer函数中。transfer方法将原有Entry数组的元素拷贝到新的Entry数组里。JDK1.7中HashMap的transfer函数源码如下:


void transfer(Entry[] newTable) {
 //src引用了旧的Entry数组
 Entry[] src = table; 
 int newCapacity = newTable.length;
 //遍历旧的Entry数组
 for (int j = 0; j < src.length; j++) {
  //取得旧Entry数组的每个元素
  Entry<K,V> e = src[j]; 
  if (e != null) {
  src[j] = null;
  //释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
  do {
   Entry<K,V> next = e.next;
   int i = indexFor(e.hash, newCapacity); 
   //重新计算每个元素在数组中的位置
   e.next = newTable[i]; //标记[1]
   newTable[i] = e; //将元素放在数组上
   e = next; 
   //访问下一个Entry链上的元素
   } while (e != null);
  }
 }
}

这段代码是HashMap的扩容操作,重新定位每个桶的下标,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是在多线程环境下会形成死循环的关键点。扩容造成死循环和数据丢失的详细过程这里不再赘述,可以搜索很多分析这个过程的文章。


JDK1.8的源码中已经没有transfer函数,因为JDK1.8直接在resize函数中完成了数据迁移。此外JDK1.8在进行元素插入时使用的是尾插法。为什么多线程环境下JDK1.8的HashMap会出现数据覆盖的情况呢,我们来看一下JDK1.8中的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;
    //第一次put元素时,table数组为空,先调用resize生成一个指定容量的数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //hash值和n-1的与运算结果为桶的位置,如果该位置空就直接放置一个Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果计算出的bucket不空,即发生哈希冲突,就要进一下判断
    else {
        Node<K,V> e; K k;
        //判断当前Node的key与要put的key是否相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断当前Node是否是红黑树的节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //以上都不是,说明要new一个Node,加入到链表中
        else {
            for (int binCount = 0; ; ++binCount) {
             //进入这个if说明是到达链表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    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;
            }
        }
        //走到这里,说明本次put是更新一个已存在的键值对的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //在hashMap中,afterNodeAccess方法体为空,交给子类去实现
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //下面两个自增操作都不是原子的
    ++modCount;
    if (++size > threshold)
        resize();
    //在hashMap中,afterNodeInsertion方法体为空,交给子类去实现
    afterNodeInsertion(evict);
    return null;
}

其中if((p = tab[i = (n - 1) & hash]) == null)是判断是否出现hash碰撞,假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A执行完这行代码后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所以此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。


除此之外,还有就是代码的末尾部分有个++size,我们这样想,还是线程A、B,这两个线程同时进行put操作时,假设当前HashMap的size大小为10,当线程A执行到size自增这行代码时,从主内存中获得size的值为10后准备进行+1操作,但是由于时间片耗尽只好让出CPU,线程B拿到CPU还是从主内存中拿到size的值10进行+1操作,完成了put操作并将size=11写回主内存,由于size不是volatile修改的变量,然后线程A再次拿到CPU后不会再从主内存中加载一次size的值,而是使用自己工作内存中的副本,继续执行加1,当执行完put操作后,还是将size=11写回主内存,此时,线程A、B都执行了一次put操作,但是size的值只增加了1,所有说还是由于数据覆盖又导致了线程不安全。


2、LinkedHashMap概述

HashMap是Java Collection Framework的重要成员,也是Map族中我们最为常用的一种。不过遗憾的是,HashMap是无序的,也就是说,迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便,因为在有些场景中,我们确需要用到一个可以保持插入顺序的Map。庆幸的是,JDK为我们解决了这个问题,它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销,但是它通过维护一个额外的双向链表保证了迭代顺序==。特别地,==该迭代顺序可以是插入顺序,也可以是访问顺序。因此,根据链表中元素的顺序可以将LinkedHashMap分为:保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap,其中LinkedHashMap的默认实现是按插入顺序排序的。


image.png


更直观地,下图很好地还原了LinkedHashMap的原貌:HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是,next用于维护HashMap各个桶中的Entry链,before、after用于维护LinkedHashMap的双向链表,虽然它们的作用对象都是Entry,但是各自分离,是两码事儿。


image.png


特别地,由于LinkedHashMap是HashMap的子类,所以LinkedHashMap自然会拥有HashMap的所有特性。比如,LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖),但允许多条Entry的值为Null。此外,LinkedHashMap 也是 Map 的一个非同步的实现。此外,LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法。


2.1、LinkedHashMap定义及构造函数

本质上,HashMap和双向链表合二为一即是LinkedHashMap。JDK1.8中LinkedHashMap的定义源码如下:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
 /**
  * HashMap.Node subclass for normal LinkedHashMap entries.
  */
 static class Entry<K,V> extends HashMap.Node<K,V> {
  //再加两个引用,分别指向前一个插入的Entry与后一个插入的Entry
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
         super(hash, key, value, next);
     }
 }
 /**
  * The head (eldest) of the doubly linked list.
  * 头节点引用
  */
 transient LinkedHashMap.Entry<K,V> head;
 /**
  * The tail (youngest) of the doubly linked list.
  * 尾节点引用
  */
 transient LinkedHashMap.Entry<K,V> tail;
 /**
  * The iteration ordering method for this linked hash map: <tt>true</tt>
  * for access-order, <tt>false</tt> for insertion-order.
  * true表示按照访问顺序迭代,false时表示按照插入顺序 
  * @serial
  */
 final boolean accessOrder;
 ... 
}

LinkedHashMap采用的hash算法和HashMap相同,但是它重新定义了Entry。LinkedHashMap中的Entry继承了HashMap.Node,但增加了两个指针before 和 after,它们分别用于维护双向链接列表。特别需要注意的是,next用于维护HashMap各个Node的连接顺序,before、after用于维护Entry插入的先后顺序。


LinkedHashMap的5大构造函数都是在HashMap的构造函数的基础上实现的,分别如下:


public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

2.2、LinkedHashMap的快速存取

在HashMap中最常用的两个操作就是:put(Key,Value) 和 get(Key)。同样地,在LinkedHashMap 中最常用的也是这两个操作。对于put(Key,Value)方法而言,LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法,只是对putVal(hash,key, value, onlyIfAbsent,evict)方法所调用的afterNodeAccess方法和afterNodeInsertion方法进行了重写;对于get(Key)方法,LinkedHashMap则直接对它进行了重写。下面我们结合JDK源码看 LinkedHashMap 的存取实现。


HashMap的putVal源码,上一节中已经分析过,直接来看LinkedHashMap对afterNodeAccess和afterNodeInsertion方法的实现:


void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
/**
 * 如果map应该删除最老的节点,返回true
 * 这个方法在被put和putAll方法被调用,当向map中插入一个新的entry时被执行。这个方法提供了当一个新的entry被添加到linkedHashMap中,删除最老节点的机会。
 * 
 * 这个方法是很有用的,可以通过删除最老节点来减少内存消耗,避免溢出。
 * 
 * 简单的例子:这个方法的重写将map的最大值设为100,到100时,每次增一个entry,就删除一次最老节点。
 * 
 *     private static final int MAX_ENTRIES = 100;
 *
 *     protected boolean removeEldestEntry(Map.Entry eldest) {
 *        return size() > MAX_ENTRIES;
 *     }
 *
 * 这个方法一般不会直接修改map,而是通过返回true或者false来控制是否修改map。
 *
  *
 * @param    eldest 最老的节点(即头节点)
 * @return   如果map应该删除头节点就返回true,否则返回false
 */
 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
 }

2.3、LinkedHashMap与LRU算法


到此为止,我们已经分析完了LinkedHashMap的存取实现,这与HashMap大体相同。LinkedHashMap区别于HashMap最大的一个不同点是,前者是有序的,而后者是无序的。为此,LinkedHashMap增加了两个属性用于保证顺序,分别是双向链表头结点header和标志位accessOrder。我们知道,header是LinkedHashMap所维护的双向链表的头结点,而accessOrder用于决定具体的迭代顺序。


我们知道,当accessOrder标志位为true时,表示双向链表中的元素按照访问的先后顺序排列,可以看到,虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序,但put和get方法均有判断accessOrder的值。如果accessOrder为true,put时将新插入的元素放入到双向链表的尾部,get时将当前访问的Entry移到双向链表的尾部。当标志位accessOrder的值为false时,表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序,即每次put到LinkedHashMap中的Entry都放在双向链表的尾部,这样遍历双向链表时,Entry的输出顺序便和插入的顺序一致,这也是默认的双向链表的存储顺序。


测试代码


@Test
public void testLinkedHashMap() {
    Map<String, String> map = new HashMap<>(128);
    System.out.println("------HashMap------");
    map.put("first", "a");
    map.put("second", "b");
    map.put("third", "c");
    map.put("fourth", "d");
    map.put("fifth", "e");
    map.put("sixth", "f");
    map.forEach((key,value) -> {
        System.out.println("key=" + key + ",value=" + value);
    });
    map.clear();
    System.out.println("------LinkedHashMap------");
    map = new LinkedHashMap<>(128);
    map.put("first", "a");
    map.put("second", "b");
    map.put("third", "c");
    map.put("fourth", "d");
    map.put("fifth", "e");
    map.put("sixth", "f");
    map.forEach((key,value) -> {
        System.out.println("key=" + key + ",value=" + value);
    });
}

运行结果如下,HashMap不保证有序而LinkedHashMap默认按迭代顺序和插入的顺序一致。


image.png


前面介绍的LinkedHashMap的五种构造方法,前四个构造方法都将accessOrder设为false,说明默认是按照插入顺序排序的;而第五个构造方法可以自定义传入的accessOrder的值。当我们要用LinkedHashMap实现LRU算法时,就需要调用该构造方法并将accessOrder置为true。


使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。我们可以看到,无论是put方法还是get方法,都会导致目标Entry成为最近访问的Entry,因此就把该Entry加入到了双向链表的末尾。这样,我们便把最近使用的Entry放入到了双向链表的后面。多次操作后,双向链表前面的Entry便是最近没有使用的,这样当节点个数满的时候,删除最前面的Entry即可,因为它就是最近最少使用的Entry。


public class SomeTest {
    @Test
    public void testLru() {
        LRU<Character, Integer> lru = new LRU<>(8);
        String s = "abcdefghijkl";
        for (int i = 0; i < s.length(); i++) {
            lru.put(s.charAt(i), i + 1);
        }
        System.out.println("LRU的大小: " + lru.size());
        System.out.println(lru);
        System.out.println("LRU的中key为h的value值: " + lru.get('h'));
        System.out.println(lru);
        lru.put('z', 26);
        System.out.println(lru);
    }
    public static class LRU<K, V> extends LinkedHashMap<K, V> {
        private int cacheSize;
        public LRU(int cacheSize) {
            super(cacheSize, 0.75f, true);
            this.cacheSize = cacheSize;
        }
        /**
         * 重写LinkedHashMap中的removeEldestEntry方法,当LRU中元素多余cacheSize个时,删除最老的节点(即最不经常使用的元素)
         * @param eldest
         * @return
         */
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > getCacheSize();
        }
        public int getCacheSize() {
            return cacheSize;
        }
    }
}

运行结果:


LRU的大小:8 {e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12} LRU的中key为h的value值:8 {e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8} {f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}



相关文章
|
14天前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
34 3
|
26天前
|
存储 算法 安全
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
3月前
|
存储 安全 Java
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)
这篇文章是关于Java面试的第二天笔记,涵盖了HashMap与HashTable的区别、ConcurrentHashMap的实现原理、IOC容器的实现方法、字节码的概念和作用、Java类加载器的类型、双亲委派模型、Java异常体系、GC如何判断对象可回收、线程的生命周期及状态,以及sleep、wait、join、yield的区别等十道面试题。
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)
|
3月前
|
安全 Java
【Java集合类面试十五】、说一说HashMap和HashTable的区别
HashMap和Hashtable的主要区别在于Hashtable是线程安全的,不允许null键和值,而HashMap是非线程安全的,允许null键和值。
|
3月前
|
存储 Java
HashMap与LinkedHashMap类型集合
【8月更文挑战第4天】`HashMap` 是基于哈希表实现的键值对存储结构,提供快速的查找、插入和删除操作,但不保证元素顺序。适用于不关心顺序且需高效操作的场景。 `LinkedHashMap` 继承自 `HashMap`,保持了元素的插入或访问顺序。适合需要按特定顺序遍历元素的应用,如按添加顺序显示购物车商品。其操作效率与 `HashMap` 相近。
|
6月前
|
存储 算法 Java
如果面试也能这样说HashMap,那么就不会有那么多遗憾!(中)
如果面试也能这样说HashMap,那么就不会有那么多遗憾!
46 0
|
5月前
|
存储 安全 Java
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
38 0
|
6月前
|
Python
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
|
6月前
|
存储 算法 Java
耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!
耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!
90 3
|
6月前
|
Java API
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
40 1