所谓映射便是一一对应，map英语中是[地图]的意思，这也很好的反应了映射的概念。 即：地图上的某一点都会对应现实的某一点，说是映射可谓恰到好处。Map可以说是键值对的容器，key和value一一对应，也像是根据索引查找单词。 索引当然是不能重复的。如果你发现一个字典的索引有两个[apple],你肯定会认为这个字典有问题。或者一个地图上查询两个[合肥],恐怕你也不会相信这张地图是好的。所以Map可作为Set的超集，Java中的Set集合的底层便是根据Map实现的。
Map家族一览
Map接口.png
一、永恒闪耀的明星：HashMap
作为一个多考点的类，说起HashMap总是有种神圣不可侵犯的感觉。 相关话题: 哈希碰撞相关问题：什么是哈希碰撞，如何降低哈希碰撞几率，哈希碰撞后的解决方案 HashMap底层实现问题：链表数组+红黑树数组，为什么要使用这样的数据结构 由此可以引出链表与数组的比较：效率问题，空间问题,链表的实现 由此也引出红黑树的相关问题：什么是红黑树,红黑树的特点，红黑树的翻转，红黑树与AVL树的比较
HashMap.png
来看一下HashMap的数据结构
这里是Map总结篇，所以只是简单的看一下，在HashMap精析中会详细解释 1---打开源码，可以看出内部有一个Node类，而且是单链表 2---打开源码，可以看出内部有一个TreeNode类，而且是红黑树 3---可以看到内部维护一个链表的数组，当哈希冲突时将数据插入链表尾 4---所以HashMap集数组+单链表+红黑树于一身，对数据结构而言，确实很经典。
链表节点类：可见是一个单链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
红黑树节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//可以看到内部维护一个数组链表
transient Node<K,V>[] table;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab：记录当前链表的数组
//n:当前链表的数组的长度
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)//hash:传入键的hash值
//可以看到添加元素并且没有哈希碰撞时，将元素放入数组的下一位
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 {//否则，按链表的插入，
//关于bin:就像数组里放了一个个垃圾桶(链表),来一个哈希冲突的就往里扔一个，
//所以binCount就是链表的容量
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;
}
//省略...
}
总结一下
1.HashMap会创建一个1 << 4(即16)的Node<K,V>(链表)数组，
2.当hash冲突时，该元素会插入到与其冲突的链表尾
3.当链表长度为8并且数组长度大于40时，链表转为红黑树
4.当树元素小于等于6时会解除树化，分割成链表
为什么链表要化为红黑树
单链表查询、修改、移除、尾部添加元素的时间复杂度为O(n)
红黑树查询、修改、移除、添加元素的时间复杂度为O(logn)
在数据量比较大师O(logn)的效率要比O(n)快很多(可根据数学上两种曲线比较)
红黑树这么好，为什么不直接用红黑树?
1.考虑到哈希冲突的数据不会是巨量的
2.在数据量比较少(树化阀值为8)的时候O(n)和O(logn)并无不同
3.红黑树在插入和移除时会进行额外的旋转操作,而且维护的成员变量较多逻辑较复杂，所以低数据量时反而不如单链表
二、链式哈希映射：LinkedHashMap--我有序，我骄傲
LinkedHashMap<K,V>extends HashMap<K,V>,so LinkedHashMap拥有HashMap功力 可见Entry是继承自HashMap.Node(单链表)的， Entry<K,V> before, after，说明Entry是一个双链表 由此解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题，详细原理会另开一篇
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkedHashMap.png
三、树形映射：TreeMap--我是红黑树
1----基于红黑树，由于红黑树是一种特殊的二分搜索树，所以可保证键的有序性，也可自定义排序规则 2----containsKey、get、put 和 remove 操作时间复杂度结尾O(logn)
可见节点为红黑树
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
TreeMap.png
四、哈希表：Hashtable--就让我成为历史，躲在JDK的漆黑角落。但面试官总爱挖坟...
Hashtable的老爹Dictionary这样介绍自己："NOTE: This class is obsolete"
底层数组+链表实现,无论key还是value都不能为null，
线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低
初始size为11，扩容：newsize = olesize*2+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
Hashtable.png
五、并发哈希映射：ConcurrentHashMap--我为并发而生
不是一两句话能说清的 ConcurrentHashMap锁的粒度，为对每个数组元素(Node)，Hashtable锁的粒度，为对整个数组
ConcurrentHashMap.png
最后总的比较一下
项目线程安全?实现扩容方式null键值父类
HashMap否数组+单链表+红黑树oldCap * 2允许AbstractMapHashtable是数组 + 链表oldCap * 2 + 1不允许DictionaryConcurrentHashMap是数组+单链表+红黑树oldCap * 2允许AbstractMapLinkedHashMap否数组+单链表+红黑树+双链表oldCap * 2允许HashMapTreeMap否红黑树----允许AbstractMap
后记：捷文规范
1.本文成长记录及勘误表
项目源码日期备注
V0.1--无2018-10-1Java总结之映射家族--Map概览V0.2--无--
2.更多关于我
笔名QQ微信爱好
张风捷特烈1981462002zdl1994328语言我的github我的简书我的个人网站
3.声明
1----本文由张风捷特烈原创,转载请注明 2----欢迎广大编程爱好者共同交流 3---个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 4----看到这里，我在此感谢你的喜欢与支持
转载于:https://www.cnblogs.com/toly-top/p/9781858.html
