欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java:集合类的数据结构

程序员文章站 2022-09-27 20:35:07
Java的集合其实就是各种基本的数据结构(栈,队列,hash表等),基于业务需求进而演变出的Java特有的数据结构(因为不仅仅是基本数据结构)。现在,我们以数据结构的视角来看看Java的集合到底是什么样子。并分析他们的性能。 ......

Java:集合类的数据结构

本文源自参考《think in java》,多篇博文以及阅读源码的总结

前言

java的集合其实就是各种基本的数据结构(栈,队列,hash表等),基于业务需求进而演变出的java特有的数据结构(因为不仅仅是基本数据结构)。现在,我们以数据结构的视角来看看java的集合到底是什么样子。并分析他们的性能。

一 java集合体系

java的集合体系分为两类,collection接口和map接口

主要分为三种:

  • set。无插入顺序的不重复数据集接口(集合演变而来)
  • list。有插入顺序的数据集接口(队列演变而来)
  • map。key-value的键值对数据集接口(hash表演变而来)

其中set和list继承自collection接口,map则就是map接口。

接口中都定义了一些基本增删改查的方法。

具体继承体系如下图:

Java:集合类的数据结构

基本可以从名字知道集合的内部数据结构。

  • 看后缀,有set,list,map后缀的集合,代表着该集合的基本结构,所以会具有以上所说的特性。
  • 看前缀,前缀往往代表着该数据结构的具体实现方式。一般有这几种:
    1. hash或者array,代表着以哈希(基本)数组实现的数据结构。
    2. linked,代表着集合内各个数据之间存在链表关系。
    3. tree或者sorted,代表着内部使用红黑树实现了排序。(需要提供comparator或者实现comparable)

下面大略说下每个集合的数据结构,懒得贴源码了。

1.1 list

最常用的list就是arraylist和linkedlist了,在此不讨论并发的list集合。
讨论下底层源码对它们的具体实现。

1.1.1 arraylist

使用java的基本数组实现的动态数组集合,源码底层维护着list的容量与实际长度

因为使用的基本数组,不像哈希数组一样需要考虑哈希碰撞问题,因此负载因子默认为1。当list数组容量不够时才进行扩容,扩容的倍数为1.5倍

通过arrays.copyof方法,返回复制的新数组。arrays.copyof底层调用的system.arraycopy方法。而在arraylist初始化时,如果不指定初始数组长度,在jdk1.6之后默认初始长度为0,在jdk1.6之前则默认为10。在jdk1.6后,arraylist在第一次扩容时,如果扩容长度不足10,则会直接扩容到10。

具体集合怎么使用就不废话了。

1.1.2 linkedlist

这是一个双向链表,其中节点用的是linkedlist的内部类。和数据结构中的链表差不多。可以用它实现栈和队列。

1.1.3 arraylist与linkedlist比较

很明显,arraylist是某种程度上的哈希表,适合随机读,但是不适合在集合中间插入和删除(会造成后续数据的位移)。
而linkedlist适合在头尾部插入删除,不适合随机读。

值得一提的是arraylist随机读的时间复杂度是o(1),linkedlist是o(n)。而arraylist在中间插入和删除的时间复杂度是o(n),linekdlist在中间插入删除时间复杂度也是o(n)

可以明显看出来arraylist在插入删除上和linkedlist理论上所用的时间是一个级别的,但是arraylist慢于linkedlist是因为在修改集合后需要进行其他数组数据的移动,而linkedlist则是查找节点花费了o(n),不需要额外移动数据,所以在同样数据量时,linkedlist进行数据修改优于arraylist。

1.2 map

最常用的map就是hashmap和treemap。

1.2.1 hashmap

hashmap是底层用哈希数组实现的map。hashmap就是一个个entry(key-value键值对)存储在一个哈希数组上(entry是hashmap的内部类)。

哈希数组的使用不可避免的需要考虑哈希碰撞问题,常用的解决方案有:

  • 拉链法
  • 再哈希法
  • 开放地址法
  • 建立公共溢出区。

在jdk里,使用的就是拉链法解决的哈希碰撞问题,因此每个哈希数组上的数组元素(又被称为桶——bucket),都是一个链表的表头。这样基本保证了hashmap的平均查找时间是o(1)。

hashmap的负载因子为0.75

但是当出现频繁哈希碰撞时,会导致某个链表过长进而导致了查找时间会趋近于o(n)。对此jdk原本的解决方案是设置负载因子为0.75。当哈希表总负载量达到0.75时,就会进行扩容,扩容为原本的2倍。这样当数据平均下来后,不太容易出现过长的链表(因为扩容会分解链表重新放入桶中)。

但是这并没有解决特殊情况下查找效率的问题,只是让这种特殊情况更难以出现了。

jdk1.8中 hashmap出现了红黑树

因此在jdk1.8中又做出了改进,当某个桶中的链表的长度大于8时。链表会重构成一个红黑树。这样保证了hashmap的最坏时间复杂度也仅仅是o(logn)。同时负载因子引起的扩容也保证了红黑树的重构不会频繁发生,不会因为频繁建树导致过多的性能开销。

hashmap的初始化与扩容

另外值得一说的就是hashmap在不知道初始长度进行初始化时,jdk1.6前默认长度为16,jdk1.6后默认长度为0。基本在jdk1.6中,需要初始化底层容器的集合都做出了这种优化。不会提前构造底层容器造成开销,会等到使用时才进行底层的初始化。

而hashmap默认长度设置为16,并且每次扩容都是2倍。这是为了方便底层的哈希数组进行取模时的运算,可以把取模的除法运算改写成位移运算,提升性能。

并且在jdk1.8中,hashmap关于取模运算还做了另一个优化。在jdk1.8之前,每次哈希数组扩容时,链表里的数据都会再次进行哈希运算。而在jdk1.8后,不需要再进行运算了,只需要在每个桶中选择一半数据往后移动oldlength位就行(oldlength是集合在扩容前的容量)。

1.2.2 treemap

而另一个常用的map——treemap,底层就是用java写了一个红黑树,感觉没什么好说的。有兴趣的可以回去翻翻数据结构的书。

1.2.3 linkedhashmap

hashmap的每个node还会以插入顺序相互关联成为双向链表。

1.3 set

set主要是sortedset和hashset。打开源码一看,分别new了一个treemap和hashmap,然后把数据存在了key里。嗯,这就是set的底层实现了。