文档章节

java主要集合类的数据结构学习

闪电
 闪电
发布于 2016/07/21 00:34
字数 1315
阅读 18
收藏 1
在程序中,集合类每天都在使用,以致于某些代码充斥着List和Map,一直没有机会整理下它们背后的实现原理。这几天不太忙,正好可以看会代码,补充下概念。
和集合类的大致分类类似,下面我也分List,Map和Set来描述。

一. List
1).ArrayList


 ArrayList维护着一个对象数组。如果调用new ArrayList()后,它会默认初始一个size=10的数组。
 每次add操作都要检查数组容量,如果不够,重新设置一个初始容量1.5倍大小的新数组,然后再把每个元素copy过去。
 在数组中间插入或删除,都要移动后面的所有元素。(使用System.arraycopy())

2).LindedList
LinkedList的实现是一个双向链表。每个节点除含有元素外,还包含向前,向后的指针。
新建一个LinkedList,生成一个头节点(header,就是一个头指针),它的元素为null。

它自包含,next和previous指针都指向自己。
执行add(Object obj)方法后,会生成一个新节点

Header节点的next指向链表的第一个节点,previous指向链表的最后一个节点,在这里都是first。
再增加一个对象,它的形状像下面这样。

现在是一个标准的双向链表形状。每个节点都有自己的next和previous指针。
 增加节点,只会对链表的指针进行操作,速度快
 LinkedList实现了Deque,所以它有双向队列的特征,在链表两端可增删数据
 使用index查找对象时,会以index和size/2比较,从前或从后向中间搜索
 ListIterator可向前或向后迭代

比较ArrayList和LinkedList的结构,就可以得出:
1. ArrayList的remove和add(index, Object)操作代价高,需要移动后面的每个元素。
2. LinkedList的get(index)操作代价高,它要先循环遍历list,找到Object


二. Map
1).HashMap
HashMap的结构是一个散列桶,初始化时生成如下结构

每个bucket包含一个Entry(map自定义的一种结构,包含一个往后的指针)的链表。
在put(key, value)后,它的结构如下

将key的hashcode再次散列,然后用这个hash和length-1进行按位与操作,得到bucket的index,然后检查当前bucket的链表,有没有这个key,如果有替换value,没有则跟在链表的最后。
 允许key和value都可以是null
 Index=0的bucket存key=null的value,也可以是其它hashcode为0的项
 初始容量必须为2的幂次(我的理解是,在生成index的时候有这样的代码:hase ^ (length - 1)),length – 1的二进制代码为全1,则容易进行hash的设计)
 如果两个key散列后的index一样的话,第一个key生成的Entry先存在桶中,第二个key生成的Entry会将第一个Entry设为自己的next,串起来。(如图中,先put(yy, “first”),会将这个Entry设为bucket的第一项,后put(xx,”second”),则生成新Entry,它的next为key为yy的Entry,生成一个链表)
 在put操作中,会比较threshold(capacity * load_factor,一个临界值),如果size > threshold的话,生成一个当前bucket两倍数量的buckets,然后把现有的数据重新散列到新bucket中
 对HashMap迭代时,返回数据的顺序是:index从0到length-1,循环遍历每个bucket,把不为null的数据取出,每个bucket内的顺序由链表的顺序决定。而不是由插入数据决定。

2).LinkedHashMap
上面说过,Map的迭代不由插入顺序决定。如果要保持这种顺序呢?就要新增加一种结构来保持。

LinkedHashMap是HashMap的子类,增加一个双向链表,用来存储每个新加入的节点。在遍历时,按链表的顺序进行。其实差不多就是上面HashMap和LinkedList的和吧。
三. Set
1).HashSet
HashSet使用HashMap来保持元素。Key = 元素,value是一个公有的对象,对每个元素都一样,在HashMap里面key是惟一的,当然很适合于构造set集合。等同于用HashMap包装了次,显示Set自己的特性。

最后还要提到集合类里面一个很重要的类:Collections,它有很多自己独特的静态方法。当然它主要提供几种特殊集合(List, Map,Set),可以调用静态方法来获得:Unmodifiable*(不可修改集合,不可添加或删除元素),Synchronize*(保持同步集合,它的基本每个方法都加锁,防止并发操作),Checked*(声明之始传入特定类型,以后的操作都会验证加入元素是否属于已定类型),Singleton*(集合中只包含一个元素)。它们都是通过包装集合类中的抽象类获得,产生不同的行为。

上面是常见的几种集合类,其它类我很少使用到。
不记得是谁说过,我们最容易记住图像化的知识。在学习了部分集合类知识后,总结下,以便以后忘记了还能翻看下。

本文转载自:http://langyu.iteye.com/blog/360728

闪电
粉丝 75
博文 392
码字总数 6789
作品 0
海淀
技术主管
私信 提问
Java集合源码分析之Iterable概述_一点课堂(多岸学院)

前言 当我们想要遍历集合时,Java为我们提供了多种选择,通常有以下三种写法: 写法1:for循环 写法2:foreach循环 写法3:Iterator 那么以上三种遍历方式有何区别呢?for循环我们很熟悉了,...

程伟鑫
09/10
25
0
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
2018/10/11
33
0
Java数据结构知多少?java入门学习

  初学java时,我们会了解到Java工具包提供了强大的数据结构,那么Java的数据结构都有哪几种呢?   一、枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很...

老男孩Linux培训
2018/07/09
6
1
Java集合框架(一)——集合概述

本文概述 本篇文章将分三块内容对Java中的集合框架进行介绍: 一. 集合框架相关概念 二. 集合体系通用方法 三. 集合遍历—Iteractor 一. 集合框架相关概念 集合:用于存储多个对象的容器 1....

Mr_Yanger
2017/11/11
0
0
总结一下自己关于学习java集合的一些知识

主要是想总结一下自己关于学习java集合的一些知识 与大家分享 交流 不太全面..如果有什么不足和错误的地方 还望指正 互相学习.. 集合(Collection) 运用集合的条件:我们学习的是Java -- 面向对...

NewBeeJack
2016/08/21
789
2

没有更多内容

加载失败,请刷新页面

加载更多

iOS苹果应用IPA一键签名工具及重签教程

开心签名工具,是一款跨平台ios签名和重签名工具。 同时支持在windows、linux、mac运行,数据同步,方便使用及管理! 开心重签名工具官网 功能特点 1、支持图形界面及命令行重签(部署到服务...

tintong
9分钟前
3
0
2.4G有源卡核心芯片供应商

有源2.4G RFID的防盗标签,在与无源标签相比较,通信距离远,通信时效高。我司的SI24R2E这颗芯片专门为2.4G有源标签而设计,具有低功耗,发送距离远,厂商设计简单等优势;广泛应用于现在城市...

文刀石
14分钟前
2
0
设置Ubuntu16.04启动为命令行界面

1. 修改/etc/default/grub文件,将GRUB_CMDLINE_LINUX_DEFAULT设置成”quiet splash 3” 2. 使用命令update-grub使得在/boot下重新生成GRUB2配置文件。 3. 重启...

JosiahMg
15分钟前
2
0
C++基础知识点

计算机语言 计算机不能理解高级语言,只能理解机器语言,必须要将高级语言翻译成机器语言,翻译的方式有两种,一种是编译,一种是解释 解释型语言,在运行程序时进行翻译,每个语句在执行时逐...

大瑞清_liurq
21分钟前
2
0
EFCore 多条数据更新不能同时savechanges()的解决方法

1 在ModelContext定义下增加var transaction = ctx.Database.BeginTransaction(); 1.2 在最后一个SaveChanges()后增加transaction.Commit(); 3 在finally的if (sMsgCode != "")分支中增加tra......

_Somuns
25分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部