HashMap的数据结构是怎样的？

[单选题]

JDK8之前版本，HashMap的数据结构是怎样的？

```
数组
```
```
链表
```
```
数组+链表/红黑树
```
```
二叉树
```

查看正确选项

IDEA2022.4.2

JDK8及其以后版本，HashMap的数据结构是数组+链表+红黑树

编辑于 2020-05-03 13:53:50 回复(12)

揚

HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

发表于 2019-09-15 18:57:04 回复(1)

哈哈岱伲熊

这题出的不好，jdk8以及之后才是数组+链表/红黑树，8之前应该是数组+链表的方式啊

发表于 2022-04-15 13:09:19 回复(3)

ADE_

HashMap内部包含了一个默认大小为 16 Entry 类型的数组 table,其中每个Entry 是一个链表，当链表长度大于等于 8 时会将链表转换为红黑树。

发表于 2019-09-23 23:37:09 回复(3)

人余月半子

jdk1.7 中使用个 Entry 数组来存储数据，用key的 hashcode 取模来决定key会被放到数组里的位置，如果 hashcode 相同，或者 hashcode 取模后的结果相同（ hash collision ），那么这些 key 会被定位到 Entry 数组的同一个格子里，这些 key 会形成一个链表。在 hashcode 特别差的情况下，比方说所有key的 hashcode 都相同，这个链表可能会很长，那么 put/get 操作都可能需要遍历这个链表，也就是说时间复杂度在最差情况下会退化到 O(n)

jdk1.8 中使用一个 Node 数组来存储数据，但这个 Node 可能是链表结构，也可能是红黑树结构，如果插入的 key 的 hashcode 相同，那么这些key也会被定位到 Node 数组的同个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用 treeifyBin 函数，将链表转换为红黑树。那么即使 hashcode 完全相同，由于红黑树的特点，查找某个特定元素，也只需要O(log n)的开销也就是说put/get的操作的时间复杂度最差只有 O(log n)，但是真正想要利用 JDK1.8 的好处，有一个限制：key的对象，必须正确的实现了 Compare 接口

发表于 2019-12-13 23:22:05 回复(0)

江楠201907121648656

来复习一下吧，准确的说HashMap的底层是哈希表，而Java中哈希表是由数组+链表实现的，每一个数组的节点称之为bucket桶，当桶中由多个元素就以链表的方法进行存储，当添加元素时，通过key的hash算法得出hash值，然后通过hash值映射出存在哪个桶中，如果桶中没有有元素，就添加成功，如果有元素那就代表散列冲突，比较已存在的元素和新插入的元素的hash值是否有相同，如果没有相同的则添加成功(情况1)，如果某个元素的hash值和新的元素hash值相同的，则调用key的equals方法继续进行比较，为true则新的值覆盖掉旧的值，为false添加成功(情况2)，对于情况1 和情况2，在jdk1.7是将新的元素添加到原来的头节点，jdk1.8是添加到链表后面，jdk1.8做了一个优化，因为如果链表的长度太长遍历查找复杂度为O(n)，所以引入了红黑树，当桶中的元素>8并且数组长度>64就转为红黑树，复杂度为O(logn)

发表于 2020-01-29 12:50:40 回复(0)