大佬求教，知道 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 的时候会有什么帮助呢？

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

[momocraft]

证明你可能比别人学得多懂得多 // 这是面试的目的

[eltonto187]

@momocraft 我也想知道，除去面试一说，了解这些细节对**用 HashMap**真的有帮助吗，没看之前我把它当用 get O(1)的容器，看了之后还是这样用，一点帮助也没有啊

[lhx2008]

hash 碰撞攻击怎么防范？
两个内容相同的对象，没有重写 hashcode()，进入 hashmap 会发生什么？
hashmap 线程安全吗，需要线程安全为什么不用 hashtable ？

[vegito2002]

没帮助又必须要会的东西多了去了， 平常心

[jiakme]

实际意义: 1.hashmap 扩容会 double,所以如果内存敏感,需要注意.(比如数据为 129,扩容将导致很多无效内容)内存浪费多了,性能也就差了.2.hashmap 需要指定初始值 3.了解它,也就可以了解 concurrenthashmap4.索引的技巧 5.看你是否有源码阅读习惯以及知识面的广度,如果这么简单的一个你都不看,那么肯定其他的你也看得很少.6.其他技巧,如为什么 array 前要用 transient 等等

[eltonto187]

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

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

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

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

[eltonto187]

@jiakme 感谢大佬指教，1. 扩容会 double，知道的，你说的这个数据为 129, 浪费空间，怎么解决呢，初始化传多大容量都会变成 2 的幂次方的容量啊。只要用 Hashmap 就会浪费吧。6. array 前用 transient 是为了序列化的时候少往硬盘写些内容，只存有用的，key 和 value，其他不需要存储。是这个意思吧。

[SuperMild]

面试是玄学，在 v2 这里也看到很多吐槽了，问题浅了有人说尊严受损，问题深了有人说面试造火箭上岗拧螺丝，而面试官通常也没专门研究过怎样面试才好，就拍脑袋出些题随便聊聊，何曾想求职者内心如此敏感突然就生气了呢……

[Wolfpancake]

面试如相亲，有些人要求有车有房，有些人要求身高，有些人要求颜值，都没有对错之分只是喜好罢了。

[eltonto187]

@SuperMild 大佬，我没生气，只是想知道自已看源码的姿势是不不对。
我也就是个自学编程，还没入门的人，没有面试的机会，只能对着面经撸

[agagega]

问得深点还好，特烦那种跟你就一个自己擅长但和岗位无关的问题一直聊下去最后挂掉的

[honeycomb]

@eltonto187

大部分时候和楼主知道的各种常识一样不会有某个具体的用途。

举个例子，guava cache 背后用的是 Java7 的 concurrenthashmap，有人照着 guava cache 的接口，参照了 Java8 的 concurrenthashmap 把它重写了一遍，更换了淘汰算法，做出了性能更好的 caffeine cache。

如果作者不清楚 hashmap 的实现原理，就谈不上改进它了。

[TheCure]

当然有用了, 公司需要一个分布式系统能把全站 session 存进去, 你来设计一下.

[eltonto187]

@callofmx 大佬，完全不懂，能不能给个提示？
大佬的意思是想说 hashmap 线程不安全，不能用。得用线程安全的 concurrenthashmap 吗？

[lhx2008]

@eltonto187 扩容这个，如果是 129 的话，初始化应该直接到 256，如果是 127 初始化也是 256，默认是 16，扩容上去有开销，还有就是算的时候要除上负载因子

[eltonto187]

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

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

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

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

[lhx2008]

@lhx2008 所以如果调下负载因子是可以让它的节省内存空间的

[eltonto187]

@lhx2008 大佬，你的回复好像和 @jiakme 原问题不符吧，这样虽然不用一次一次 double 上去了，可还是会浪费 127=256-129 这么多吧。 @jiakme 大佬是想引导我说出内存不足的时候用什么替换 hashmap 吧，这个我还真不到，求大佬指点

[vance]

没什么实际意义，大部份面试都是靠是这样的，你了解原理就可以了

[LukeChien]

问下 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 值再扩容
为什么？这么改动？有什么区别吗？