在程序中,集合类每天都在使用,以致于某些代码充斥着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*(集合中只包含一个元素)。它们都是通过包装集合类中的抽象类获得,产生不同的行为。
上面是常见的几种集合类,其它类我很少使用到。
不记得是谁说过,我们最容易记住图像化的知识。在学习了部分集合类知识后,总结下,以便以后忘记了还能翻看下。
分享到:
相关推荐
自定义集合类的一个例子是,你可能想要创建一个支持优先级排序的队列,这时可以实现一个`PriorityQueue`类,基于最小堆数据结构实现,允许用户通过优先级插入和删除元素。 在实际应用中,自定义集合类可以提高代码...
实现是指表示这些集合接口的具体实现,实质上是可重用的数据结构,即通用集合类。算法是指可以对实现集合接口的类进行一些实用计算的方法,比如排序和查找。 Java 集合框架的接口层次和通用实现如下: 图 1 Java ...
Java 集合类是 Java 语言中的一种基本数据结构,用于存储和操作大量数据。集合类可以分为三大类:Collection、List 和 Set。 Collection 是集合框架中的根接口,提供了基本的集合操作,如 add、remove、contains 等...
Java集合框架还包含了一些实用类,如ArrayList、LinkedList、HashSet、HashMap等,它们是具体的数据结构实现。这些类提供了丰富的操作方法,如add、remove、contains、get等,方便了程序员在实际开发中的使用。 在...
Java集合类层次结构是Java编程语言中用于存储和管理对象的核心框架。这个层次结构由多个接口和类组成,为开发者提供了灵活且强大的数据结构选择。理解这个层次结构对于编写高效、可维护的Java代码至关重要。 在Java...
理解这些基本数据结构有助于更好地理解和使用Java集合类。 总之,Java集合类提供了丰富的选择来满足不同场景下的数据存储需求,从无序不重复的Set到有序可重复的List,再到键值对的Map,都有对应的接口和实现类。...
根据提供的文件信息,本部分将对“JAVA版数据结构.pdf”中的内容进行知识点的详细说明。...在实际阅读和学习过程中,应该关注每个章节的具体内容,结合Java语言的具体语法规则和数据结构的详细实现来深入理解。
本资源"超级适合java学习者使用的数据结构"针对Java学习者提供了一套全面、详细的数据结构教程,以面向对象的方式进行讲解,有助于读者深入理解数据结构与Java的结合。 在Java中,数据结构是存储和组织数据的方式,...
总的来说,《数据结构(Java版本)》是一本适合程序员入门的教材,通过学习,你可以系统地掌握数据结构和算法,并用Java语言进行实现,为今后的软件开发打下坚实的基础。无论你是准备面试,还是想要提升编程技能,这...
Collection接口是JAVA中所有集合类的父接口,它提供了基本的集合操作方法,如add、remove、contains、size等。Collection接口的实现类有很多,如List、Set、Map等。 List接口 List接口继承自Collection接口,是一...
此外,课件可能还会涵盖数据结构在Java集合框架中的应用,如ArrayList、LinkedList、HashSet、HashMap等的内部实现原理,以及如何根据实际需求选择合适的数据结构。理解并熟练掌握这些内容对于提升编程能力、解决...
Java集合类是Java语言中的一种重要数据结构,用于存储和管理数据。Java集合类可以分为两种:Collection接口和Map接口。Collection接口有两个子接口:List接口和Set接口。List接口是有序的,可以重复元素,常用的实现...
《数据结构和Java集合框架》是清华大学出版社出版的一本经典教材,主要涵盖了计算机科学中的核心概念——数据结构以及Java编程语言中的集合框架。这本书通过深入浅出的方式,讲解了如何用Java实现各种常用的数据结构...
本文将深入讲解Java集合类,特别是Collection接口和其下的List、Set,以及Map接口中的几个重要实现类。 首先,我们来看Collection接口。Collection是最基本的集合接口,它代表一组Object,即它的元素。Collection...
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
### Java集合排序及Java集合类详解 #### 一、集合框架概述 集合框架是Java编程语言的核心组件之一,用于组织和操作数据集。Java集合框架提供了多种数据结构,包括列表(List)、集(Set)和映射(Map),这些数据结构...
总结起来,Java集合类的学习不仅仅是了解每个类的基本用法,更关键的是理解它们背后的实现原理和数据结构,以便根据实际需求选择最合适的集合类。通过深入学习和实践,我们可以提高代码的效率和可维护性,更好地应对...
总结来说,Java集合类通过提供丰富的接口和实现,使得Java开发者可以灵活选择适合特定需求的数据结构,提高代码的可读性和性能。理解并熟练掌握这些集合类和接口,对于编写高质量的Java程序至关重要。
### Java集合类详解总结 在Java编程中,集合框架(Collection Framework)是处理一组对象的强大工具,它提供了标准的数据结构来存储和操作这些对象。Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`...