HashMap扩容机制、线程安全
1.容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // HashMap初始容量大小(16)
static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量
transient int size; // The number of key-value mappings contained in this map
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子
HashMap的容量size乘以负载因子[默认0.75] = threshold; // threshold即为开始扩容的临界值
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // HashMap的基本构成Entry数组
Entry基本构成
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
..........
}
2.
当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。
这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。
（1）放入值put()
【不同版本的jdk,HashMap源码不同,机制类似】
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null总是放在数组的第一个链表中
int hash = hash(key);//求取哈希值
int i = indexFor(hash, table.length);
//遍历i位置的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key在链表中已存在，则替换为新value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;//返回old值
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e,是Entry.next,实现链表结构
//如果size超过threshold，则扩充table大小。再散列
if (size++ >= threshold)
resize(2 * table.length);//默认扩容为原来的2倍
}
（2）确定数组位置index
HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；算法如下：
/*
* Returns index for hash code h.
*/
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的n次方,"length must be a non-zero power of 2";则下面的等式成立，
h & (length-1) = h % length 等值不等效 h & (length-1)的效率高于h % length
按位取与，作用上相当于取模mod或者取余%。hashCode不同也可能数组下标相同。
为什么HashMap的容量或之后的扩容，总是2的n次方?
这看上去很简单，其实很巧妙。
假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：
h & (table.length-1) hash table.length-1
8 & (15-1)： 0100 & 1110 = 0100
9 & (15-1)： 0101 & 1110 = 0100
-----------------------------------------------------------------------------------------------------------------------
8 & (16-1)： 0100 & 1111 = 0100
9 & (16-1)： 0101 & 1111 = 0101
-----------------------------------------------------------------------------------------------------------------------
**从上面的例子中可以看出：当8、9两个数和(15-1)2=(1110)进行“&运算”的时候，产生了相同的结果，都为0100，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。
**同时，我们也可以发现，当数组长度为15的时候，hash值会与(15-1)2=(1110)进行“&运算”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
**而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1(这是一个奇妙的世界)，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。
**所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
***********************************************************************************
（3）HashMap的resize（rehash）：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果当前的数组长度已经达到最大值，则不在进行调整
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据传入参数的长度定义新的数组
Entry[] newTable = new Entry[newCapacity];
//按照新的规则，将旧数组中的元素转移到新数组中
transfer(newTable);
table = newTable;
//更新临界值
threshold = (int)(newCapacity * loadFactor);
}
//旧数组中元素往新数组中迁移
void transfer(Entry[] newTable) {
//旧数组
Entry[] src = table;
//新数组长度
int newCapacity = newTable.length;
//遍历旧数组
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置
e.next = newTable[i];//实现链表结构，新加入的放在链头，之前的的数据放在链尾
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
*******************************************************************************************************************
1.HashMap线程不安全
public static final HashMap<String, String> map = new HashMap<String, String>();
public static void main(String[] args) throws InterruptedException {
//线程1
Thread t1 = new Thread(){
public void run() {
for(int i=0; i<25; i++){
map.put(String.valueOf(i), String.valueOf(i));
}
}
};
//线程2
Thread t2 = new Thread(){
public void run() {
for(int i=25; i<50; i++){
map.put(String.valueOf(i), String.valueOf(i));
}
}
};
t1.start();
t2.start();
Thread.currentThread().sleep(1000);
for(int i=0; i<50; i++){
//如果key和value不同，说明在两个线程put的过程中出现异常。
if(!String.valueOf(i).equals(map.get(String.valueOf(i)))){
System.err.println(String.valueOf(i) + ":" + map.get(String.valueOf(i)));
}
}
}
HashMap源码
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，
然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。
2.synchronizedMap线程安全
Map m = Collections.synchronizedMap(new HashMap(...));
更好的选择：ConcurrentHashMap
java5中新增了ConcurrentMap接口和它的一个实现类ConcurrentHashMap。
ConcurrentHashMap提供了和Hashtable以及SynchronizedMap中所不同的锁机制。
Hashtable中采用的锁机制是一次锁住整个hash表，从而同一时刻只能由一个线程对其进行操作；
而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶，诸如get,put,remove等常用操作只锁当前需要用到的桶。
这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。
上面说到的16个线程指的是写线程，而读操作大部分时候都不需要用到锁。只有在size等操作时才需要锁住整个hash表。