`
langyu
  • 浏览: 883165 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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

    博客分类:
  • java
阅读更多
在程序中,集合类每天都在使用,以致于某些代码充斥着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*(集合中只包含一个元素)。它们都是通过包装集合类中的抽象类获得,产生不同的行为。

上面是常见的几种集合类,其它类我很少使用到。
不记得是谁说过,我们最容易记住图像化的知识。在学习了部分集合类知识后,总结下,以便以后忘记了还能翻看下。
20
0
分享到:
评论
9 楼 yang3516793 2016-04-12  
那个index哪里你写的按位异或操作吧!不是按位与操作吧
8 楼 langyu 2011-03-05  
nicholasun 写道
楼主的图是用什么软件画的?

呵呵,Office里的Visio
7 楼 nicholasun 2011-03-05  
楼主的图是用什么软件画的?
6 楼 qiushily2030 2010-07-01  
数据结构啊,有点简单,又有点复杂. 应该是我基础不扎实吧
5 楼 zhangshixi 2010-06-02  
写的不错。
我在我的博客里也写了几篇关于Java集合类的源码解析,如:深入Java集合学习系列:HashMap的实现原理,可以相互借鉴下。
4 楼 arantam 2009-06-26  
好文章!复习一下.
3 楼 75468850 2009-04-07  
不错,学习了。
2 楼 langyu 2009-04-07  
avanry 写道

有点复杂...晕了

这只是我们常见的几种集合类,像那种红黑树的调整,看的我都昏啊。

可能是我说的不太明白,慢慢改进吧。
1 楼 avanry 2009-04-07  
有点复杂...晕了

相关推荐

    Java数据结构及集合类.doc

    Java数据结构及集合类.doc

    数据结构与问题求解Java语言

    作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...

    数据结构与算法分析_java语言描述

    作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...

    java集合类学习汇总

    简单介绍了java几个集合类的使用(为了方便浅显了解java集合类的使用和应用场景)

    java深入学习教程书籍ppt及pdf集合

    这是本文精心搜集的关于java方面的深入学习的资料...java类库简介和数据结构类使用ppt 深入java虚拟机pdf书籍 深入理解java虚拟机pdf 数据结构与算法 java语言版pdf 数据结构与算法分析java版 数据结构与算法项目化教程

    java集合类原理面试题

    java集合类 Java中有哪些容器(集合类)? 线程安全和线程不安全的分别有哪些? Map接口有哪些实现类? 描述一下Map put的过程 如何得到一个线程安全的Map? HashMap有什么特点? ConcurrentHashMap是怎么分段分组...

    Java编程实践:10个实用例子助您提升技能正则表达式、文件操作、日期和时间处理、数据结构、集合类、接口和多态、递归、多线程编程

    9. 使用Java集合类实现队列:演示了如何使用Java集合类中的Queue接口来实现队列数据结构。 10. 多线程编程:创建和启动线程:展示了如何通过实现Runnable接口创建一个新线程,并演示了多线程编程的基本概念。

    Java集合框架.pdf

    Java集合框架是一个抽象数据类型的框架,它提供了一组接口和类,可用于处理各种类型的数据结构,如列表、队列、集、映射等。 Java集合框架的主要特点是: 1、可扩展性:Java集合框架提供了一组可扩展的接口和类,可...

    java 中的数据结构

    数据结构在java集合类中的应用 jdk首先细节与如何高效应用

    java集合资料整理

    关于java集合资料的整理 集合接口:6个接口,表示不同集合类型,是集合框架的基础。 抽象类:5个抽象类,对集合接口的部分实现。可扩展为自定义集合类。 实现类:8个实现类,对接口的具体实现。 在很大程度上,...

    Java集合框架使用总结

    本文是对Java集合框架做了一个概括性的解说,目的是对Java集合框架体系有个总体认识,如果你想学习具体的接口和类的使用方法,请参看Java API文档。 一、概述 数据结构对程序设计有着深远的影响,在面向过程的...

    Java学习总结,目前包括数据结构,算法,设计模式,反射,线程,集合和内部类..zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...

    java实现将实体类list集合,转化成geojson字符串

    GeoJSON是一种对各种地理数据结构进行编码的格式,基于Javascript对象表示法(JavaScript Object Notation, 简称JSON)的地理空间信息数据交换格式...该工具可以实现通过java代码将任意的实体类数据集合生成GeoJSON字符串

    (数据结构与算法:C#语言描述(英文)

    在.NET 框架库中包含有一套数据结构类(也称为集合类)。这套类的范围从Array 类、ArrayList 类和Collection 类到Stack类和Queue 类,再到Hashtable 类和SortedList 类。学习数据结构与算法的学生在学习如何实现它们...

    Java工具包提供了强大的数据结构

    在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性(Properties) 以上这些类是传统遗留的,在Java2...

    细说Java之常用集合类

    线性表,链表,哈希表是常用的数据结构,在进行Java 开发时,JDK 已经为我们提供 了一系列相应的类来实现基本的数据结构。这些类均在java.util 包中。本文试图通过简单的 描述,向读者阐述各个类的作用以及如何正确...

    数据结构(C语言版)\Java数据结构和算

    5.10 不相交集合的表示 5.11 二叉树的计数 5.12 参考文献和选读材料 第6章 图 6.1 图的抽象数据类型 6.2 图的基本操作 6.3 最小代价生成树 6.4 最短路径和迁移闭包 6.5 活动网络 6.6 参考文献和选读材料 ...

    java数据结构和算法

    java数据结构和算法,各种排序,二叉树,队列,集合类,等等。

    Java数据结构与算法中的源代码和applet - 站长下载

    书名:数据结构Java版 图书编号:2086963 出版社:清华大学 定价:118.0 ISBN:730213544 作者:(美)福特(Ford,W.H.),(美)托普(Topp,W.R.) 著,梁志敏 译 出版日期:2006-11-11 版次: 开本: 简介: 本书...

Global site tag (gtag.js) - Google Analytics