189 8069 5689

HashMap你了解多少

HashMap几乎是面试必问的知识，对于HashMap面试是你真的能从容面对吗？相信如果你去面试知名互联网公司的时候，决对不会只是问问你HashMap的数据结构这么简单的问题。我收集了最近老大在面试过程中关于HashMap常问的几个问题：

创新互联建站专注于企业全网营销推广、网站重做改版、鹤山网站定制设计、自适应品牌网站建设、HTML5、商城建设、集团公司官网建设、外贸营销网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为鹤山等各大城市提供网站开发制作服务。

1. 为什么HashMap是2的幂次方？

new HashMap(14);

HashMap是由数组+链表（1.8还有红黑树）来实现的，那么上面这行代码它执行后，创建的数组大小是多少呢？
追踪源码可以看到它会执行这样一个函数来返回数组大小的：

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;
}

HashMap你了解多少
图解：

  • 第一次右移并且或运算，可以保证从左到右第一位1后面再多出来一个1
  • 第二次右移并且或运算，可以保证从左到右再多出两个1
  • 以此类推，因为java中int值是4个字节，32位的，所以最后移16位的时候，足以保证2^32这种情况的出现；

  • 通过这个函数的运算，可以将我们传入的14运算得到16，也就是大于14的最小的2的n次幂。

上面说明了数组大小最后会保证是2的n次幂，那么接下来说说为什么要保证是2的n次幂

 static int indexFor(int h, int length) {
     return h & (length-1);
 }

在jdk1.7的时候，在put元素时，会执行这样一段代码片段，它的用意就是数据长度与hashCode值取余运算。那既然是取余，为什么不直接用%号呢？是因为位运算要比%运算高效很多。

那既然是&运算，又为什么非要保证length是2^n呢？
HashMap你了解多少

  • 长度是2^n-1的话，可以保证&的结果是在hash表的大小范围内；
  • &运算与%取模的结果可以保证一致；

2. 为什么HashMap的扩容因子是0.75？

加载因子是非常重要的一块，如果加载因子太大，假如为1，那么从空间利用率倒是上去了，但是时间效率就降低了。
如果加载因子太小，倒导致hashmap频繁的扩容操作，每次扩容都非常耗性能；
好吧！说了就像没说一样，关于这个问题我也只能抛砖引玉；
其实是这样的：

Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million

选择0.75是空间和时间的一个折中，也并不是说，非必须是0.75，其它的编程语言也有配置成0.72的。

3. jdk1.7扩容时是怎么产生死循环的？

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
           }
       }
   }

说起这个话题，当时在网上找博客看是真没有能看懂的，所以我尽量用图的方式来表述
HashMap你了解多少

4. jdk1.8扩容时会产生死循环吗？

Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {
                if (loTail == null)
                        loHead = e;
                else
                        loTail.next = e;
                loTail = e;
        }
        else {
                if (hiTail == null)
                        hiHead = e;
                else
                        hiTail.next = e;
                hiTail = e;
        }
} while ((e = next) != null);
if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
}
if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead;
}

看下方图文分析：
HashMap你了解多少

所以，jdk1.8中的HashMap在扩容时就不会产生死锁了！

5. 为什么是链表长度达到8时转为红黑树？

首先，TreeNode节点的占用空间的大小是链表节点的两倍，只有当容器达到8的时候才转为红黑树，为什么是8呢，在第二个问题中已经说明了，根据泊松分布可以看出，链表节点是很难达到长度为8的时候的，如果真有特殊情况达到8了，那么才将链表转为红黑树；
转为红黑树时还有个要求，就是hashMap中的元素个数达到64。

6. jdk1.8 HashMap是线程安全的吗？

JDK1.8HashMap虽然能够尽大的避免扩容时死循环问题，但是，HashMap仍然是线程不安全的，例如：线程A在put元素时，线程B进行扩容；
之所以不安全的原因是多线程会操作同一实例变化，导致变量状态不一致；


当前题目：HashMap你了解多少
文章转载：http://cdxtjz.com/article/pichop.html

其他资讯