前言
HashMap，应该所有java程序员都用过这个集合，是平时中很常用的一个集合。大部分人都知道怎么用它，也知道它不是线程安全的，HaspTable才是线程安全的。但很多人只是极限于此。并不知道Haspmap里面的构造是怎么样的，也不知道haspmap为什么线程不安全。所以我们今天就来看看HaspMap的源码构造吧。
HashMap的类结构
可以看出，HashMap的结构是竖直方向是数组，横向就是链表的存储方式。数组的存储方式在内存的地址是连续的，大小固定，一旦分配不能被其他引用占用。它的特点是查询快，时间复杂度是O(1)，插入和删除的操作比较慢，时间复杂度是O(n)，链表的存储方式是非连续的，大小不固定，特点与数组相反，插入和删除快，查询速度慢。HashMap是介于两者之间，算是一种小优化吧。
构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
可以看到hashmap的构造函数有3种。
1.HashMap(int initialCapacity, float loadFactor)可以指定初始化容量和扩容因子，里头做了容量的判断，最小是4，不能大于1>>30.扩容因子默认是0.75
2.HashMap(),创建一个空的HashMap，容量为4，扩容因子0.75
3.HashMap(Map<? extends K, ? extends V> m) 将一个map的数据赋值给当前的hashmap，我们来看看里面两个方法
/**
* 当HashMap为空的时候初始化当前HashMap
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
//下一次扩容的大小为当前容量*扩容因子
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];//构建一个容量大小的数组
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
inflateTable(int toSize),里面通过roundUpToPowerOf2(toSize)方法找到一个比number大的2的倍数，这里面解释一下threshold这个变量，这个变量是当hashmap的里面的数据达到这个容量的时候，就会开始扩容了，一般这个变量的值是当前容量 * 扩容因子，即capacity * loadFactor。最后创建一个当前容量的数组。
putAllForCreate(m)这个方法就是讲参数中map的值赋值给hashmap。这里面我们先不说它是怎么找到hashmap位置然后赋值的。后面讲put的时候再说。
put的原理
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//当前HashMap为空
inflateTable(threshold);//初始化HashMap，此时会构建好table[]、容量和扩容值
}
if (key == null)//HashMap支持null作为key
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//当前链表中没有指定key的节点，新建一个节点并且添加到链表当中
addEntry(hash, key, value, i);
return null;
}
/**
* 当添加到HashMap中的键值对的key为null的时候
* @param value key为null对应的value
* @return 如果当前是覆盖操作，返回被覆盖的原来的value，否则为null
*/
private V putForNullKey(V value) {
//可以看到key为null的时候，默认hash为0
//先遍历table[0]的链表，看是否需要覆盖
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//如果当前节点key为null，直接覆盖value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//否则新建一个节点并且添加到链表当中
return null;
}
/**
* 新建一个节点并且添加到指定的链表的头部
* @param hash 需要添加的key的hash值
* @param key 需要添加的节点的key
* @param value 需要添加的节点的value
* @param bucketIndex 需要添加到table[]的下标
*/
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);
}
//新建节点并放在放在table[bucketIndex]链表的头部，大小+1
createEntry(hash, key, value, bucketIndex);
}
/**
* 扩容操作
* 当HashMap添加数据的时候发现已经到了扩容标准
* 则进行扩容
* @param newCapacity 当前希望的新的容量
*/
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 当进行扩容的时候，需要将旧的table[]数据转移到当前新的table[]上面
* @param newTable 扩容后新建的table[]
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;//扩容后的大小
//遍历旧的table[]，将旧的节点转移到新的table[]中
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这里总结一下put的流程。
1.首先判断key是否为空，为空的时候会走putForNullKey(value)这个方法，这个方法会遍历table[0]的链表，遍历的时候，发现有节点的key为null，会覆盖当前节点的value值。遍历完后发现没有key为null，会创建一个节点并添加到当前链表中。
2.看看新建节点这个方法。addEntry(int hash, K key, V value, int bucketIndex)，这个方法一开始会判断是否需要扩容，如果需要扩容，则会直接将原数组的容量扩充2倍，然后通过transfer(HashMapEntry[] newTable)将原hashmap里面的值重新赋值给新数组，transfer这个方法里面会通过indexFor方法重新计算所有值得数组下标值然后重新放置。最后重新计算threshold 这个临界值。
2.key不为null，则计算key的hash值，然后通过indexFor(hash, table.length)这个方法计算得到数组的下标位置。看看indexFor方法
static int indexFor(int h, int length) {
return h & (length-1);
}
这里介绍一下这个方法，这个方法就一行代码，很简单。
举个例子
1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。加入换成不是2的倍数，得出来的重复性就会很大，很可能多个值都集中在一条链表上面。这显然不符合Hash算法均匀分布的原则。
3.找到数组的下标位置后，如果发现当前key已经存在当前链表中，会替换原来key对应的value值。否则通过
addEntry(hash, key, value, i)方法将当前值插入到链表的头结点。
4.modCount值会加一，等会解释modCount这个值的用意。
get的原理
/**
* 从HashMap中获得指定key对应的value
* @param key 需要查找的key，支持null
* @return value，没有的话为null
*/
public V get(Object key) {
if (key == null)//key为空，直接查找table[0]即可，相对于getEntry节省了indexFor的开销
return getForNullKey();
Map.Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Map.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;
}
get就比较简单了，判断key是否为null，如果为null，走getForNullKey这个方法，这个就是在table[0]这个链表中获取key为null的value值，之前我们put的时候是有放置的。
如果key不为null，走getEntry(Object key)，这个方法很放置的原理差不多，根据key通过indexFor找到数组的下标位置。然后在当前下标的链表中找到key值相同的value。
总结
1.可以看到hashmap的put和get操作都是有比较多的遍历列表的操作。这是有点损耗性能。
2.haspmap在计算数组下标时会尽量避免hash冲突，使值尽可能的均匀分布在各个链表中。解决Hash的冲突有以下几种方法：
1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列
2. 再哈希法
3. 链地址法
4. 建立一 公共溢出区
而HashMap采用的是链地址法。
3.HaspMap不是线程安全的，在多线程高并发的情况下会有问题。ConcurrentHashMap就是为了解决这个问题而提出的。
