转载需要时立即联系
HashSet的基础使用一种称为哈希表的数据结构。 值得一提的是，Java在HashSet内部使用HashMap存储元素(将整个元素设置为key )。
内部结构JDK 7概述
JDK 8
在JDK 7版本中，哈希表在数组+链表上实现。 每个链表都称为“铲斗”。 插入对象时，必须确定其在表格中的位置。 首先，必须计算该对象的哈希值，并获取桶的总数和剩余数。 实际上不准确，稍后再详细说明。 余数是对象在哈希表中的位置索引。 如上图中的白色桶所示，如果桶为空，则可以将对象直接插入到相应索引的桶中。 如果桶已满(如上图中的彩色桶)，则必须将该对象与桶中的所有对象进行比较，以确定该对象是否已经存在。 如果所有比较都不存在，则添加到桶中，并在JDK 8版本中通过数组+链表+红黑树改进了哈希表实现。 如果桶频繁散列碰撞，链表的长度会非常长，然后新对象必须按顺序比较桶中的所有对象，从而降低性能需要很长时间。 因此，如果桶中包含的对象数超过8个，JDK 8就会将此链表转换为红黑树进行存储。 在上图的黑色水桶上所示。 这大大减少了新对象在桶中的比较次数，并提高了性能
如果可以估计插入到整个初始时段数initial capacity哈希表中的元素总数，则可以指定时段数的初始值。 在Java中，如果在构建时未指定初始值，则为默认值16； 如果指定初始值，则使用最接近指定初始值的2的幂，因为Java使用的桶数是2的幂。 也就是说，初始值为18，实际上用32初始化。 初始值为32，实际上用32初始化。 ）
Note:一些研究者认为，虽然没有足够的证据，但建议将桶数设置为素数
加载因子加载因子并不总是估计哈希表中的元素总数； 另一方面，即使当时可以预料到，在很多情况下，由于未来状况的变化，散列表中的元素总数大幅增加，散列表的性能也开始下降。 必须从中进行重新散列，创建桶数更多的新哈希表，将原始哈希表中的所有元素重新插入新哈希表，然后销毁原始哈希表。 这里计算被占满桶数/桶数，并将其与装填因子3358www.Sina.com/进行比较。 当当前人百分比达到负载系数设置时，系统将使用新哈希表自动重新哈希，该哈希表是当前哈希表中桶数的两倍。 这是因为Java使用的桶数都是2的幂。 在Java中，默认值为load factor，如果元素中嵌入了哈希表中75%以上的桶，则会重新散列
在源代码分析的tableSizeFor方法中，如上所述，如果在HashSet构造函数中指定了桶数的初始值，JDK将确定该值是否为2的幂，如果是，则使用指定的初始值。 否则，它将自动与下一个最近的平方对齐，并使用该值初始化。 通过在构造函数中调用tableSizeFor方法完成上述平方的对齐操作
分析JDK 11的源代码实现
本节首先简要介绍Integer.numberOfLeadingZeros方法。 此方法返回参数二进制文件(存储在计算机上的二进制文件是补码)的前导零个数。
源代码的形参cap是为构造函数指定的初始值桶数，在此分为两种情况进行讨论。
cap为2的幂：使其二进制具有x位的有效数字，其中第x位为1，第x-1位~第1位为0； cap-1的二进制变为x-1位的有效数字，第x-1位~第1位均为1；
从上图容易看出Cap-1的前导零的个数为33-x。 -1的二进制数(补数)从第32位到第1位全部为1，将其无符号向右移动33-X时为n )。
最后，进行n 1操作，从下图可以看出，得到的结果与前面提到的形参Cap一致，为平方
cap不是2的幂：假设其二进制中有x位有效数字。 其中，如果第x位为1，则在第x-1位~第1位一定存在1，所以容易理解cap-1二进制仍然是x位的有效数字，第x位为1；
从上图容易看出Cap-1的前导零的个数为32-x。 -1的二进制数(补数)在第32位~第1位全部为1，将其无符号向右移动32-X时为n )。
最后，进行n 1操作，从下图可以看出，得到了与前面提到的形参Cap最接近的下一个平方的结果
桶位置索引的计算
如上所述，链表数组中元素的位置计算是使用元素的哈希值和时段总数完成的。 其实这个表达不准确。
现根据JDK 11给出准确的解释：下述代码中通过位运算完成元素哈希值hash与桶总数n取余后用于确定桶位置索引i，十分巧妙且效率高。n表示总桶数,hash可以暂时理解就是元素的哈希值。前文已经说明，在Java中，由于其总桶数n均为2幂，其二进制应该为100...00，则n-1后，恰好变为11...11，则正好为n余数的低位掩码，此时再将n-1与hash做位与计算后，其结果正好就是 hash%n
i = (n - 1) & hash;但是上述方法的缺陷也很明显，即指只考虑了hash值的低x位(余数掩码位)，这样对于那些高位有差异，而在余数掩码位一致的元素而言，将大大增加其哈希冲突的可能性。为此，Java设计了一个如下的扰动函数:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }将 元素的哈希值h 与 哈希值h无符号右移16位后 进行XOR异或操作 得到一个新的hash值，然后再用新哈希值hash与总桶数n求余来确定最后元素所存放的桶的位置索引 对元素哈希值h进行扰动计算，其通过简单高效的位运算实现将原哈希值h中的高位和低位信息进行融合，尽可能提高了低位信息的随机性，以降低发生冲突的可能性
rehash时新位置的计算在JDK 11 中当需要进行rehash将调用resize()进行自动扩容，其中关于扩容后新位置的计算很巧妙，现结合扩容前后的图解进行分析说明，如前文所述，图中hash均为原哈希值经过扰动后的值
桶位置索引的计算前文提到，关于元素在链表数组中的位置计算，是用元素的哈希值与桶总数取余得到。其实这种表述并不准确。现根据JDK 11给出准确的解释：
下述代码中通过位运算完成元素哈希值hash与桶总数n取余后用于确定桶位置索引i，十分巧妙且效率高。n表示总桶数,hash可以暂时理解就是元素的哈希值。前文已经说明，在Java中，由于其总桶数n均为2幂，其二进制应该为100...00，则n-1后，恰好变为11...11，则正好为n余数的低位掩码，此时再将n-1与hash做位与计算后，其结果正好就是 hash%n
i = (n - 1) & hash;但是上述方法的缺陷也很明显，即指只考虑了hash值的低x位(余数掩码位)，这样对于那些高位有差异，而在余数掩码位一致的元素而言，将大大增加其哈希冲突的可能性。为此，Java设计了一个如下的扰动函数:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }将 元素的哈希值h 与 哈希值h无符号右移16位后 进行XOR异或操作 得到一个新的hash值，然后再用新哈希值hash与总桶数n求余来确定最后元素所存放的桶的位置索引 对元素哈希值h进行扰动计算，其通过简单高效的位运算实现将原哈希值h中的高位和低位信息进行融合，尽可能提高了低位信息的随机性，以降低发生冲突的可能性
rehash时新位置的计算在JDK 11 中当需要进行rehash将调用resize()进行自动扩容，其中关于扩容后新位置的计算很巧妙，现结合扩容前后的图解进行分析说明，如前文所述，图中hash均为原哈希值经过扰动后的值
通过上图，可以看出发生扩容后余数掩码位比扩容前多了一位(Java中，扩容为当前容量的下一个2幂)，所以： - 如果hash的第X位为0，即 $a_x = 0$ , 则 $index2 = index1$ ，扩容后该元素的位置保持不变； - 如果hash的第X位为1，即 $a_x = 1$ , 则为 $index2 = index1 + cap$ ，扩容后的位置该元素的位置为原位置和原容量大小之和
所以在resize的源码中可以看到其通过(cap & hash)实现判断hash的第X位是否为1： - 与结果为0，则第X位为0； - 与结果为1，则第X位为1；
扩容后新位置计算的伪代码如下:
if( cap & hash ) { newIndex = oldIndex + oldCap; } else { newIndex = oldIndex; } HashSet 方法HashSet 提供了多种情况下的构造函数:
public HashSet(); // 构造一个空哈希表 public HashSet(int initialCapacity); // 构造一个指定桶数的空哈希表 // 构造一个指定桶数，指定装填因子的空哈希表 public HashSet(int initialCapacity, float loadFactor); // 构造一个哈希表，并将集合c 中的所有元素添加到该哈希表中 public HashSet(Collection<? extends E> c); 特点 底层使用哈希表实现元素不可重复排列无序（准确说，应该是其不保证有序。迭代器在遍历HashSet时，大多情况下是无序的，但也可能由于巧合，使其输出恰好为有序，这也是允许的。所以你的程序不应该依赖这个巧合的有序情况，而应该按照无序这种普适的情况进行处理）存取速度快线程不安全