文字版HashSet底层

随便说说，大家当看个乐

new了一个HashSet后，调用了HashMap方法，创建了一个table，大小是16，往里面添加数据时

1. 会先得到添加进来的数据的hashCode值，通过一个算法，将hashcode转为一个int，这个int是用来决定放在table的哪一个位置的

2. 也就是说现在已经确定了这个加进来的数据，应该放在空的table表的哪个位置，加进来就完事了

3. 那万一，我有另一个数据，它的hashcode通过算法计算得出的int，和刚才一样，那也就是说这个新的数据，也要放到刚才已经被占用的位置，那怎么办呢

4. 那我用equals,判断一下他们是不是同样的内容，注意这里的equals，程序员可以自定义判定两个元素之间相同的判断条件，简单说就是我可以自己决定，如果元素里面的哪个内容是相同的，那么这2个元素就是相同的，举个简单的例子，有2个dog对象，一个叫jack,一个叫mary，他们有毛色设个属性，他们毛色相同，那么我重写equals方法，他们虽然是2条狗，但是他们相同，如果是同样的内容，我就不加了，如果不一样，那就加到这个元素的后面，形成一个链表

5. 那假如我现在有很多数据，要添加到这个hashset中，16个不够用怎么办呢？在java8中，hashset有这么个机制，新创建的table有16个空间，目前形态是数组，假如我现在不同的添加数据进去，当第12个数据加到这里之后会对table表进行扩容，扩容多大呢？扩容成2倍大小，那新表是16，第一次扩容后就变32了，那为什么到12会扩容，而不是别的数字呢？因为有一个扩容因子，这个因子说白了是一个float类型的固定值 = 0.75 ，table表里面的数据增加到多少，就扩容，是由这个0.75决定的，当表的大小*0.75个数据放进这个表之后，就会开始扩容，注意！当到达这个临界值就会扩容，而不是过了这个临界值才会扩容

6. 那假如我现在运气贼好，我要添加的数据，通过哈希值得到的应该存放到表的下标位置都一样，那是不是就表示，这个table里面只有1条很长的链表呢？是的，没错，这条链表会很长很长，但是链表太长了，那么学过数据结构的朋友都知道，一个链表太长，对查找操作而言是非常麻烦的一件事，所以高司令(java作者)决定，当这条链表的长度达到8，且table的大小大于等于64的时候，将这个链表转为一棵红黑树

7. 哎那我上面说table表的大小是16，那我表里面的单个链表的大小长度达到8了，但是table是16啊，还没到64呢，那会发生什么呢？当链表长度达到8，但是table大小还是16 的时候，表会扩容到32，也就是说，当第8个数据被添加到链表之后，数组从原来的16个大小变成了32，此时，虽然链表有8个节点，但是并没有转换成红黑树的数据结构，那我再加一个数据到链表之后呢？table才32，会再次扩容到64，也就是说链表里已经有9个节点了，但是它仍然是单链表结构，只不过table扩容成了64，那么现在，转换成红黑树的条件已经达到了：链表节点有8个，table大小大于等于64，当再次添加一个节点到这个链表之时，这条链表就变成红黑树的结构了

写的有点乱，但是我自己看的懂，如果观众朋友们看不懂，可以看

【零基础 快速学Java】韩顺平 零基础30天学会Java_哔哩哔哩_bilibili