本文共 11358 字,大约阅读时间需要 37 分钟。
前言:把这段时间复习的关于集合类的东西整理出来,特别是HashMap相关的一些东西,之前都没有很注意1.7 ->> 1.8的变化问题,但后来发现这其实变化挺大的,而且很多整理的面试资料都没有更新(包括我之前整理的…)
1)说说常见的集合有哪些吧? 答:Map接口和Collection接口是所有集合框架的父接口: Collection接口的子接口包括:Set接口和List接口 Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等 Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等 List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等 2)HashMap与HashTable的区别? 答: HashMap没有考虑同步,是线程不安全的;Hashtable使用了synchronized关键字,是线程安全的; HashMap允许K/V都为null;后者K/V都不允许为null; HashMap继承自AbstractMap类;而Hashtable继承自Dictionary类; 3)HashMap的put方法的具体流程? 图引用自:https://blog.csdn.net/u011240877/article/details/53358305 答:下面先来分析一下源码 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; // 1.如果table为空或者长度为0,即没有元素,那么使用resize()方法扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2.计算插入存储的数组索引i,此处计算方法同 1.7 中的indexFor()方法 // 如果数组为空,即不存在Hash冲突,则直接插入数组 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 3.插入时,如果发生Hash冲突,则依次往下判断 else { HashMap.Node<K,V> e; K k; // a.判断table[i]的元素的key是否与需要插入的key一样,若相同则直接用新的value覆盖掉旧的value // 判断原则equals() - 所以需要当key的对象重写该方法 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // b.继续判断:需要插入的数据结构是红黑树还是链表 // 如果是红黑树,则直接在树中插入 or 更新键值对 else if (p instanceof HashMap.TreeNode) e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果是链表,则在链表中插入 or 更新键值对 else { // i .遍历table[i],判断key是否已存在:采用equals对比当前遍历结点的key与需要插入数据的key // 如果存在相同的,则直接覆盖 // ii.遍历完毕后任务发现上述情况,则直接在链表尾部插入数据 // 插入完成后判断链表长度是否 > 8:若是,则把链表转换成红黑树 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; } } // 对于i 情况的后续操作:发现key已存在,直接用新value覆盖旧value&返回旧value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 插入成功后,判断实际存在的键值对数量size > 最大容量 // 如果大于则进行扩容 if (++size > threshold) resize(); // 插入成功时会调用的方法(默认实现为空) afterNodeInsertion(evict); return null; }图片简单总结为:
4)HashMap的扩容操作是怎么实现的?
答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析: /**5)HashMap是怎么解决哈希冲突的?
参考资料:https://juejin.im/post/5ab99afff265da23a2291dee 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突:这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化
hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) }这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动);
JDK1.8新增红黑树通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn);
总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的:equals()
方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; 9)ConcurrentHashMap和Hashtable的区别? 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。ConcurrentHashMap 锁的方式是稍微细粒度的。 面试官:ConcurrentHashMap的具体实现知道吗? 参考资料:http://www.importnew.com/23610.html 答:在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下:该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;
Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,结构如下:插入元素过程(建议去看看源码):
如果相应位置的Node还没有初始化,则调用CAS插入相应的数据; else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin }如果相应位置的Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁,如果该节点的hash不小于0,则遍历链表更新节点或插入新节点;
if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } }如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;
如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 10)Java集合的快速失败机制 “fail-fast”? 答: 是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。 例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。 原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。 解决办法:由于HashMap的K值本身就不允许重复,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V,那么在HashSet中执行这一句话始终会返回一个false,导致插入失败,这样就保证了数据的不可重复性;
14)BlockingQueue是什么? 答: Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。免费分享java技术资料,需要的朋友可以在关注后私信我,自助领取