java集合分为哪几大类,java集合框架
Yyds干货库存
一、数组列表概述:
ArrayList是基于array实现的,array是一个动态数组,容量可以自动增加,类似于C语言中的动态应用内存,动态增加内存。
ArrayList不是线程安全的,只能在单线程环境下使用。在多线程环境中,可以考虑使用集合。Synchronized List (listl)函数返回一个线程安全的ArrayList类,也可以在concurrent和contracting下使用CopyOnWriteArrayList类。
ArrayList实现了Serializable接口,所以支持序列化,可以通过序列化传输,实现了RandomAccess接口,支持快速随机访问。其实就是通过下标序列号快速访问,实现可克隆接口,可以克隆。
每个ArrayList实例都有一个容量,它指的是用于存储列表元素的数组的大小。它总是至少等于列表的大小。随着元素不断添加到ArrayList中,它的容量会自动增长。自动增长会导致数据被复制回新数组,所以如果可以预测数据量,那么在构造ArrayList时就可以指定它的容量。在添加大量元素之前,应用程序还可以使用ensureCapacity操作来增加ArrayList实例的容量,这样可以减少增量重分布的次数。
注意,这个实现不是同步的。如果多个线程同时访问一个ArrayList实例,并且其中至少有一个线程在结构上修改了列表,那么它必须保持外部同步。
二、ArrayList的实现:
对于ArrayList,它实现了List接口,底层使用数组保存所有元素。它的操作基本上是对一个数组的操作。下面我们来分析一下ArrayList的源代码:
1)私有属性:
ArrayList定义只定义了一个类的两个私有属性:
/**
*存储ArrayList元素的数组缓冲区。
ArrayList的容量就是这个数组缓冲区的长度。
*/
私有瞬态对象[]element data;
/**
ArrayList的大小(它包含的元素数)。
*
* @串行
*/
私有int大小;
很好理解,elementData在ArrayList中存储元素,size表示它包含的元素个数。
有一个关键词需要说明:瞬态。
短暂的.
有点抽象。看个例子就明白了。
公共类UserInfo实现Serializable {
private static final long serial version uid=996890129747019948 l;
私有字符串名称;
私有瞬态字符串psw
public UserInfo(字符串名称,字符串psw) {
this.name=name
this.psw=psw
}
公共字符串toString() {
return name= name ,psw= psw
}
}
公共类TestTransient {
公共静态void main(String[] args) {
Useruserinfo=newuserinfo(张三, 123456 );
system . out . println(userInfo);
尝试{
//序列化,设置为瞬态的属性不序列化
object output stream o=new object output stream(新文件输出流(
userinfo . out ));
o . writeobject(userInfo);
o . close();
} catch(异常e) {
//TODO:处理异常
e . printstacktrace();
}
尝试{
//重新阅读内容
ObjectInputStream in=new ObjectInputStream(new file inputstream(
userinfo . out ));
UserInfo read UserInfo=(UserInfo)in . read object();
//读取后psw的内容为空
system . out . println(read userinfo . tostring());
} catch(异常e) {
//TODO:处理异常
e . printstacktrace();
}
}
}
序列化对象时,不会保存标记为瞬态的属性。
然后回到ArrayList的分析。
2)施工方法:
ArrayList以三种方式提供构造函数:默认初始容量为10的空列表、指定初始容量的空列表和包含指定集合元素的列表,这些元素按照集合的迭代器返回它们的顺序排列。
//容量大小为的ArrayList构造函数。
公共数组列表(int initialCapacity) {
super();
if (initialCapacity 0)
抛出新的IllegalArgumentException(非法容量:
初始容量);
//创建一个新数组
这个。元素数据=新对象[初始容量];
}
//ArrayList无参构造函数。默认容量是10。
公共数组列表(){
这(10);
}
//创建一个包含募捐的数组列表
公共数组列表(集合?扩展中文){
元素数据=c . to array();
size=elementData .长度
if (elementData.getClass()!=对象[]。类)
元素数据=数组。(元素数据,大小,对象[]得副本.类);
}
3) 元素存储:
数组列表提供了set(在index,Ee元素中)、add(Ee)、add(在index,Ee元素中)、addAll(集合?extendsE c)、addAll(intindex,Collection?extendsE c)这些添加元素的方法。下面我们一一讲解:
20 //用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。
21公共E集(int index,E element) {
22范围检查(索引);
23
24e旧值=(E)元素数据[索引];
25元素数据[索引]=元素;
26返回旧值
27 }
28 //将指定的元素添加到此列表的尾部。
29公共布尔加法(E e) {
30确保容量(尺寸1);
31元素数据[大小]=e;
32返回真实的
33 }
34 //将指定的元素插入此列表中的指定位置。
35 //如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。
36 public void add(int index,E element) {
37如果(索引大小索引0)
38 throw new IndexOutOfBoundsException( Index: Index ,Size: Size);
39 //如果数组长度不足,将进行扩容。
40确保容量(尺寸1);//递增modCount!
41 //将元素数据中从索引位置开始、长度为尺寸指数的元素,
42 //拷贝到从下标为索引一位置开始的新的元素数据数组中。
43 //即将当前位于该位置的元素以及所有后续元素右移一个位置。
44 System.arraycopy(elementData,index,elementData,index 1,size-index);
45元素数据[索引]=元素;
46码;
47 }
48 //按照指定募捐的迭代器所返回的元素顺序,将该募捐中的所有元素添加到此列表的尾部。
49公共布尔addAll(集合?扩展中文){
50 Object[]a=c . to array();
51 int numNew=a.length
52确保容量(尺寸numNew);//增加modCount
53 System.arraycopy(a,0,elementData,size,numNew);
54 size=numNew
55返回numNew!=0;
56 }
57 //从指定的位置开始,将指定募捐中的所有元素插入到此列表中。
58公共布尔addAll(int index,Collection?扩展中文){
59如果(索引大小索引0)
60抛出新的IndexOutOfBoundsException(
61 Index: index ,Size: Size);
62
63 Object[]a=c . to array();
64 int numNew=a.length
65确保容量(尺寸numNew);//增加modCount
66
67 int num moved=size-index;
68 if (numMoved 0)
69 System.arraycopy(elementData,index,elementData,index numNew,num moved);
70
71 System.arraycopy(a,0,elementData,index,numNew);
72 size=numNew
73返回numNew!=0;
}
书上都说数组列表是基于数组实现的,属性中也看到了数组,具体是怎么实现的呢?比如就这个添加元素的方法,如果数组大,则在将某个位置的值设置为指定元素即可,如果数组容量不够了呢?
看到添加(英英)中先调用了确保容量(尺寸1)方法,之后将元素的索引赋给elementData[size],而后大小自增。例如初次添加时,尺寸为0,添加将元素数据[0]赋值为e,然后大小设置为1(类似执行以下两条语句元素数据[0]=e;size=1)。将元素的索引赋给元素数据[大小]不是会出现数组越界的情况吗?这里关键就在确保容量(尺寸1)中了。
//返回此列表中指定位置上的元素。
public E get(int index) {
范围检查(索引);
return(E)元素数据[index];
}
5) 元素删除:
数组列表提供了根据下标或者指定对象两种方式的删除功能。如下:
romove(int index):
1 //移除此列表中指定位置上的元素。
2 public E remove(int index) {
3范围检查(索引);
四
5 modCount
6 E旧值=(E)元素数据[索引];
七
8 int num moved=size-index-1;
9如果(numMoved 0)
10 System.arraycopy(elementData,index 1,elementData,index,num moved);
11元素数据[-size]=null;//让千兆周做它的工作
12
13返回旧值
14 }
首先是检查范围,修改modCount,保留将要被移除的元素,将移除位置之后的元素向前挪动一个位置,将目录末尾元素置空(空),返回被移除的元素。
移除(对象o)
1 //移除此列表中首次出现的指定元素(如果存在)。这是应为数组列表中允许存放重复的元素。
2公共布尔删除(对象o) {
3 //由于数组列表中允许存放空,因此下面通过两种情况来分别处理。
4 if (o==null) {
5 for(int index=0;索引大小;索引)
6 if (elementData[index]==null) {
7 //类似remove(int index),移除列表中指定位置上的元素。
8快速移除(索引);
9返回真实的
10 }
11 }其他{
12 for(int index=0;索引大小;索引)
13 if(o . equals(element data[index]){
14快速移除(索引);
15返回真实的
16 }
17 }
18返回假;
19 }
20 }
首先通过代码可以看到,当移除成功后返回没错,否则返回错误。移除(对象o)中通过遍历元素寻找是否存在传入对象,一旦找到就调用快速移除移除对象。为什么找到了元素就知道了索引,不通过移除(索引)来移除元素呢?因为快速移除跳过了判断边界的处理,因为找到元素就相当于确定了指数不会超过边界,而且快速移除并不返回被移除的元素。下面是快速移除的代码,基本和移除(索引)一致。
一私有void fastRemove(int index) {
2 modCount
3 int num moved=size-index-1;
4 if (numMoved 0)
5 System.arraycopy(元素数据,索引1,元素数据,索引,
6 num移动);
7元素数据[-size]=null;//让千兆周做它的工作
8 }
removeRange(int fromIndex,int toIndex)
一受保护的void removeRange(int fromIndex,int toIndex) {
2 modCount
3 int num moved=size-toIndex;
4 System.arraycopy(elementData,toIndex,elementData,fromIndex,
5 num移动);
6
7 //让千兆周做它的工作
8 int newSize=size-(toIndex-from index);
9 while(大小!=新尺寸)
10元素数据[-size]=null;
11 }
执行过程是将元素数据从结束下标位置开始的元素向前移动到fromIndex,然后将结束下标位置之后的元素全部置空顺便修改尺寸。
这个方法是受到保护,及受保护的方法,为什么这个方法被定义为保护呢?
这是一个解释,但是可能不容易看明白http://堆栈溢出。why-is-javas-abstract lists-remove range-method-protected
先看下面这个例子
数组列表整数ints=新的ArrayList整数(数组。作为列表(0,1,2,
3, 4, 5, 6));
//子列表的起始下标低端点(含低端点)
//toIndex子列表的高端点(不含)
ints.subList(2,4).clear();
系统。出去。println(ints);
输出结果是[0, 1, 4, 5, 6],结果是不是像调用了removeRange(int fromIndex,int toIndex)!哈哈哈,就是这样的。但是为什么效果相同呢?是不是调用了removeRange(int fromIndex,int toIndex)呢?
6)调整数组容量确保容量:
从上面介绍的向数组列表中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法确保容量(intminCapacity)来实现。在实际添加大量元素前,我也可以使用保证容量来手动增加数组列表实例的容量,以减少递增式再分配的数量。
public void确保容量(int minCapacity){
modCount
旧能力=要素数据。长度;
如果(最小容量旧容量){
对象旧数据[]=元素数据;
int新容量=(旧容量* 3)/2 1;//增加50% 1
if(新容量最小容量)
newCapacity=minCapacity
//minCapacity通常接近size,所以这是一个win:
element data=arrays . copy of(element data,new capacity);
}
}
从上面的代码可以看出,当数组被扩展时,旧数组中的元素会被复制回新数组,数组的容量每次都会增加1.5倍左右。这种操作的成本很高,在实际使用中要尽量避免数组容量的扩大。当我们可以预测需要保存的元素数量时,就应该在构造ArrayList实例时指定它的容量,避免数组膨胀。或者根据实际需求通过调用ensureCapacity方法手动增加ArrayList实例的容量。
ObjectoldData[]=element data;//为什么要用oldData[]
乍一看,后面并没有使用oldData。这句话好像是多余的!但这是一个涉及内存管理的类,应该知道内部的问题。而这句话为什么还在if里面?与element data=arrays . copy of(element data,new capacity)相同;这句话是有关联的。下面这句话的实现Arrays.copyOf创建一个新的内存,大小为newCapacity,然后把旧的elementData放进去。OldData好像也不用。有什么问题?问题是旧的内存引用是elementData,它指向新的内存块。如果有一个局部变量oldData引用了旧内存块,那么在复制的过程中会比较安全,因为这证明这个旧内存还是有引用的,在分配内存的时候不会被侵占。那么这个局部变量的生命在复制之后就过去了,然后释放它就安全了。否则,如果新内存或其他线程分配的内存在复制未完成时侵占了旧内存,这将是一个严重的问题。
ArrayList和Vector的区别如下:
内存不足时ArrayList默认扩大50%,Vector默认扩大1倍。Vector提供indexOf(obj,start)接口,ArrayList没有。Vector属于线程安全级别,但是大部分情况下不使用Vector,因为线程安全需要更多的系统开销。
ArrayList还为我们提供了将底层数组的容量调整为当前列表中存储的实际元素的大小的功能。它可以通过trimToSize方法实现。代码如下:
127 public void trimToSize() {
128 modCount
129 int old capacity=element data . length;
130如果(大小旧容量){
131 element data=arrays . copy of(element data,size);
132 }
}
由于elementData的长度将被扩展,因此大小标志着其中包含的元素的数量。所以会出现尺寸小但elementData.length大的情况,会有空间浪费。TrimToSize会向elementData返回一个新数组,元素内容保持不变,长度和大小相同,节省空间。
7)转换为静态数组
4.注意ArrayList的两个toArray方法,它们被转换成静态数组。
首先调用Arrays.copyOf会返回一个元素大小为elementData的数组,也就是将elementData的元素从0到size-1复制到新数组中并返回。
公共对象[] toArray() {
return arrays . copy of(element data,size);
}
第二,如果传入数组的长度小于size,则返回一个与传入数组大小相同、类型相同的新数组。如果传入数组的长度等于大小,则将elementData复制到传入数组中,并返回传入数组。如果传入数组的长度大于size,那么除了复制elementData之外,返回数组的size元素将被设置为null。
公共T T[] toArray(T[] a) {
如果(长度尺寸)
//生成a的运行时类型的新数组,但我的内容:
return(T[])arrays . copy of(element data,size,a . getclass());
System.arraycopy(elementData,0,a,0,size);
如果(长度尺寸)
a[size]=null;
返回a;
}
快速失效机制:
ArrayList还采用了快速失效的机制,通过记录modCount参数来实现。面对并发修改,迭代器很快就会完全失效,而不是在未来某个不确定的时间冒任何不确定行为的风险。详情请参考本文深入Java集合学习系列:HashMap实现原理中的Fail-Fast机制。
总结:
关于ArrayList的源代码,给出了一些重要的总结:
1.注意它的三种不同的施工方法。无参数构造方法构造的ArrayList的容量默认为10,带集合参数的构造方法将集合转换为数组并赋给ArrayList的实现数组elementData。
2.注意扩容的方法——保容。ArrayList每次添加元素(可能是1个或一个组)时都会调用这个方法,以确保足够的容量。当容量不足以容纳当前的元素数量时,新容量被设置为旧容量的1.5倍。如果设置的新容量不够,则直接将新容量设置为传入参数(即所需容量),然后通过Arrays.copyof()方法将元素复制到新数组中(详见下面第3点)。可以看出,容量不够的时候,每次添加元素都要把原来的元素复制到一个新的数组中,非常耗时。因此,只有在可以预先确定元素个数的情况下,才建议使用ArrayList,否则建议使用LinkedList。
3.ArrayList的实现中广泛使用Arrays.copyof()和System.arraycopy()方法。我们有必要深入了解这两种方法的实现。
让我们先来看看Arrays.copyof()方法。它有许多重载方法,但实现思路都是一样的。让我们看看通用版本的源代码:
public static T T[]copy of(T[]original,int newLength) {
return (T[]) copyOf(original,newLength,original . getclass());
}
显然,调用了另一个copyof方法。该方法有三个参数,最后一个参数指示要转换的数据类型。其源代码如下:
public static T,U T[] copyOf(U[] original,int newLength,Class?extends T[] newType) {
t[]copy=((Object)new type==(Object)Object[]。类)
?(T[])新对象[newLength]
:(T[])array . new instance(new type . getcomponenttype(),new length);
System.arraycopy(原始,0,副本,0,
Math.min(original.length,new length));
返回副本;
}
这里可以清楚的看到,这个方法实际上是创建了另一个数组,数组内部的长度为newlength,并调用System.arraycopy()方法将原数组中的元素复制到新数组中。
让我们看看System.arraycopy()方法。此方法被标记为native,并调用系统的C/C代码。它在JDK是不可见的,但是它的源代码可以在openJDK中看到。其实这个函数最后调用的是C语言的memmove()函数,所以可以保证同一数组中元素的正确复制和移动,比常见的复制方法效率高很多,非常适合数组的批量处理。Java在复制大量数组元素时强烈推荐这种方法,以达到更高的效率。
4.ArrayList是基于array实现的,可以通过下标索引直接找到指定位置的元素,所以搜索效率高。但是每次插入或删除元素都要移动大量的元素,插入和删除元素的效率较低。
5.在寻找给定元素的索引值的方法中,源代码将元素的值视为null和非null,并允许元素在ArrayList中为null。
版权归作者所有:来自博主的苦糖?原创作品请联系作者授权转载,否则将追究法律责任。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。