对于HashMap我们一定要分成jdk1.7和jdk1.8两部分来看，我们首先来看jdk1.7的HashMap。
首先来看看几个重要的常量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认的初始值，要设置成二的整数次幂，这个等会会详细解释
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
默认最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认加载因子，我们要扩容肯定不能是已经满了再扩容，加载因子就是帮助我们确定那个值。如默认的加载因子为0.75，默认初始容量为16，因此默认会在容量为12的时候扩容，12这个值就是threshold。（时间和空间成本上提供了很好的折衷)
再来看看Entry类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）
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;
threshold = initialCapacity;
init();
}
这是HashMap的构造函数，我们可以发现，在构造函数中并没有申请任何的空间。那申请空间这一步是什么时候发生的呢？没错，就是在put方法的时候，put方法也是HashMap中非常非常重要的方法，接下来我们就详细的看一看这个put方法。
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
//此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
hash函数：
/**这是一个神奇的函数，用了很多的异或，移位等运算
对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
indexFor方法：
/**得到数组下标**/
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);
}
这里的h & (length-1)很有意思，它并没有采用取模的方式，而是采用位运算的方式，因为位运算的速度更加快。而且因为length必然是2的整数次幂，那么length-1的二进制形式必然全是1，这样就能保证Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位，这样不同的key计算得出的index索引相同的几率才会较小，数据在数组上分布也比较均匀，碰撞的几率也小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法
JDK1.8中HashMap的性能优化
JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
HashMap总结.png
1. HashMap1.7版本的死循环问题
1） Thread1和Thread2同时向hashmap中添加数据，假设Thread1获得执行权，向hashmap中插入数据的时候开始扩容，此时创建了一个新的数组，还没来得及转移旧的数据，此时Thread2执行。（此时的A -> B）
Thread1.png
2）假设Thread2开始执行之后，添加数据的时候又开始扩容，此时Thread2创建新数组并完成了所有的操作。（头插法，变成了B -> A）
Thead2开始执行.png
3）假设此时Thread1获取到执行权，那么Thread1开始执行，先把A放到新的table，在把B也放到新的table，继续读取的时候发现，在第一步的时候A是指向B的，但是经过了第二步，此时又会读取到B指向A。因此形成了循环链表，也就产生了死循环。
2. HashMap1.8版本树化和反树化的条件
树化：
- 链表长度大于等于 TREEIFY_THRESHOLD 8
- 桶数组容量大于等于 MIN_TREEIFY_CAPACITY 64
反树化： - 链表长度小于等于UNTREEIFY_THRESHOLD = 6;
3. hashmap是线程安全的吗？请解释
答：1.7和1.8都不是线程安全的。
1.7中，在resize时，转移元素的transfer方法，由于采用的头插法和直接覆盖新数组位置，在多线程情况下，有可能造成循环链表，形成死循环。
1.8中，通过尾插法和先链接到指定节点上，最后再覆盖新数组的情况，不会出现循环链表但是会有数据覆盖问题。
1.7和1.8共有的问题是，多线程情况下，线程的操作可能被覆盖或者被忽视，导致数据丢失。其余也有例如size只是采用transient修饰，并没有采用violet修饰，所以size也可能产生问题。
（补充：如果此时被问到，是否可以通过加volatile关键字保证size可以正常，是不行的，由于每次put完毕或者删除，都会对size进行自增或者自减操作，而自增或者自减操作是非原子性的，所以不行。volatile关键字只能保证被修饰的变量可以保证多线程对这个变量的可见性.i++操作,变量的写操作依赖当前值,所以不能保证线程安全）
4. HashMap为什么2倍扩容
容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！
容量为什么是2的n次幂？
索引的计算公式为h& (length-1)
- 当容量为2的n次幂时，h& (length-1)运算从数值上来讲其实等价于对length取模，也就是h%length，但是按位与比取模运算效率高。
- 能保证索引值肯定在HashMap的容量大小范围内
- (n - 1) & hash的值是均匀分布的，可以减少hash冲突
5. 加载因子为什么是0.75？
提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的时候碰撞最小。在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布。当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。也就是说，红黑树的出现概率其实也不高。
网友评论