黑马程序员技术交流社区

标题: Hash结构的集合底层的数据结构是什么？ [打印本页]

---

作者: 面具猴    时间: 2014-10-23 08:56
标题: Hash结构的集合底层的数据结构是什么？


再毕老师的视频中画出的哈希表底层的数据结构是数组，
但在JDK文档中有这样一段话话：


其中的桶又是什么？
在哪能找到哈希表底层数据结构的实现代码？

---

作者: qq8921310    时间: 2014-10-23 08:59
我记得好像底层、是hash表

---

作者: 面具猴    时间: 2014-10-23 11:33

qq8921310 发表于 2014-10-23 08:59
我记得好像底层、是hash表

就是这个底层的hash表是什么数据结构？
是数组、链表数组还是二维链表，或者这个桶是其他的形态。。。

---

作者: qq8921310    时间: 2014-10-23 11:49

面具猴 发表于 2014-10-23 11:33
就是这个底层的hash表是什么数据结构？
是数组、链表数组还是二维链表，或者这个桶是其他的形态。。。 ...

百度上有很详细的解释，我就不给你复制了。

---

作者: 面具猴    时间: 2014-10-24 18:05
我看了一下HashMap的源码。
其实HashMap的底层数据结构是  数组+链表  的方式，如果使用无参的构造方法，默认的初始数组长度是11，
加载因子值为0.75。也就是当HashMap中存储的元素个数大于等于 （int）11*0.75=8  时，进行再哈希。
此时，重新new出一个数组长度为2*11+1=23的数组，然后在把之前数组上的对象重新计算索引，放到新的数组上。
那么链表又是干什么的呢？
当一个元素经过计算得到的数组索引上已经有元素了，并且经过判断这个元素和此索引上的所有元素都不相同时，就把这个让数组的索引指向后来的元素，再让这个元素指向旧的元素，也就是在这个索引上形成了一个链表。
存储元素的 链 是一个Entry类型，这个类型里有一个Entry next;这么一个变量，就是用来形成链的。

---

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

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