HashMap简述
HashMap 是数组+ 链表 的数据结构。时间复杂度(理想状态)O(1)。（是数组 查找时间复杂度O(1)，插入时间复杂度O(n)，链表 查找时间复杂度O(n)，插入时间复杂度O(1) 的 中庸选择）
- 链表使用一个next指针维护链表结构的，它的插入和删除的效率比较高，再插入和删除时，不用挪动后面的数据。但是查找每次都得从头结点遍历，所以效率不高
- 数组使用下标维护数据的，所以查找起来，效率会很高。插入和删除，需要移动后面的数据，效率不高。
- 所以，在只需要查找的时候，建议使用数组，而经常需要插入和删除数据，建议使用链表
HashMap主要原理
1、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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 若哈希表的数组tab为空，则 通过resize() 创建
// 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建
// 关于resize（）的源码分析将在下面讲解扩容时详细分析，此处先跳过
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算插入存储的数组索引i：根据键值key计算的hash值 得到
// 此处的数组下标计算方式 = i = (n - 1) & hash，同JDK 1.7中的indexFor（），上面已详细描述
// 3. 插入时，需判断是否存在Hash冲突：
// 若不存在（即当前table[i] == null），则直接在该数组位置新建节点，插入完毕
// 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：a. 当前位置的key是否与需插入的key相同、b. 判断需插入的数据结构是否为红黑树 or 链表
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // newNode(hash, key, value, null)的源码 = new Node<>(hash, key, value, next)
else {
Node<K,V> e; K k;
// a. 判断 table[i]的元素的key是否与 需插入的key一样，若相同则 直接用新value 覆盖 旧value
// 判断原则：equals（）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b. 继续判断：需插入的数据结构是否为红黑树 or 链表
// 若是红黑树，则直接在树中插入 or 更新键值对
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ->>分析3
// 若是链表,则在链表中插入 or 更新键值对
// i. 遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历节点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
// ii. 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
// 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
else {
for (int binCount = 0; ; ++binCount) {
// 对于ii：若数组的下1个位置，表示已到表尾也没有找到key值相同节点，则新建节点 = 插入节点
// 注：此处是从链表尾插入，与JDK 1.7不同（从链表头插入，即永远都是添加到数组的位置，原来数组位置的数据则往后移）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 插入节点后，若链表节点>数阈值，则将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 树化操作
break;
}
// 对于i
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 更新p指向下一个节点，继续遍历
p = e;
}
}
// 对i情况的后续操作：发现key已存在，直接用新value 覆盖 旧value & 返回旧value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 替换旧值时会调用的方法（默认实现为空）
return oldValue;
}
}
++modCount;
// 插入成功后，判断实际存在的键值对数量size > 最大容量threshold
if (++size > threshold)
resize();
afterNodeInsertion(evict);// 插入成功时会调用的方法（默认实现为空）
return null;
}
- 首次table数组为null，调用resize方法，生成一个
默认16大小的数组 - 对 Entry（Node） key的hashCode()做hash，并计算在储蓄数组中的index
- 存储时，判断hash冲突，如果当前index没有值（即当前table[i] == null），直接存value。
- 否则，代表hash冲突。
- 1、如果当前key与需存储key相同（equals），覆盖当前value。
- 2、判断存储的数据是红黑树 或 链表
- 若是链表,则在链表中插入 or 更新键值对
- 遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历节点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
- 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
- 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
2、get
public V get(Object key) {
Node<K,V> e;
// 1. 计算需获取数据的hash值
// 2. 通过getNode（）获取所查询的数据
// 3. 获取后，判断数据是否为空
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 计算存放在数组table中的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 4. 通过该函数，依次在数组、红黑树、链表中查找（通过equals（）判断）
// a. 先在数组中找，若存在，则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// b. 若数组中没有，则到红黑树中寻找
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// c. 若红黑树中也没有，则通过遍历，到链表中寻找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- bucket里查找节点，命中返回
- 如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。
3、resize
存储键值时，发现容量不足，需要扩容，生成一个当前 2倍 的新数组。
/**
* 分析4：resize（）
* 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量 = 长度
int oldThr = threshold;// 扩容前的数组的阈值
int newCap, newThr = 0;
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若无超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通过右移扩充2倍
}
// 针对情况1：初始化哈希表（采用指定 or 默认值）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结
HashMap 采用数组和链表的方式解决hash冲突，（Java 8 添加红黑树）。允许存储null。
hashmap流程图
参考：
动态扩容问题详见： HashMap扩容
扩展
LinkedHashMap
基本和HashMap实现类似，多了一个链表来维护元素插入的顺序，因此维护的效率会比HashMap略低。但是因为有链表的存在，遍历效率会高于HashMap。
get()操作后，会把当前数据移动到链表尾部。所以基于这个属性，可以实现 Lru缓存
详见：
ConCurrentHashMap
结构图
线程安全，而且采用分段锁的方式进行数据同步，因此相对于Hashtable来说，效率要高。但是因为引入了段的概念，所以ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部，因此效率会低于HashMap。不过在多线程情况下，这种性能的牺牲换取数据安全是非常值得的。因此在多线程的情况下应该首选ConcurrentHashMap。（HashMap ConCurrentHashMap 对比）
SparseArray
private int[] mKeys;//int 类型key数组
private Object[] mValues;//value数组
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
SparseArray 如果不设置置顶容量大小，会默认初始一个 容量10 的大小内容。
内部通过 两个数组 来存储数据，一个存储key，一个存储value。key 只支持int类型，避免了装箱
put get 时，都会使用二分查找。所以在数据量大的情况下性能并不明显，将降低至少50%
扩容 当currentSize(当前存储的值的个数)小于等于4的时候，扩容至8，否则扩容至两倍的currentSize
所以用 SparseArray 代替 HashMap 最好是：
- 数据量不大，最好在千级以内
- key必须为int类型，这中情况下的HashMap可以用SparseArray代替
ArrayMap
public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
MapCollections<K, V> mCollections;
int[] mHashes;
Object[] mArray;
ArrayMap继承自SimpleArrayMap实现了Map接口。ArrayMap内部是两个数组（都为 空数组），一个存放hash值，一个存放键值对 key value。
put
首先就是判段key是否null，是null，hash值直接置为0，如果不为null，通过Obejct的hashCode()方法计算出hash值。然后通过indexfOf方法计算出index的值。indexfOf 内部则是使用二分查找。
扩容
如果我们的osize(已经存储的多少value个数)大于等于两倍的BASE_SIZE(常量为4)我们就在原来osize的基础上扩容0.5倍
如果我们的osize小于8(两个BASE_SIZE)并且大于4（一个BASE_SIZE），我们将数组扩容到8，否则我们将数组大小扩容到4
ArrayMap 与 HashMap 对比：
- 插入基于二分查找，效率不如HashMap
- 比HashMap占用内存少，更省空间， 时间换空间
选择使用：
- 在数据量小的时候一般认为1000以下，当你的key为int的时候，使用
SparseArray确实是一个很不错的选择，内存大概能节省30%，相比用HashMap，因为它key值不需要装箱，所以时间性能平均来看也优于HashMap，建议使用 - ArrayMap相对于SparseArray，特点就是key值类型不受限，任何情况下都可以取代HashMap，但是通过研究和测试发现，ArrayMap的内存节省并不明显，也就在10%左右，但是时间性能确是最差的，当然了，1000以内的如果key不是int 可以选择
ArrayMap
