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

[eltonto187]

最近看了一些 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]

@LukeChien 只是热场啊，我看到还有问 == 和 equals 的区别的，这个才算是热场吧，背背就好了。
问 hashmap 源码这个还得一行一行抠源码。

[otakustay]

最简单的，你能根据业务开一个初始大小，让它的 size 调整和重分配尽量少出现，但又不会因为初始大小太大浪费内存

[eltonto187]

@otakustay

大佬，初始大小开业务需要的大小就行了吧。看源码难道是让知道 initialCapacity 这个参数的意义？

再说。
大部分动态的结构重新分配的时候都是 double 吧。
StringBuilder 也是 double，不过 ArrayList 是增长一半。
我看过 Redis 的字符串实现，也是 double 的。

[fuxiaohei]

单纯 HashMap 就有很多的细节，https://www.zhihu.com/question/28119895

理解这些的前提就是熟悉源码。

[feverzsj]

hash table 本身很简单，面试这个意义不大，可以选 skip list 这种比较偏的

[eltonto187]

@fuxiaohei 感谢大佬，内容很有营养，
不过我一个初学编程的人，这么挖下去就快掉井里了。

[ipwx]

数据结构和算法是基本编程素养，就好像数学是基本科学素养。没学过初中数学的，怕是会认同“彩票中不中的概率是 1/2 “这句话吧？同理，会不会这些，写程序有根本性的思维差异。

[eltonto187]

@ipwx 大佬，你有点偏题，我问的是知道实现能如何，不是不知道原理。原理我是知道的。

[fuxiaohei]

@eltonto187 看源码更多的意义是知道有这么回事。很难保证以后会不会遇到通过原理寻找原因的问题。有一些知识增加一些方向和想法吧。

[ipwx]

@eltonto187 实现细节难道不是数据结构和算法的一部分？

[otakustay]

@eltonto187 你得知道它每一次增长是几倍啊，得知道一次增长后重分配的代价是多少啊，第 1 次增长和第 10 次增长的代价虽然是线性的但绝对资源消耗上是不一样的啊

[crossoverJie]

楼上说了很多，其实问 HashMap 就是一个切入点，如果都比较了解那么接下来就会问：

线程安全嘛？有没有线程安全的 K V ？分别是怎么实现的？ HashSet 呢？

如果第一点都聊不下去更谈不上后续的了，业务清楚的情况下其实大部分人都没问题，是要找出一定差异。

[c4f36e5766583218]

jdk7 先扩容再 put 值; jdk8 先 put 值再扩容
为什么？这么改动？有什么区别吗？