010期JavaSE面试题十集合之Map

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

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

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

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

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

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

何时进行扩容？

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

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 同步锁，重大就义了性能，而且对并发的效率就更低了，并发汇合则通过简单的策略不仅保障了多线程的平安又进步的并发时的效率。

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（））

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

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

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

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

构造:

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

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

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 内的具体数组下标。

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

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

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

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

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 可能曾经不同了。

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

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

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 类来解决这种状况，能够将多个变量放到一个对象中。

010期JavaSE面试题十集合之Map

开篇介绍

HashMap 和 HashTable 有什么区别？

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

谈一下 HashMap 的个性？

谈一下 HashMap 的存储构造？

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

说一下 HashMap 扩容机制？

遍历 map 汇合的三种形式？

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

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

HashCode 雷同，抵触怎么办？

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

HashMap 如何判断有环形表？

介绍一下 ConcurrentHashMap？

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

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

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

HashMap1.7 和 1.8 的区别？

ConcurrentHashMap1.7 和 1.8 的区别？