Java 里 hashset 放置元素的过程，这么理解对吗？

[amiwrong123]

正在写一篇博客，但是由于还没有去看过 hashset 或 hashmap 的源码，只是自己想当然的这么理解哈希容器放置元素的过程，怕自己误人子弟啊😂

1. 放置元素时，先调用元素的 hashcode 方法，为元素找到哈希桶的位置，之后元素就会放到这个哈希桶里。
2. 此时哈希桶里可能已经有了多个元素。根据上图，两个对象 hashcode 相同，并不能得出两个对象是否为 equal 的。而哈希容器是不允许有两个 equal 的元素同时放在容器里的。所以哈希桶里的每个元素会分别和传入的元素执行 equals 比较。
3. 如果哈希桶的每个元素执行 equals 比较后，返回的都是 false，那么放入传入的元素。如果哈希桶里某个元素和传入的元素执行 equals 比较后，返回了 true，那么需要执行相应的策略（ 1.用传入元素替换掉哈希桶里既存元素 2.忽略传入元素，哈希桶里既存元素不变）。
4. 这也是为什么源码注释说，unequal 的两个对象最好是产生不同的 hashcode，因为一个哈希桶里的元素越多，需要执行的 equals 的次数就越多。

[renmu]

就是很标准的哈希表的实现，可以去看一下哈希表的 wiki

[cxtrinityy]

对倒是没啥不对，就是还要稍微深入点，第一点，数组下标是由 hashcode 和 size 通过除留余数法得出的，第二点，jdk 的实现一般在桶位上使用链表，链表内超过 8 个会转换为红黑树，以此加速相同 hash code 的查找比较，第三点，每个 key 得到不同 hashcode 这种完美散列实际情况常常难以满足，因为 jdk 的实现，数组 size 不是素数，而是 2 的幂次，方便用位操作加速下标的计算，开发编写的 hash 方法也是其中影响的一环，同时注意 load factor

[amiwrong123]

@renmu
看到这句话 A real world example of a hash table that uses a self-balancing binary search tree for buckets is the HashMap class in Java version 8.

self-balancing binary search tree 这难道就是传说中的红黑树😂

[amiwrong123]

@cxtrinityy
好吧，确实是不够深入。你说的这几点我记下，回头再继续看。你说的第三点感觉挺有意思，虽然我现在有点理解不了，哎，得看源码了。

[qwerthhusn]

你没有提到一个哈希桶里面具体是什么，
其实是一个双向链表，如果链表里面的值过多（好像是 6 还是 8 忘记了），会转化成红黑树。

[lhx2008]

差不多
@cxtrinityy 其实并不是 hashcode 直接算的，还要高低一半的位做一些运算，确保 hashcode 足够混乱