论坛 › 数据结构与算法 › HashSet的存储分析

cx1521126332 发表于 2019-2-22 17:23:30

HashSet的存储分析

一、问题的发现:(以下代码可直接复制测试)
                在做斗地主洗牌的时候我们发现在一个新的HasSet中添加1-52,打印HasSet时输出也是1-52
                Set hashSet = new HashSet();
                      for (int i = 1; i <= 52; i++) {
                            hashSet.add(i);
              }
              System.out.println(hashSet);//
二、问题的提出:
        问题1.不是说HashSet是无序吗?
                解:HashSet的无序是体现在''存放''的顺序和''取出''的顺序可能会不一样;
                        Set hashSet = new HashSet();
                              hashSet .add(3);
                        hashSet .add(2);
                        hashSet .add(17);
                      System.out.println(hashSet);//
                        看这就无序了,那为什么会这样呢
        问题2.HashSet到底是如何存放数据的?
                第一步:我们得先看一下HashSet的数据结构是什么样子的;
                                在jdk1.8之前:HashSet结构=数组结构+链表结构;
                                在jdk1.8之后包括1.8:HashSet结构=数组结构+链表结构;
                                                                HashSet结构=数组结构+红黑树结构(当链表长度>=8);
                第二步:
                        每次数据存放的位置是:()数据的hasCode()值) 取余(数组长度 )=余数,该余数就是放在数组对应的索引上面
                                2.1:那万一余数相同怎么办?
                                                如果没有重写equals()方法:则比较地址值,地址值相同则不存;否则以链表的形式存取
                                                如果重写了equals()方法:则比较内容值,内容值相同则不存;否则以链表的形式存取
                                2.2:那初始的数组长度是多少?
                                                新建的HashSet初始数组长度是2*4=16;
                                                每当hasSet.length>数组长度*0.75时,为保证能存下所有数据数组的长度会翻一倍2*5=32,HashSet的数据结构会重建,之后再刚刚提到的方式进行数据重新排序;
                                3.3:那hashCode()值如何计算?
                                                调用hashCode()方法打印就可以看到;
                                                String类源码较为复杂(我也没看懂)总结为:
                                                        public static int getStringHasCode(String str){
                                                              char[] chars = str.toCharArray();//{0,0}
                                                              int hasCode = 0;
                                                              for (int i = 0; i < chars.length; i++) {
                                                                            hasCode = 31*hasCode + chars;//48,48*31+48
                                                                      }
                                                              return hasCode;
                                                                    }

cx1521126332 发表于 2019-2-22 17:26:14

本帖最后由 cx1521126332 于 2019-2-22 17:32 编辑

HashSet存取数据流程.png

cx1521126332 发表于 2019-2-22 17:27:06

本帖最后由 cx1521126332 于 2019-2-22 17:32 编辑

HasSet的数据结构.png

荣耀 发表于 2019-2-24 17:16:51

{:10_265:}

liuzhengyuan 发表于 2020-7-28 10:10:02

鱼币

liuzhengyuan 发表于 2020-7-28 10:10:43

鱼币

心驰神往 发表于 2020-10-30 16:54:50

鱼币

心驰神往 发表于 2020-10-30 16:55:33

{:10_269:}

yobdc 发表于 2021-8-25 09:58:53

学习

yobdc 发表于 2021-8-25 10:03:00

学习

bwzxhjy 发表于 2021-8-26 08:20:11

学习学习{:10_256:}{:10_256:}{:10_256:}

yobdc 发表于 2021-8-26 11:19:35

学习

别吃我饼干 发表于 2021-12-30 17:01:41

{:10_279:}

别吃我饼干 发表于 2021-12-30 17:02:23

{:10_266:}

别吃我饼干 发表于 2021-12-30 17:02:56

没有

别吃我饼干 发表于 2021-12-30 17:04:04

{:10_256:}

别吃我饼干 发表于 2021-12-30 17:07:29

{:10_260:}

别吃我饼干 发表于 2021-12-30 17:08:44

{:10_258:}

别吃我饼干 发表于 2021-12-30 18:43:20

没有了

别吃我饼干 发表于 2021-12-30 18:44:03

{:10_261:}

查看完整版本: HashSet的存储分析