hashMap作为一个典型的数据结构，之前或多或少都了解一些，这一次就详细的看一下它管理hashshu以及（链表、红黑树），对阈值的管理扩容，以及hashmap在多线程里面存在的非线程安全。
在jdk1.7和1.8hashMap的实现稍有变化，对应于android里面的sdk25 26；从我们熟知的数组+链表，变成了数组+链表或者红黑树。红黑树的作用查找方便，从链表从头结点往下找的O(N)变成O(lgn)；
由于sdk25的hashMap不含红黑树的操作，所以这个相对简单一些，从这个入手。
构造函数：
hashMap主要是3个参数 初始容量 负载因子 阈值
初始容量决定初始阈值，当前节点数量>阈值*负载因子时会触发扩容，扩容很耗时
通常我们使用时 Hashmap map = new HashMap();
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
static final int DEFAULT_INITIAL_CAPACITY = 4;
会使用默认的容量 4，负载因子0.75；
在sdk26里面默认值是16和0.75；
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
put:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//hash方法 根据key获取hash值，尽量使值散列在低位
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//位运算取余数 也就是hash值位于哪个hash桶
int i = indexFor(hash, table.length);
//遍历这个链表，如果有hash值相同且key相等的则值替换为新值，并且返回旧值
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//从这里可以联想到为什么重新obj的equals时 也要重写hash方法
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果这个链表没有，则说明之前没有put过多对应的，需要新加一个进去
modCount++;
addEntry(hash, key, value, i);
return null;
}
从上面的代码和注释可以看到通过对key进行hash运算得到hash值，然后取余拿到Index。如果index对应的链表存在了，则更新key对应的value；如果没有则需要addEntry，并返回null表示不存在相同的值。
hash运算暂时不用深究，可以知道的是，hash出来的hash值必然是尽量散列在低位的，因为Index是根据取余求出来的。如果不同的key都散列在高位，低位基本不变，必然导致index冲突非常严重，hash碰撞。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
因为length是2的次方（主要由扩容的逻辑保证），length-1在二进制必然是11....11的形式，与运算也相当于求余了，计算机运算得更快一些。
addEntry:
addEnty在put新元素的时候调用。因为在sdk25里面元素叫做hashMapEntry的原因吧。在26里面称为Node；不过貌似也只是换了个名字，也是继承map.entry ，变量及方法都一样。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
因为涉及到新加元素了，所以要判断一下是否要扩容了，如果不需要扩容，就直接加到链表里面去。
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
//可以看到是放入到链头
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
可以看到添加到链表的逻辑，实际上是把新加的元素作为node，它的next指向之前的node，也就是每次新加的其实是加到链表的表头，而不是链尾巴哦。可能是觉得
如果addEntry的时候发现当前的size已经到阈值了，这时候就要扩容了resize;
resize:
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//hashMapEntry数组变成两倍，只是元素需要重新计算index；
//因为如果之前的长度0-15 在index=0位置的0、16、32、48这些就不会都在index=0这个位置了
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
//在两倍长的数组里重新计算index
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
如代码注释扩容时重新计算index，以及所有元素在新的数组的位置。看到这个操作把所有的元素都检查了一遍，对比查找get的遍历单个链表（红黑树上耗时更低），这个transfer确实是非常耗时了。
在sdk26 put方法多了检查当前节点是否是树节点的操作，如果是红黑树的结构，就是通过树查找。而且熟悉树的都知道，树的查找速度快大部分是因为维护树比较麻烦，所以红黑树扩容更加麻烦。
get:
如果put的逻辑搞懂了，get就是超级简单了
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
通过key得到hash值，取余得到index；遍历查找key和hash都相等的，如果没有就返回空。
hashmap非线程安全
在多线程并发的情况下，比如多个线程都在put,addEntry 当前的头结点是preNode，线程的结果新加一个node在链头，但是大家都以为之前的头结点是preNode，然后 newNode.next = preNode，那么必然导致其他同时在操作的线程的结果被覆盖掉。
在resize扩容的时候，如果一个线程先扩容完成了，第二个线程再扩容，但是里面的table已经变成了扩容后的，这些都是会引起问题的，比如链表死循环的问题。
如何解决这个问题呢？线程同步的问题，我们可以用同步手段处理。但是Java提供了更有效的ConcurrentHashMap。
