HashMap和concurrentHashMap的初始化
HashMap和concurrentHashMap的初始化
HashMap和concurrentHashMap的初始化时的区别
初始化的区别
主要分析下传入指定容量时，最后真正初始化的容量到底是多少？
HashMap的构造函数
当不指定负载因子时，负载因子为0.75
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}最终调用的都是这个HashMap(int initialCapacity, float loadFactor)方法
其中计算容量的方法为
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}都是位运算，可能不太看得懂，但是我们通过注释可以知道这么一系列位移操作算法最后是为了得到一个power of two size的值。（也就是第一个大于指定容量的值）
ConcurrentHashMap
同样的，我们不去看负载因子0.75，并发级别16这些，只关注指定容量
/**
* Creates a new, empty map with an initial table size
* accommodating the specified number of elements without the need
* to dynamically resize.
*
* @param initialCapacity The implementation performs internal
* sizing to accommodate this many elements.
* @throws IllegalArgumentException if the initial capacity of
* elements is negative
*/
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}主要的部分就是
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));sizeCtl=大于（1.5倍initialCapacity+1）的最小的2的幂次
这算出来的也就是容量，但是sizeCtl变量还有其他的含义
sizeCtl的含义
- 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
- 当为负的时候，说明表正在初始化或扩张，
- -1表示初始化
- -(1+n) n:表示活动的扩张线程
数组长度要求为2^n的原因
在存入元素的时候下标的计算方式为
index = hashcode % table.length但是a % (2^n) 等价于 a & (2^n - 1)
同时位运算比取模运算具有更高的效率，所以作者就将取模运算改为了位运算
然后计算方式就变为了
index = hashcode & (n - 1)其中n为数组长度为2的整数次幂 HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法； 这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)， hash%length==hash&(length-1)的前提是length是2的n次方；
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；
其实就是按位“与”的时候，每一位都能 &1 ，也就是和1111……1111111进行与运算