序言
这个我随手整到的一个知识点，确实很值得深挖，我在这其中得到的知识点也远大于其本身，这一点知识让我明白了任何小知识都得深挖源码，收获太大了。
首先感谢一下带给我思路的知乎答者：https://www.zhihu.com/question/28414001
下面正式开始我的表演
首先（看结果）
以一段代码开始
package cn.mr8god.kchaptereleven;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
/**
* @author Mr8god
* @date 2020/4/22
* @time 20:37
*/
public class SetOfInteger {
public static void main(String[] args) {
Random rnd = new Random(47);
Set<Integer> intset = new HashSet<Integer>();
for (int i = 0; i < 10000; i++){
intset.add(rnd.nextInt(30));
}
System.out.println(intset);
}
}
这是一段平平无奇的，展示HashSet魅力的一段代码。代码的意思也很简单，就是让随机生成的0~29的数字存入我们的Set当中去。这里边随机了10000次，就意味着有很多很多重复的数字，当然我们大Set家族绝对不会包容两个一模一样的玩意儿，所以输出结果很是理想（单指这方面的理想），它就输出了这三十个数字
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
但是呢，结果却好像有点违背了我们所讲的“无序”，这明明是有顺序的一个一个排着输出的呀，啷个嘞就给我说成“无序”了呢？顺便展示一下概念
HashSet：一种没有重复元素的无序集合
我先来回答这个问题：我们一般所说的HashSet是无序的，但是它既不能保证存储和取出顺序一致， 更不能保证自然顺序一致（按照a-z）
顺道一提，我《Thinking in Java》书本中的输出是这样的
[15, 8, 23, 16, 7, 22, 9, 21, 6, 1 , 29 , 14, 24, 4, 19, 26, 11, 18, 3, 12, 27, 17, 2, 13, 28, 20, 25, 10, 5, 0]
现在是不是就很奇妙了，为啥我同一段代码运行出来会是两个不同的结果，一个“有序”，一个“无序“。其实按照我江某人在C++中的经验来看，这很有可能就是语言版本的问题，这边很有可能就是JDK版本的问题，于是我们来分析源码验证我的思路
然后（分析源码）
我们首先从程序的第一步——集合元素的存储开始看起，先看HashSet 的 add方法的源码：
// HashSet 源码节选-JKD8
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
我们可以看到，HashSet直接调用的是HashMap的put方法，并且将元素e放到map的key位置（保证了唯一性）
顺着线索继续查看我们的HashMap的put方法源码:
//HashMap 源码节选-JDK8
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
而我们的值在返回前需要经过HashMap中的hash方法
接着定位到hash方法的源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash方法的返回结果中是一句三目运算符，键（key）为null即返回0，存在则返回后一句的内容
(h = key.hashCode()) ^ (h >>> 16)
重点来了，这个东西叫做“扰动函数”
这个时候断一下我们再来分析一下
hashCode是Object类中的一个方法，在子类中一般会被重写，而根据我们之前自己给出的程序，暂以Integer类型为例，我们来看一下Integer中hashCode方法的源码
/**
* Returns a hash code for this {@code Integer}.
*
* @return a hash code value for this object, equal to the
* primitive {@code int} value represented by this
* {@code Integer} object.
*/
@Override
public int hashCode() {
return Integer.hashCode(value);
}
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
果然，不出所料，这边真的重写hashCode了，Integer中hasCode方法的返回值就是这个数本身
注释：其实整数的值因为与整数本身一样唯一，所以它也是一个足够好的散列值呢
这上面得出的结论就是，下面的A式和B式是等价的
A：(h = key.hashCode()) ^ (h >>> 16)
B：key ^ (h >>> 16)
over，继续回归正途，接下来就是直接进行位运算层面了
接着（转攻计算散列值——位运算开始了）
首先不急，先理清思路，这个时候
HashSet因为底层使用了哈希表（链表结合数组）实现，存储key时可以通过一系列运算后得出自己在数组中所处的位置。
我们在hashCode方法中返回到了一个等同于本身值的散列值（证明过程如“然后（分析源码）”中的“这个时候断一下我们再来分析一下”可见）。
但是呢，考虑到int类型数据的范围：-2147483648~2147483647，很明显，这些散列值不能够直接使用，因为内存是没有办法放得下一个40亿长度的数组的。所以它使用了对数组长度进行取模运算的解决方法，得余后再作为其数组下标。
在JDK7中，这个被称为indexFor()的方法就是用来做这个的。 在JDK8中，就是一句代码，其实和JDK7的一样
//JDK8中
(tab.length - 1) & hash；
//JDK7中
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length - 1);
}
顺道加一句，为什么我们取模运算不用%而用&呢？因为位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度会非常快，这样就导致了位运算&效率要比取模运算%高很多。
看到这边我们就知道了，存储时key的下标位置是需要通过hash方法和indexFor()或JDK8的类indexFor()运算得来的。
正式开始我们的位运算（&）
我们开始举个例子了
HashMap中初始长度为16，length - 1 = 15；其二进制表示为 00000000 00000000 00000000 00001111
而与运算计算方式为：遇0则0，我们随便举一个key值
1111 1111 1010 0101 1111 0000 0011 1100
& 0000 0000 0000 0000 0000 0000 0000 1111
----------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1100
上面随便举的key值就是：1111 1111 1010 0101 1111 0000 0011 1100
我们将这32位从中分开，左边16位称作高位，右边16位称作低位，可以看到经过&运算后 结果就是高位全部归0，剩下了低位的最后四位。但是问题就来了，我们按照当前初始长度为默认的16，HashCode值为下图两个，可以看到，在不经过扰动计算时，只进行与(&)运算后 Index值均为 12 这也就导致了哈希冲突
哈希冲突的简单理解：计划把一个对象插入到散列表（哈希表）中，但是发现这个位置已经被别人的对象给占据了
例子中，两个不同的HashCode值却经过运算后，得到了相同的值，也就代表，他们都需要被放在下标为2的位置
一般来说，如果数据分布比较广泛，而且存储数据的数组长度比较大，那么哈希冲突就会比较少，否则很高。
但是，如果像上例中只取最后几位的时候，这可不是什么好事，即使我的数据分布很散乱，但是哈希冲突仍然会很严重。
别忘了，我们的扰动函数还在前面搁着呢，这个时候它就要发挥强大的作用了,还是使用上面两个发生了哈希冲突的数据，这一次我们加入扰动函数再进行与(&)运算
补充 ：>>> 按位右移补零操作符，左操作数的值按右操作数指定的为主右移，移动得到的空位以零填充 ^ 位异或运算，相同则0，不同则1
可以看到，本发生了哈希冲突的两组数据，经过扰动函数处理后，数值变得不再一样了，也就避免了冲突
其实在扰动函数中，将数据右位移16位，哈希码的高位和低位混合了起来，这也正解决了前面所讲 高位归0，计算只依赖低位最后几位的情况, 这使得高位的一些特征也对低位产生了影响，使得低位的随机性加强，能更好的避免冲突
再然后
到了这里，我们一步步研究到了这一些知识
HashSet add() → HashMap put() → HashMap hash() → HashMap (tab.length - 1) & hash；
有了这些知识的铺垫，我对于刚开始自己举的例子又产生了一些疑惑,我使用for循环添加一些整型元素进入集合，难道就没有任何一个发生哈希冲突吗，为什么遍历结果是有序输出的，经过简单计算 2 和18这两个值就都是2
//key = 2,(length -1) = 15
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0000 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0000 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//2的十进制结果：2
//key = 18,(length -1) = 15
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//18的十进制结果：2
按照我们上面的知识，按理应该输出 1 2 18 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 但却仍有序输出了
这就非常苦恼了，不过我发现了一个有趣的现象，当我的代码如下时
package cn.mr8god.kchaptereleven;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
/**
* @author Mr8god
* @date 2020/4/22
* @time 20:37
*/
public class SetOfInteger {
public static void main(String[] args) {
Random rnd = new Random(47);
Set<Integer> intset = new HashSet<Integer>();
for (int i = 0; i < 3; i++){
intset.add(rnd.nextInt(30));
}
System.out.println(intset);
}
}
输出结果是
[5, 8, 13]
于是我将问题的核心转为了数组长度问题，这个就是最终的大Boss了
最后（大Boss——数组长度）
继续找到HashMap源码，我发现了一个有趣的东西
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
<< ：按位左移运算符，做操作数按位左移右错作数指定的位数，即左边最高位丢弃，右边补齐0，计算的简便方法就是：把 << 左面的数据乘以2的移动次幂 为什么初始长度为16：1 << 4 即 1 * 2 ^4 =16;
这里边有一个叫做加载因子的东西，他默认值为0.75f，这是什么意思呢，我们来补充一点它的知识：
加载因子就是表示哈希表中元素填满的程度，当表中元素过多，超过加载因子的值时，哈希表会自动扩容，一般是一倍，这种行为可以称作rehashing(再哈希)。 加载因子的值设置的越大，添加的元素就会越多，确实空间利用率的到了很大的提升，但是毫无疑问，就面临着哈希冲突的可能性增大，反之，空间利用率造成了浪费，但哈希冲突也减少了，所以我们希望在空间利用率与哈希冲突之间找到一种我们所能接受的平衡，经过一些试验，定在了0.75f
现在可以解决我们上面的疑惑了
数组初始的实际长度 = 16 * 0.75 = 12
这代表当我们元素数量增加到12以上时就会发生扩容，当我们上例中for循环添加0-18， 这19个元素时，先保存到前12个到第十三个元素时，超过加载因子，导致数组发生了一次扩容，而扩容以后对应与(&)运算的(tab.length-1)就发生了变化,从16-1 变成了 32-1 即31
我们来算一下
//key = 2,(length -1) = 31
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0011 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//十进制结果：2
//key = 18,(length -1) = 31
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0011 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0010
//十进制结果：18
当length - 1 的值发生改变的时候，18的值也变成了本身。
到这里，才意识到自己之前用2和18计算时 均使用了 length -1 的值为 15是错误的，当时并不清楚加载因子及它的扩容机制，这才是导致提出有问题疑惑的根本原因。
总结
JDK7到JDK8，其内部发生了一些变化，导致在不同版本JDK下运行结果不同，根据上面的分析，我们从HashSet追溯到HashMap的hash算法、加载因子和默认长度。
由于我们所创建的HashSet是Integer类型的，这也是最巧的一点，Integer类型hashCode()的返回值就是其int值本身，而存储的时候元素通过一些运算后会得出自己在数组中所处的位置。由于在这一步，其本身即下标(只考虑这一步)，其实已经实现了排序功能，由于int类型范围太广，内存放不下，所以对其进行取模运算，为了减少哈希冲突，又在取模前进行了，扰动函数的计算，得到的数作为元素下标，按照JDK8下的hash算法，以及load factor及扩容机制，这就导致数据在经过 HashMap.hash()运算后仍然是自己本身的值，且没有发生哈希冲突。
补充：对于有序无序的理解
集合所说的序，是指元素存入集合的顺序，当元素存储顺序和取出顺序一致时就是有序，否则就是无序。
并不是说存储数据的时候无序，没有规则，当我们不论使用for循环随机数添加元素的时候，还是for循环有序添加元素的时候，最后遍历输出的结果均为按照值的大小排序输出，随机添加元素，但结果仍有序输出，这就对照着上面那句，存储顺序和取出顺序是不一致的，所以我们说HashSet是无序的，虽然我们按照123的顺序添加元素，结果虽然仍为123，但这只是一种巧合而已。
所以HashSet只是不保证有序，并不是保证无序