Java-HashSet

HashSet（​​参考文章​​）

HashSet 是一个 没有重复元素 ，而且 无序 （存入和取出的顺序不一定相同）的集合。

它是由 HashMap 实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。

HashSet 底层是 HashMap

添加 add 机制：

（1） 添加一个元素时，先得到 hash 值（会转化为索引值）

获取 hash 值的方法是：

<code>static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16); // ^ 异或，&gt;&gt;&gt; 无符号右移 }</code>

为什么要异或和右移，参考文章：javascript:void(0)

（2） 找到存储数据表 table ，看这个索引位置是否已经存放有元素：

若没有，直接加入；

若有，调用 equals方法比较，如果相同，则放弃添加；如果不相同，则添加到最后。

扩容机制：

扩容实际调用的方法是： resize()

（1） 第一次添加时，table数组扩容到16，临界值（threshold）是 16 * 加载因子（loadFactor）是 0.75 = 12；

（2） 如果table数组使用到了临界值12，就会扩容到16 * 2 = 32，新的临界值就是 32 * 0.75 = 24，以此类推；

<code>if (++size &gt; threshold) resize(); //这里的 size 就是插入的结点数</code>

（3）在Java8中，如果一条链表的元素个数到达 TREEIFY_THRESHOLD（默认是8），并且table的大小 &gt;= MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）,否则仍然采用数组扩容机制。

例子：假如有 12 个对象，它们的 hash值相同（转化的索引就相同），但是它们调用 equals方法显示各不相同。在 table数组上，当添加到第八个对象时，就会进行数组扩容（此时它们的索引会发生相应的改变，但还是相同），添加第九个对象时，也会进行数组扩容，这些对象仍然在同一个索引点的链表上。

由于 HashSet 是无序的，遍历方式常用的两种：

迭代器循环（快捷键 <code>itit</code>）

增强 for 循环 （快捷键 <code>集合名字.for</code>）

main方法执行的代码：

debug进去：