大佬求教，知道 HashMap 的实现又能如何？

最近看了一些 java 的面经，公司都喜欢问 HashMap 的实现，我想知道，知道了实现又能如何？

这是 java1.8 的实现。

比如：1.计算数组索引时，

if ((p = tab[i = (n - 1) & hash]) == null)  
	tab[i] = newNode(hash, key, value, null);

n = 2 的 k 次幂，用的是掩码取低 k 位找 index, 而不是最常用的 hash%n 找 index.

2.它的容量大小总是 2 的 k 次幂, 以配合上面的取索引。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

3.单条链表长度大于 8 时，转换为红黑树。

 //链表长度大于 8 转换为红黑树进行处理
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
     treeifyBin(tab, hash);

4.扩容的时候不用重新计算新数组 index.只可能在原 index 的位置，或者 index * 2 的位置。

// 原索引放到 bucket 里
if (loTail != null) {
	loTail.next = null;
	newTab[j] = loHead;
}
// 原索引+oldCap 放到 bucket 里
if (hiTail != null) {
	hiTail.next = null;
	newTab[j + oldCap] = hiHead;
}

用的时候还不是假定 get 操作是 O(1)时间复杂度。比如我在刷 leetcode 的时候，只把它当作 O(1)时间能取东西的容器，不会考虑它的扩容啊，计算索引的小技巧之类的东西。

大家学 Hash 的时候不都是看算法书，了解原理。

了解这些小技巧对平时用 HashMap 的时候会有什么帮助呢？

知道了实现真的有用吗？或者到底那些面试官想问什么呢？求大佬指教。

eltonto187

2018-04-25 11:56:38 +08:00

@lhx2008 首先感谢你，你的几个问题我有所思考，但都不是张口就能说出来。

首先 hash 碰撞攻击，以前没听过，刚看了下。自定义类重写 hashcode()和 equals()不是常规操作嘛，现在的实现链表长度大于 8 就会转为红黑树，即使都撞到一个桶里也是 O(lgn)吧。

两个内容相同的对象，不重写 hashcode()返回的内存地址啊，在 hashmap 里存不同位置。

hashmap 线程不安全的，线程安全的用 ConcurrentHashMap, 任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap.

eltonto187

2018-04-25 13:47:47 +08:00

@honeycomb 大佬，首先我学习 hash 的原理是看的算法 4。hash 就是数组索引为键，解决冲突用链表，拉链法。或者把链表链到数组里，也就是开放寻地址。

然后，面试官直接问 hash 的原理就好了，为什么要看过源码呢？假设面试官问我源码（还没有面试机会，意淫一下）他是想听上面提到的 trick 呢，还是想更深一层的，比如初始容量为什么要是 16，为什么解决冲突用拉链法而不用开放寻地址法。

要是问原理呢，我是知道的，要是问上面的实现细节呢，现在是知道的，估计过不了过不了多久就忘了，要是问更深层次的源码为什么这么做，我是不知道的，源码也没有写。

是不是我读源码 get 的点不对，不是读细节，而是要再往深挖