HashMap面试题(二)
目录一、HashMap中如何计算数组下标的
static int indexFor(int h ,int length){
//
return h & (length-1);
}
为什么不对Hash表的长度直接取余而选择使用位运算得到索引呢？
首先我们就要分析HashMap中的扩容方法了解其扩容机制
//获取当前table的长度
int newCapacity = table.length;
//若长度小于目标长度，则扩展为之前的2倍
while (newCapacity < targetCapacity)
newCapacity <<= 1;
HashMap的初始容量和扩容都是以2的次方来计算的，那么将length-1将得到一个奇数，也就是换成二进制所有的位都为1，按位与的原则是全都是1，结果才是1，否则就为0.所以该方法其实等价于对length取模。那为什么不用取余来计算呢，因为位运算，是计算机最底层的运算，所以效率要比取余高不少。
二、JDK1.7中rehash的底层是怎样实现的
rehash顾名思义重新计算hash值那么在什么时候才需要重新计算hash值呢，首先我们需要了解一个initHashSeedAsNeeded方法
initHashSeedAsNeeded方法
/*查看initHashSeedAsNeeded函数，返回值是switching，switching取决于 currentAltHashing ^ useAltHashing;这是个异或运算，currentAltHashinghashSeed = hashSeed != 0;hashSeed默认为0，因此currentAltHashinghashSeed默认为false;boolean useAltHashing = sun.misc.VM.isBooted() &&(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);前部分为true,后部分取决于Holder.ALTERNATIVE_HASHING_THRESHOLD。
*/
final boolean initHashSeedAsNeeded(int capacity){
//hashSeed默认情况下为0
boolean currentAltHashing = hashSeed ! =0;
boolean useAltHashing =sun.misc.VM.isBooted() &&
//关键在于传进来的数组的容量
(capacity >=Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching =currentAltHashing ^ useAltHashing;
if(switching){
hashSeed =useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0 ;
}
return switching;
}
Holder方法
/*
ALTERNATIVE_HASHING_THRESHOLD = threshold;
threshold = (null != altThreshold)? Integer.parseInt(altThreshold): ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
因此threshold又取决于altThreshold和ALTERNATIVE_HASHING_THRESHOLD_DEFAULT，
前者altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));可以理解为你可以配置虚拟机参数如-D jdk.map.althashing.threshold=3，不配置就为null
后者ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;整数最大值
因此不配置altThreshold的时候，threshold为Integer.MAX_VALUE;整数最大值，这个时候ALTERNATIVE_HASHING_THRESHOLD=Integer.MAX_VALUE;整数最大值，再回到上面(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);一定为false， boolean switching = currentAltHashing ^ useAltHashing;中的useAltHashing为false,currentAltHashing默认为false,switching就为false,就不会初始化hashseed，也不会重新计算hash。
如果配置altThreshold的时候，ALTERNATIVE_HASHING_THRESHOLD=threshold=配置的值，(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD)如果成立，就为true,boolean switching = currentAltHashing ^ useAltHashing;中的useAltHashing为true,currentAltHashing默认为false,switching就为true,就会初始化hashseed，也会重新计算hash。
*/
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
本质是什么呢，其实就是看你是否想要初始化hashseed，默认为零的，如果你要初始化hashseed,就要设置虚拟机参数，然后rehash才会有可能发生。
rehash的好处是什么呢，在扩容转移数据的时候，rehash后，重新计算的索引值就会变化概率更大，链表就有可能拆散分到数组上去，这样就加强了查询的效率。
三、HashMap中的modCount是什么意思
首先我们要知道modCount代表的就是修改次数的意思，put()，get(),remove()方法都是在修改次数
由于HashMap不是线程安全的,所以在迭代的时候,会将modCount赋值到迭代器的expectedModCount属性中,然后进行迭代, 如果在迭代的过程中HashMap被其他线程修改了,modCount的数值就会发生变化, 这个时候expectedModCount和ModCount不相等, 迭代器就会抛出ConcurrentModificationException()异常
四、多线程情况下HashMap为什么会出现线程不安全
HashMap的线程不安全主要体现在下面两个方面：
1.在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。
2.在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。
JDK1.7中的线程不安全
在JDK1.7中，扩容数据时要进行把原数据迁移到新的位置，使用的方法：
//数据迁移的方法，头插法添加元素
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
//以下三行是线程不安全的关键
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这段代码是HashMap在JDK1.7的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点。
将关键的几行代码提取出：
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
2、扩容造成死循环和数据丢失
假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作：
正常扩容后的结果是下面这样的：
但是当线程A执行到上面transfer函数的第11行代码时，CPU时间片耗尽，线程A被挂起。即如下图中位置所示：
此时线程A中：e=3、next=7、e.next=null
当线程A的时间片耗尽后，CPU开始执行线程B，并在线程B中成功的完成了数据迁移
重点来了，根据Java内存模式可知，线程B执行完数据迁移后，此时主内存中newTable和table都是最新的，也就是说：7.next=3、3.next=null。
随后线程A获得CPU时间片继续执行newTable[i] = e，将3放入新数组对应的位置，执行完此轮循环后线程A的情况如下：
接着继续执行下一轮循环，此时e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环，结果如下：
此时没任何问题。
上轮next=3，e=3，执行下一次循环可以发现，3.next=null，所以此轮循环将会是最后一轮循环。
接下来当执行完e.next=newTable[i]即3.next=7后，3和7之间就相互连接了，当执行完newTable[i]=e后，3被头插法重新插入到链表中，执行结果如下图所示：
上面说了此时e.next=null即next=null，当执行完e=null后，将不会进行下一轮循环。到此线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，当在以后对该HashMap进行操作时会出现死循环。
并且从上图可以发现，元素5在扩容期间被莫名的丢失了，这就发生了数据丢失的问题。
JDK1.8中的线程不安全
上面的扩容造成的数据丢失、死循环已经在在JDK1.8中已经得到了很好的解决，如果你去阅读1.8的源码会发现找不到HashMap#transfer()，因为JDK1.8直接在HashMap#resize()中完成了数据迁移。
为什么说 JDK1.8会出现数据覆盖的情况？ 我们来看一下下面这段JDK1.8中的put操作代码：
其中第六行代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
除此之前，还有就是代码的第38行处有个++size，我们这样想，还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的zise大小为10，当线程A执行到第38行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。
标签：面试题,HashMap,next,THRESHOLD,线程,threshold,HASHING From： https://www.cnblogs.com/rito-blog/p/16900223.html