首页 / 程序员圈 / 正文
面试和开发必备,Java核心数据结构(List,Map,Set)原理与使用技巧
M1xc 发表于:2020-5-27 07:47:43 复制链接 看图 发表新帖
阅读数:27755

下载APP可以快速和圈友联系

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
先容

JDK供给了一组首要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继续自 java.util.Collection 接口,并位于 java.util 包内。

口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-1.jpg

1、List接口

最重要的三种List接口实现:ArrayList、Vector、LinkedList。它们的类图以下:

口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-2.jpg

可以看到,3种List均来自 AbstratList 的实现。而 AbstratList 间接实现了List接口,并扩大自 AbstratCollection。

ArrayList 和 Vector 利用了数组实现,可以以为,ArrayList 封装了对内部数组的操纵。比如向数组中增加、删除、插入新的元素或数组的扩大和重界说。对ArrayList大概Vector的操纵,等价于对内部工具数组的操纵。

ArrayList 和 Vector 几近利用了不异的算法,它们的唯一区分可以以为是对多线程的支持。ArrayList 没有对一个方式做线程同步,是以不是线程平安的。Vector 中绝大大都方式都做了线程同步,是一种线程平安的实现。是以ArrayList 和 Vector 的性能特征相差无几。

LinkedList 利用了循环双向链表数据结构。LinkedList 由一系列表项毗连而成。一个表项总是包括3个部分:元素内容、先驱表项和后驱表项。如图所示:

口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-3.jpg

LinkedList的表项源码:
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
不管LinkedList能否为空,链表都有一个header表项,它既是链表的起头,也暗示链表的结尾。它的后驱表项即是链表的第一个元素,先驱表项即是链表的最初一个元素。如图所示:

口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-4.jpg

下面比力下ArrayList 和 LinkedList的分歧。

1.增加元素到列表尾端

对于ArrayList来说,只要当前容量充足大,add()操纵的效力是很是高的。

只要当ArrayList对容量的需求跨越当前数组的巨细时,才需要停止扩容。扩容会停止大量的数组复制操纵。而复制时终极挪用的是System.arraycopy()方式,是以,add()效力还是相当高的。

LinkedList由于利用了链表的结构,是以不需要保护容量的巨细。这点比ArrayList有上风,不外,由于每次元素增加都需要新建Node工具,并停止更多的赋值操纵。在频仍的系统挪用中,对性能会发生一定影响。

2.插入元素到列表肆意位置

ArrayList是基于数组实现的,而数组是一块持续的内存空间,每次插入操纵,城市停止一次数组复制。大量的数组复制会致使系统性能低下。

LinkedList是基于链表实现的,在肆意位置插入和在尾端增加是一样的。所以,假如系统利用需要对List工具在肆意位置停止频仍的插入操纵,可以斟酌用LinkedList替换ArrayList。

3.删除肆意位置元素

对ArrayList来说,每次remove()移除元素都需要停止数组重组。而且元素位置越靠前开销越大,要删除的元素越靠后,开销越小。

在LinkedList的实现中,首先需要经过循环找到要删除的元素。假如要删除的元素位置处于List的前半段,则畴前往后找;若处于后半段,则从后往前找。假如要移除中心位置的元素,则需要遍历完半个List,效力很低。

4.容量参数

容量参数是ArrayList 和 Vector等基于数组的List的特有性能参数,它暗示初始数组的巨细。

公道的设备容量参数,可以削减数组扩容,提升系统性能。

默许ArrayList的数组初始巨细为10。
private static final int DEFAULT_CAPACITY = 10;
5.遍历列表

常用的三种列表遍历方式:ForEach操纵、迭代器 和 for循环。

对于ForEach操纵,反编译可知现实上是将ForEach循环体作为迭代器处置。不外ForEach比自界说的迭代器多了一步赋值操纵,性能不如间接利用迭代器的方式。

利用For循环经过随机拜候遍历列表,ArrayList表示很好,速度最快;可是LinkedList的表示很是差,应避免利用,这是由于对LinkedList的随机拜候时,总会停止一次列表的遍历操纵。

2、Map接口

Map是一种非经常用的数据结构。围绕着Map接口,最首要的实现类有Hashtable, HashMap, LinkedHashMap 和 TreeMap,在Hashtable中,还有Properties 类的实现。

口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-5.jpg

Hashtable和hashMap的区分在于Hashtable的大部分方式都做了线程同步,而HashMap没有,是以,Hashtable是线程平安的,HashMap不是。其次,Hashtable 不答应key 或 value利用null值,而HashMap可以。第三,它们在内部对key的hash算法和hash值到内存索引的映照算法分歧。

由于HashMap利用普遍,本文以HashMap为例,论述它的实现道理。

1.HashMap的实现道理

简单来说,HashMap就是将key做hash算法,然后将hash值映照到内存地址,间接获得key所对应的数据。在HashMap中,底层数据结构利用的是数组。所谓的内存地址,就是数组的下标索引。

用代码简单暗示以下:
object[key_hash] = value;
2.Hash抵触

当需要寄存的两个元素1和2经hash计较后,发现对应在内存中的同一个地址。此时HashMap又会若何处置以保证数据的完整寄存?

在HashMap的底层利用数组,但数组内的元素不是简单的值,而是一个Entity类的工具。每一个Entity表项包括key,value,next,hash几项。留意这里的next部分,它指向别的一个Entity。当put()操纵有抵触时,新的Entity会替换原本的值,为了保证旧值不丧失,会将next指向旧值。这便实现了在一个数组空间内寄存多个值项。是以,HashMap现实上是一个链表的数组。而在停止get()操纵时,假如定位到的数组元素不含链表(当前entry的next指向null),则间接返回;假如定位到的数组元素包括链表,则需要遍历链表,经过key工具的equals方式逐一比对查找。

3.容量参数

和ArrayList一样,基于数组的结构,不成避免的需要在数组空间不敷时,停止扩大。而数组的重组比力耗时,是以对其做一定的优化很有需要了。

HashMap供给了两个可以指定初始化巨细的机关函数:
HashMap(int initialCapacity)  机关一个带指定初始容量和默许负载因子 (0.75) 的空 HashMap。HashMap(int initialCapacity, float loadFactor)  机关一个带指定初始容量和负载因子的空 HashMap。
其中,HashMap会利用大于即是initialCapacity而且是2的指数次幂的最小的整数作为内置数组的巨细。

负载因子又叫做添补比,它是介于0和1之间的浮点数。

负载因子 = 现实元素个数 / 内部数组总巨细

负载因子的感化就是决议HashMap的阈值(threshold)。

阈值 = 数组总容量 × 负载因子

当HashMap的现实容量跨越阈值便会停止扩容,每次扩容将新的数组巨细设备为原巨细的1.5倍。

默许情况下,HashMap的初始巨细是16,负载因子为0.75。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final float DEFAULT_LOAD_FACTOR = 0.75f;
4.LinkedHashMap

LinkedHashMap继续自HashMap,是以,它具有了HashMap的良好特征,并在此根本上,LinkedHashMap又在内部增加了一个链表,用以寄存元素的顺序。是以,LinkedHashMap 可以简单了解为一个保护了元素顺序表的HashMap.

LinkedHashMap 供给两品种型的顺序:一是元素插入时的顺序;二是比来拜候的顺序。
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)  机关一个带指定初始容量、负载因子和排序形式的空 LinkedHashMap 实例
其中 accessOrder 为 true 时,依照元素最初拜候时候排序;当 accessOrder 为 false 时,依照插入顺序排序。默以为 false 。

在内部实现中,LinkedHashMap 经过继续 HashMap.Entity 类,实现 LinkedHashMap.Entity,为 HashMap.Entity 增加了 before 和 after属性用以记录某一表项的先驱和后继,并组成循环链表。

5.TreeMap

TreeMap可以简单了解为一种可以停止排序的Map实现。与 LinkedHashMap 分歧,LinkedHashMap 是按照元素增加大概拜候的前后顺序停止排序,而TreeMap则按照元素的Key停止排序。为了肯定Key的排序算法,可以利用两种方式指定:

(1)在TreeMap的机关函数中注入一个Comparator:
TreeMap(Comparator<? super K> comparator)
(2)利用一个实现了 Comparable 接口的 Key。

TreeMap的内部实现是基于红黑树的。红黑树是一种平衡查找树,这里不做过量先容。

TreeMap 别的排序接口以下:
subMap(K fromKey, K toKey)  返回此映照的部分视图,其键值的范围从 fromKey(包括)到 toKey(不包括)。tailMap(K fromKey)  返回此映照的部分视图,其键大于即是 fromKey。firstKey()  返回此映照中当前第一个(最低)键。headMap(K toKey)  返回此映照的部分视图,其键值严酷小于 toKey。
一个简单示例以下:
public class MyKey implements Comparable<MyKey> { private int id; public MyKey(int id) { this.id = id; } @Override public int compareTo(MyKey o) { if (o.id < this.id){ return 1; }else if (o.id > this.id){ return -1; } return 0; } public static void main(String[] args) { MyKey myKey1 = new MyKey(1); MyKey myKey2 = new MyKey(2); MyKey myKey3 = new MyKey(3); Map<MyKey,Object> map = new TreeMap<>(); map.put(myKey1,"一号"); map.put(myKey3,"三号"); map.put(myKey2,"二号"); Iterator<MyKey> iterator = map.keySet().iterator(); while (iterator.hasNext()){ System.out.println(map.get(iterator.next())); } }}
口试和开辟必备,Java焦点数据结构(List,Map,Set)道理与利用技能-6.jpg

3、Set接口

Set并没有在Collection接口之上增加额外的操纵,Set调集合的元素是不能反复的

其中最为重要的是HashSet、LinkedHashSet、TreeSet 的实现。这里不再逐一赘述,由于一切的这些Set实现都只是对应的Map的一种封装而已。

4、优化调集拜候代码

1.分手循环中被反复挪用的代码

举个例子,当我们要利用for循环遍历集应时
for (int i =0;i<collection.size();i++){ //..... }
很明显,每次循环城市挪用size()方式,而且每次城市返回不异的数值。分手一切类似的代码对提升循环性能有着积极地意义。是以,可以将上段代码革新成
int size= collection.size(); for (int i =0;i<size;i++){ //..... }
当元素的数目越多时,这样的处置就越成心义。

2.省略不异的操纵

假定我们有一段类似的操纵以下
int size= collection.size(); for (int i =0;i<size;i++){ if (list.get(i)==1||list.get(i)==2||list.get(i)==3){ //... } }
虽然每次循环挪用get(i)的返回值分歧,但在同一次挪用中,成果是不异的,是以可以提取这些不异的操纵。
int size= collection.size(); int k=0; for (int i =0;i<size;i++){ if ((k = list.get(i))==1||k==2||k==3){ //... } }
3.削减方式挪用

方式挪用是需要消耗系统仓库的,假如可以,则只管拜候内部元素,而不要挪用对应的接口,函数挪用是需要消耗系统资本的,间接拜候元素会更高效。

假定上面的代码是Vector.class的子类的部分代码,那末可以这么改写
int size = this.elementCount; Object k=null; for (int i =0;i<size;i++){ if ((k = elementData)=="1"||k=="2"||k=="3"){ //... } }
可以看到,原本的 size() 和 get() 方式被直代替换为拜候原始变量,这对系统性能的提升是很是有用的。

5、RandomAccess接口

RandomAccess接口是一个标志接口,自己并没有供给任何方式,任何实现RandomAccess接口的工具都可以以为是支持快速随机拜候的工具。此接口的首要目标是标识那些可以支持快速随机拜候的List实现

在JDK中,任何一个基于数组的List实现都实现了 RandomAccess接口,而基于链表的实现则没有。这很好了解,只稀有组可以快速随机拜候,(比如:经过 object[5],object[6]可以间接查找并返回工具),而对链表的随机拜候需要停止链表的遍历。

在现实操纵中,可以按照list instanceof RandomAccess来判定工具能否实现 RandomAccess 接口,从而挑选是利用随机拜候还是iterator迭代器停止拜候。

在利用法式中,假如需要经过索引下标对 List 做随机拜候,只管不要利用 LinkedList,ArrayList和Vector都是不错的挑选。


上一篇:连再会也没说:PHPCMS和FoosunCMS悄无声息关站
下一篇:零根本快速自学SQL,2天足矣!
温馨提示:
下载好向圈客户端可以随时随地交流学习经验,也可以和圈友发起聊天成为好友
好向圈www.kuaixunai.com是一个专业经验分享交流平台,请提供优质的经验内容分享,拒绝任何广告内容出现,低质量广告内容硬广包含手机号码,微信,QQ或者二维码,网址等形式存在可能会审核不通过甚至封号 圈友联系仅限于好向圈APP进行及时沟通咨询 要想被各大搜索引擎尽快收录请做好内容原创工作,才会有更好的推广效果。
返回列表
使用道具 举报
#arraylist, #实现, #vector, #数组, #数据
15 条评论
您需要登录后才可以回帖 登录 | 立即注册
菊花茶啊茶f 发表于 2020-5-27 07:49:15 | 阅读全部
集合
使用道具 举报
回复
爱情零点一忱 发表于 2020-5-27 07:53:01 | 阅读全部
,,,,
使用道具 举报
回复
涟源一中校草草f 发表于 2020-5-27 07:59:03 | 阅读全部
mark
使用道具 举报
回复
kxm8617 发表于 2020-5-27 08:01:50 | 阅读全部
转发了
使用道具 举报
回复
123473510 发表于 2020-5-27 08:06:46 | 阅读全部
6666
使用道具 举报
回复
推探哥紧 发表于 2020-5-27 08:12:26 | 阅读全部
转发了
使用道具 举报
回复
随显萨完 发表于 2020-5-27 08:19:05 | 阅读全部
转发了
使用道具 举报
回复
少雪夫争 发表于 2020-5-27 08:20:36 | 阅读全部
转发了
使用道具 举报
回复
wssw54000 发表于 2020-5-27 08:21:43 | 阅读全部
转发了
使用道具 举报
回复
胖胖宝儿狭 发表于 2020-5-27 08:27:28 | 阅读全部
转发了
使用道具 举报
回复
任在江湖嘶 发表于 2020-5-27 08:31:31 | 阅读全部
转发了
使用道具 举报
回复
直次格酒 发表于 2020-5-27 08:35:13 | 阅读全部
转发了
使用道具 举报
回复
十三笔画1314 发表于 2020-5-27 08:41:00 | 阅读全部
转发了
使用道具 举报
回复
123473208 发表于 2020-5-27 08:43:02 | 阅读全部
转发了
使用道具 举报
回复
龙宿1987 发表于 2020-5-27 08:45:10 | 阅读全部
转发了
使用道具 举报
回复
    侵权投诉可通过好向圈APP举报投诉----社区技术支持:泰帮动力 江苏好向圈信息科技有限公司 网站地图1 网站地图2