HasMap 是最早出现是JDK1.2，到1.7的版本都没大的太大的变化，
? JDK1.7 --- JDK1.8 有很大改动
? * jdk1.7的存储结构是数组+链表*
? HasMap 是非线程安全的，也就是说在多个线程对HasMap 中的某个元素进行crud操作时，是不能保证数据的一致性。
首先是把元素一个个放在数组中，后面存放的数据元素越来越多，于是就出现了链表，对于数组中的每一个元素，都有一条链表来存储元素。
后面因为存储的元素越来越多，链表也越来越长。这样查找元素的时候效率不但没有提高反而下降了（链表不适合查找，适合增删）
数组：采用一段连续的存储单元来存储数据 ，对于指定下标的查找，时间复杂度为0（1）；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度为0（n）；
? 查询快、插入慢
链表是 一种物理存储单元上非连续的、非顺序的存储结构，
? 插入快，查找慢
jdk1.8就把链表变成了一个适合查找的树形结构，就是红黑树。
**** 不是红黑树就就一定效率高，只有在链表长度不小于8，而且数组长度不小于64的时候才讲链表转换成红黑树 ****
那为什么不把整个链表编程红黑树？也可以说为什么等到链表的长度大于8时，才将链表转化为红黑树？
1 红黑树是一个特殊的平衡二叉树，查找的时间复杂度是 O(logn) ；而链表查找元素的时间复杂度为 O(n)，远远大于红黑树的 O(logn)。红黑树的查询效率很高。
2 构造红黑树要比构造链表复杂的多，再在链表的节点不是很多的时候，从整体性能来看，数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。杀鸡用牛刀，过度张扬。
3 HasMap 频繁的扩容，就会造成底部的红黑树不断地进行拆分重组，非常耗时，即只有链表很长的时候才转换为红黑树。
? 放置元素put HasMap
public class Test {
/**
* 测试HasMap
*/
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>();
//存储第一个元素
hashMap.put("Shang",18);
System.out.println(hashMap);
}
}
详解：
HashMap<String, Integer>
? String----->键 Integer----->值 键值对
put源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put内部调用的是putVal方法
putVal源码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
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)
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 {
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;
}
}
//第三部分三小节四小小节
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//第四部分
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
第一个参数，调用hash方法计算hash值
第二个参数key，即键值对的键
第三个参数是value
第四个onlyIfAbsent，也就是键相等时，不修改已存在的值
第五个 evict 要是为false，那么数组就处于创建模式中，所以一般为true
?
1
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4 参数：initialCapacity 初始容量 参数：loadFactor 负载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) //如果初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始容量超过最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
//则使用最大容量作为初始容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果负载容量小于等于0或者不是数字，则抛出异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//把负载因子赋值给成员变量loadFactor
this.loadFactor = loadFactor;
// 调用tableSizeFor方法计算出不小于initialCapacity的最小的幂的结果,
// 并赋值给成员变量threshold
this.threshold = tableSizeFor(initialCapacity);
}
英语不好的人看的我真是一脸懵逼，不过好在大概意思还能明白。看第三行Poisson_distribution这不就是泊淞分布嘛。而且最关键的就是
当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。
1 在访问方式上
数组可以随机访问其中的元素
链表则必须是顺序访问，不能随机访问
2 空间的使用上
链表可以随意扩大
数组则不能
数组:
优点：使用方便 ，查询效率 比链表高，内存为一连续的区域
缺点：大小固定，不适合动态存储，不方便动态添加
链表：
优点：可动态添加删除 大小可变 ，内存可能是不连续内存，链式存储。
缺点：只能通过顺次指针访问，查询效率低
原文：https://www.cnblogs.com/ShangStudyJava/p/14717592.html