Map接口：
----HashMap：Map主要实现类，线程不安全，效率高，存储null的key和value
----LinkedMap：保证遍历map元素时，可以根据添加顺序实现遍历，和LinkedSet原理相似，频繁遍历效率高
----TreeMap：保证添加的key-value对进行排序，实现排序遍历，对key进行自然排序和定制排序,key必须同一个类创建对象
----HasTable：古老实现类，线程安全，效率低，不能存储null的key和value
----Properties：常用处理文件，key和value都是String类型
HashMap底层原理：
当实例化一个HashMap时，系统会创建一个长度为16的Entry数组，数组中存放元素的位置称为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。每个bucket中存储一个Entry对象，其中Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。而且新添加的元素作为链表的head。
hashmap中的定义的结构：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
初始容量为2的n次幂原因：
1.方便进行与运算。
2.在进行扩容后方便数据的移动。
HasMap源码分析（1.8）：
hashmap中含有四种构造方法如下：
//可以在源码看出，当new一个hashmap对象时，构造方法底层并没有进行数组的创建。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hashmap定义的常量参数：
//数组初始化容量16，必须为2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，如果有参数的构造函数隐式指定了更高的值，则使用。必须是2的n次幂<=2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//构造函数中未指定时使用的默认负载因子，负载因子的大小决定了HashMap的数据密度。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//转为红黑树时的阈值，即树化时的阈值,该值大于2，至少应为8
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
作为调整非树化(红黑树转链表)时的数组容器阈值，必须小于树化阈值，并且最多为6作为树网拆解阈值。
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh(网格，匹配，适合) with shrinkage(收缩量) detection(发现) under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
数组容器树化时最小链表节点容量（否则，如果数组容器中的节点太多，则会改变节点的大小）应至少为 4*TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
hashmap中的put方法源码：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//创建一个空数组(hash表)引用
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//当数组为空时，调用resize方法进行初始化，创建数组对象
n = (tab = resize()).length;
//此时n值为默认16，因此此时换算二进制为1111与运算和取模运算达到效果一致，但是效率远高于取模。
//2的n次幂原因：与运算代替模运算
//通过hash值进行散列分布
if ((p = tab[i = (n - 1) & hash]) == null)
//将对象放入空数组中
tab[i] = newNode(hash, key, value, null);
//当该数组中含有元素对象时
else {
Node<K,V> e; K k;
//如果新放置的key值等于原key值
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);
//若新放置key值不等于原key值
else {
//在前数组元素中进行尾插链表的形式，循环插入
for (int binCount = 0; ; ++binCount) {
//当该元素下一个节点为null时
if ((e = p.next) == null) {
//new一个新的节点
p.next = newNode(hash, key, value, null);
//当节点数大于等于7时
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;
}
}
//1.当key值一样时将原有的value值进行覆盖
//2.当key值不同时，将新的value 值放入新创建的节点中或者是hash表(数组)中。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//模加一
++modCount;
//当hash表长度大于吞吐临界值时，进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
在给定哈希表的索引处替换数组容器中的所有链表节点，当表太小，则将改为调整大小。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果当前tab为null或者该hash表(即该数组长度)小于64时，不进行树化，而是进行resize方法
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
/**
初始化或2倍扩容。如果为空，则根据字段阈值中保留的初始容量目标进行分配。否则，因为我们使用的是二次幂展开， 所以每个数组容器中的元素要么保持在同一索引中，要么在新数组容器中以二次幂偏移量移动
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//当hash表中扩容后新的容量小于64，且老容量大于等于16，则吞吐临界值×2=24
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
//初始化数组默认长度16
newCap = DEFAULT_INITIAL_CAPACITY;
//第一次扩容时设置数组扩容时的吞吐临界值为12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将设置吞吐临界值赋给全局阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建一个容量为16的数组，扩容时也是在此步创建一个新的扩容后的hash表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//赋给全局数组对象
table = newTab;
//将老hash表中的值数据迁移到新hash表中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//数据迁移时临时存储节点
Node<K,V> e;
//当老hash表索引处中没有节点存在，将其赋给用于临时存储的节点e，并将该索引下hash表中的元素 置为空。
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//进行散列后存储e中数据到新hash表中
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//当老hash表中索引处存在节点时，扩容后新hash表多出散列值，因此原有的hash表中链表节点 需要重新分配，如原hash表长度16，扩容32，本来key值为17存放在原hash表1索引节点处，而新 hash表存储在17索引处。
else {
//储存低位处节点
Node<K,V> loHead = null, loTail = null;
//存储高位处节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//下移
next = e.next;
//判断该节点属于低位处节点还是高位处节点
if ((e.hash & oldCap) == 0) {
//低位处节点时，且尾节点loTail为空会将老hash表中索引处头节点存放到头节 点loHead处
if (loTail == null)
loHead = e;
//否则存放到loTail的下一个节点
else
loTail.next = e;
loTail = e;
}
//存放高位处节点在hiHead和hiTail处
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
//直到该索引处没有节点
} while ((e = next) != null);
//将高低位处节点重新分配到新的hash表中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扰动函数源码：
//计算key.hashCode（）并将哈希的高位（XOR）扩散到低位。由于该hash表使用2次幂作为掩码，因此仅在当前掩码上方的位上变化的哈希集将始终发生冲突(在已知的例子中有一组在小表格中保持连续整数的浮点键。）因此我们应用了一种向下扩展高位影响的变换。在速度、实用性和位扩展质量之间存在一种折衷。因为许多常见的散列集已经被合理地分布（因此不能从散播中受益），而且因为我们使用树来处理容器中的大量冲突，所以我们只是以最便宜的方式对一些移位的位进行异或，以减少系统损失，以及合并最高位的影响，否则由于表边界，这些最高位将永远不会用于索引计算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//设计原因:
//1.将高位移到低位尽可能降低 hash 碰撞，越分散越好；
//2.算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
添加元素的过程：
JDK7:
向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到)，哈希值经过处理后，得到在底层Entry[]数组中要存储的位置i。如果位置i上没有元素，则entry1直接添加成功。如果位置i上已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次比较entry1中key和其他的entry。如果彼此hash值不同，则直接添加成功。如果hash值不同，继续比较二者是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素。扩容为原有2倍。
jdk8：
? 数组+链表（JDK7）
? 数组+链表+红黑树（JDK8）
? Map中key是无序，不可重复的 —key所在的类需要重写equals和hashCode
? Map中value是无序，可重复的 （一对key-value构成一个entry对象，entry对象无序，不可重复，由Set存储）
扩容机制
吞吐临界值:扩容时的临界值threshold=12
负载因子的大小决定了HashMap的数据密度。
? 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,
造成查询或插入时的比较次数增多，性能会下降。
? 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的
几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性
能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建
议初始化预设大一点的空间。
? 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此
时平均检索长度接近于常数
红黑树：红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园 (cnblogs.com)
? https://blog.csdn.net/v_JULY_v/article/details/6105630
使用红黑树原因：红黑树时平衡了插入性能和查询性能，因此使用红黑树而不使用其他树。
死循环问题：
? 因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示：
jdk8相较于jdk7在底层实现方面的不同: .
- new HashMap():底层没有创建数组
- jdk 8底层的数组是: Node[], 而非Entry[]
- 首次调用putVal()方法时，底层创建长度为16的数组
- jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。当数组的某一个索引位置 上的元素以链表形式存在的数据个数> 8且当前数组的长度> 64，此时此索引位置上的所有数据改为使用红黑树存储。
- 在多线程情况下：1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。
做优化的原因：防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)和解决死循环问题。