黑马程序员技术交流社区

标题: 深入了解HasSet中的链表结构 [打印本页]

作者: NBoss 时间: 2016-9-6 23:55
标题: 深入了解HasSet中的链表结构
今天老师讲了HashSet这个集合，听了一下解决哈希冲突方法，就是有一个单向链表，计算哈希值之后会把计算好的值放在链表中，然后有重复的哈希值会在已有的哈希值上再连接一个链表，如图

当时我就不理解链表里为空的是什么，为什么会有空的值，然后就各种查资料，最后查到源代码中HashSet底部维护了一个HashMap，而这个HashMap底部又维护了一个默认长度为16的数组，所以没有插入的地方就是null
还有就是对这个链表又有了深入的了解，HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket 里存储的不是一个哈希值，而是一个哈希值链，系统只能必须按顺序遍历每个哈希值链，直到找到想搜索的哈希值为止——如果恰好要搜索的哈希值位于该哈希值链的最末端（该哈希值是最早放入该哈希值中），那系统必须循环到最后才能找到该元素。

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个默认长度为16的数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

作者: 1185573341 时间: 2016-9-7 00:05
可以的写的很详细加油

作者: NewBeeCoder 时间: 2016-9-7 00:08
可以的研究的很透彻虽然我理解的不多

作者: MarsBong 时间: 2016-9-7 00:47
这个在数据结构中有介绍,HashMap的底层是散列表,类似于链表吧,但不全是,存储数据的时候,需要散列函数,根据散列函数的不同,来判断存放的具体位置,如果某一位置多个元素,这样就是造成了散列冲突,就会进行链表式的排列

作者: NBoss 时间: 2016-9-7 11:11
百度上对于哈希表和哈希函数有很多详解，我主要是对哈希冲突是的链式结构表有点小疑问，就查了各种资料，对于哈希函数通俗的来说就是一种算法，一种加密算法，典型的就是MD5加密，算法难免会有算出来的值一样，但原数不一样，这时就会产生哈希冲突，链式结构只是解决哈希冲突的一种方法，还有再哈希等等，就不在这里介绍了，百度有很多。

作者: NBoss 时间: 2016-9-18 22:52
自己的帖子自己顶

作者: 我就是那匹黑黑 时间: 2016-9-19 00:50

写的很详细 ,谢谢分享

作者: NBoss 时间: 2016-9-19 23:06
继续顶！！！！！！

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2