开篇介绍

大家好，我是Java最全面试题库的提裤姐，明天这篇是JavaSE系列的第十篇，次要总结了Java汇合中的Map汇合，在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。

HashMap和HashTable有什么区别？

  • HashMap容许键和值是null，而Hashtable不容许键或者值是null。
  • Hashtable是同步的，而HashMap不是。因而，HashMap更适宜于单线程环境，而Hashtable适宜于多线程环境。
  • HashMap提供了可供给用迭代的键的汇合，因而，HashMap是疾速失败的。另一方面，Hashtable提供了对键的列举(Enumeration)。
  • 因为Hashtable继承自Dictionary类。而这个类曾经基本上废除了，所以个别认为Hashtable是一个遗留的类。

Java中HashMap的key值要是为类对象，则该类须要满足什么条件？

须要重写equals()和hashCode()办法。

谈一下HashMap的个性？

1.HashMap存储键值对实现疾速存取，容许为null。key值不可反复，若key值反复则笼罩。
2.非同步，线程不平安。
3.底层是hash表，不保障有序(比方插入的程序)；

谈一下HashMap的存储构造？

1.7版本：数组+链表
1.8版本：数组+链表+红黑树


图中，紫色局部即代表哈希表，也称为哈希数组（默认数组大小是16，每对key-value键值对其实是存在map的外部类entry里的），数组的每个元素都是一个单链表的头节点，跟着的绿色链表是用来解决抵触的，如果不同的key映射到了数组的同一地位处，就会采纳头插法将其放入单链表中。

HashMap在JDK1.7和JDK1.8中有哪些不同？

说一下HashMap扩容机制？

何时进行扩容？

HashMap应用的是懒加载，结构完HashMap对象后，只有不进行put 办法插入元素之前，HashMap并不会去初始化或者扩容table。
当首次调用put办法时，HashMap会发现table为空而后调用resize办法进行初始化，当增加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize办法进行扩容。

扩容过程：
若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16
默认的负载因子大小为0.75，当一个map填满了75%的bucket时候（即达到了默认负载因子0.75），就会扩容，扩容后的table大小变为原来的两倍（扩容后主动计算每个键值对地位，且长度必须为16或者2的整数次幂）
若不是16或者2的幂次，位运算的后果不够均匀分布，显然不合乎Hash算法均匀分布的准则。
反观长度16或者其余2的幂，Length-1的值是所有二进制位全为1，这种状况下，index的后果等同于HashCode后几位的值。只有输出的HashCode自身散布平均，Hash算法的后果就是平均的。
假如扩容前的table大小为2的N次方，元素的table索引为其hash值的后N位确定扩容后的table大小即为2的N+1次方，则其中元素的table索引为其hash值的后N+1位确定，比原来多了一位从新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing
因而，table中的元素只有两种状况：
元素hash值第N+1位为0：不须要进行地位调整
元素hash值第N+1位为1：将以后地位挪动到 原索引+未扩容前的数组长度 的地位
扩容或初始化实现后，resize办法返回新的table

遍历map汇合的三种形式？

public static void main(String[] args) {         Map<String, String> map = new HashMap<>();        //增加办法        map.put("我的昵称", "极多人小红");        map.put("我的csdn", "csdn_hcx");        map.put("我的简书", "js_hcx");        map.put("我的网站", "www.hcxblog.site");        //map汇合中遍历形式一： 应用keySet办法进行遍历       毛病：keySet办法只是返回了所有的键，没有值。        Set<String> keys = map.keySet();  //keySet() 把Map汇合中的所有键都保留到一个Set类型 的汇合对象中返回。        Iterator<String> it = keys.iterator();        while (it.hasNext()) {            String key = it.next();            System.out.println("键：" + key + " 值：" + map.get(key));        }        //map汇合的遍历形式二： 应用values办法进行 遍历。    毛病：values办法只能返回所有 的值，没有键。        Collection<String> c = map.values(); //values() 把所有的值存储到一个Collection汇合中返回。        Iterator<String> it2 = c.iterator();        while (it2.hasNext()) {            System.out.println("值：" + it2.next());        }        //map汇合的遍历形式三：entrySet办法遍历。        Set<Map.Entry<String, String>> entrys = map.entrySet();        //因为Iterator遍历的是每一个entry，所以也用泛型：<Map.Entry<String,String>>        Iterator<Map.Entry<String, String>> it3 = entrys.iterator();        while (it3.hasNext()) {            Map.Entry<String, String> entry = it3.next();            System.out.println("键：" + entry.getKey() + " 值：" + entry.getValue());        }}

并发汇合和一般汇合区别？

并发汇合常见的有 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque 等。并发汇合位于 java.util.concurrent 包下,是 jdk1.5 之后才有的。
在 java 中有一般汇合、同步（线程平安）的汇合、并发汇合。
一般汇合通常性能最高，然而不保障多线程的安全性和并发的可靠性。
线程平安汇合仅仅是给汇合增加了 synchronized 同步锁，重大就义了性能，而且对并发的效率就更低了，并发汇合则通过简单的策略不仅保障了多线程的平安又进步的并发时的效率。

HashMap的put()和get()原理？

put()原理：
1.依据key获取对应hash值：int hash = hash（key.hash.hashcode（））
2.依据hash值和数组长度确定对应数组引int i = indexFor(hash, table.length);
简略了解就是i = hash值%模以 数组长度（其实是按位与运算）。如果不同的key都映射到了数组的同一地位处，就将其放入单链表中。且新来的是放在头节点。

get()原理：
通过hash取得对应数组地位，遍历该数组所在链表（key.equals（））

HashCode雷同，抵触怎么办？

采纳“头插法”，放到对应的链表的头部。
因为HashMap的发明者认为，后插入的Entry被查找的可能性更大，所以放在头部。（因为get()查问的时候会遍历整个链表）。

HashMap是线程平安的吗？为什么？在并发时会导致什么问题？

不是，因为没加锁。
hashmap在靠近临界点时，若此时两个或者多个线程进行put操作，都会进行resize（扩容）和ReHash（为key从新计算所在位置），而ReHash在并发的状况下可能会造成链表环。在执行get的时候，会触发死循环，引起CPU的100%问题。

注：jdk8曾经修复hashmap这个问题了，jdk8中扩容时放弃了原来链表中的程序。然而HashMap仍是非并发平安，在并发下，还是要应用ConcurrentHashMap。

HashMap如何判断有环形表？

创立两个指针A和B（在java里就是两个对象援用），同时指向这个链表的头节点。而后开始一个大循环，在循环体中，让指针A每次向下挪动一个节点，让指针B每次向下挪动两个节点，而后比拟两个指针指向的节点是否雷同。如果雷同，则判断出链表有环，如果不同，则持续下一次循环。
通俗易懂一点：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，起因很简略，因为跑道是环形的。

介绍一下ConcurrentHashMap？

构造:

hashmap是由entry数组组成，而ConcurrentHashMap则是Segment数组组成。
Segment自身就相当于一个HashMap。
同HashMap一样，Segment蕴含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。
繁多的Segment构造如下：

Segment对象在ConcurrentHashMap汇合中有2的N次方个，独特保留在一个名为segments的数组当中。
能够说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表上面，有若干个子哈希表。（这样类比了解多个hashmap组成一个cmap）

ConcurrentHashMap的put()和get()原理？

put()原理：
1.为输出的Key做Hash运算，失去hash值。
2.通过hash值，定位到对应的Segment对象
3.获取可重入锁
4.再次通过hash值，定位到Segment当中数组的具体位置。
5.插入或笼罩HashEntry对象。
6.开释锁。

get()原理：
1.为输出的Key做Hash运算，失去hash值。
2.通过hash值，定位到对应的Segment对象
3.再次通过hash值，定位到Segment当中数组的具体位置。

由此可见，和hashmap相比，ConcurrentHashMap在读写的时候都须要进行二次定位。先定位到Segment，再定位到Segment内的具体数组下标。

为什么ConcurrentHashMap和hashtable都是线程平安的，然而前者性能更高呢？

因为前者是用的分段锁，依据hash值锁住对应Segment对象，当hash值不同时，使其能实现并行插入，效率更高，而hashtable则会锁住整个map。

并行插入：当cmap须要put元素的时候，并不是对整个map进行加锁，而是先通过hashcode来晓得他要放在那一个分段（Segment对象）中，而后对这个分段进行加锁，所以当多线程put的时候，只有不是放在同一个分段中，就实现了真正的并行的插入。

留神：在统计size的时候，就是获取ConcurrentHashMap全局信息的时候，就须要获取所有的分段锁能力统计（即效率稍低）。

分段锁设计解决的问题：
目标是细化锁的粒度，当操作不须要更新整个数组的时候，就仅仅针对数组中的一部分行加锁操作。

ConcurrentHashMap为何不反对null键和null值？

HashMap是反对null键和null值，而ConcurrentHashMap却不反对
查看源码如下：
HashMap:

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

ConcurrentHashMap:

    /** Implementation for put and putIfAbsent */final V putVal(K key, V value, boolean onlyIfAbsent) {        if (key == null || value == null)  throw new NullPointerException();        int hash = spread(key.hashCode());        int binCount = 0;        ......}

起因：通过get(k)获取对应的value时，如果获取到的是null，此时无奈判断它是put（k,v）的时候value为null，还是这个key素来没有做过映射（即没有找到这个key）。而HashMap是非并发的，能够通过contains(key)来做这个判断。而反对并发的Map在调用m.contains（key）和m.get(key),m可能曾经不同了。

HashMap1.7和1.8的区别？

1.为了放慢查问效率，java8的HashMap引入了红黑树结构，当数组长度大于默认阈值64时，且当某一链表的元素>8时，该链表就会转成红黑树结构，查问效率更高。
2.优化扩容办法，在扩容时放弃了原来链表中的程序，避免出现死循环

红黑树:一种自均衡二叉树，领有优良的查问和插入/删除性能，广泛应用于关联数组。比照AVL树，AVL要求每个结点的左右子树的高度之差的绝对值（均衡因子）最多为1，而红黑树通过适当的放低该条件（红黑树限度从根到叶子的最长的可能门路不多于最短的可能门路的两倍长，后果是这个树大抵上是均衡的），以此来缩小插入/删除时的均衡调整耗时，从而获取更好的性能，而这尽管会导致红黑树的查问会比AVL稍慢，但相比插入/删除时获取的工夫，这个付出在大多数状况下显然是值得的。

ConcurrentHashMap1.7和1.8的区别？

1.8的实现曾经摈弃了Segment分段锁机制，利用Node数组+CAS+Synchronized来保障并发更新的平安，底层采纳数组+链表+红黑树的存储构造。

CAS：
CAS，全称Compare And Swap（比拟与替换），解决多线程并行状况下应用锁造成性能损耗的一种机制。java.util.concurrent包中大量应用了CAS原理。
JDK1.8 中的CAS:
Unsafe类，在sun.misc包下，不属于Java规范。Unsafe类提供一系列减少Java语言能力的操作，如内存治理、操作类/对象/变量、多线程同步等。其中与CAS相干的办法有以下几个：

//var1为CAS操作的对象，offset为var1某个属性的地址偏移值，expected为期望值，var2为要设置的值，利用JNI来实现CPU指令的操作public final native boolean compareAndSwapObject(Object var1, long offset, Object expected, Object var2);public final native boolean compareAndSwapInt(Object var1, long offset, int expected, int var2);public final native boolean compareAndSwapLong(Object var1, long offset, long expected, long var2);

CAS毛病：

  • ABA问题。当第一个线程执行CAS操作，尚未批改为新值之前，内存中的值曾经被其余线程间断批改了两次，使得变量值经验 A->B->A 的过程。

解决方案：增加版本号作为标识，每次批改变量值时，对应减少版本号；做CAS操作前须要校验版本号。JDK1.5之后，新增AtomicStampedReference类来解决这种状况。

  • 循环工夫长开销大。如果有很多个线程并发，CAS自旋可能会长工夫不胜利，会增大CPU的执行开销。
  • 只能对一个变量进原子操作。JDK1.5之后，新增AtomicReference类来解决这种状况，能够将多个变量放到一个对象中。