java集合包总结(添加、删除等操作实现原理)

时间:2022-01-21 22:12:33

1.集合包

常用的是CollectionMap两个接口的实现类。

Collection常用的两种接口:ListSet

List实现类:ArrayListLinkedListVectorStack

Set实现类:HashSetTreeSet

Collection主要包括创建、增加、删除、获取单个对象、遍历对象、判断对象是否存在与Collection中、对象的排序。

1.1ArrayList

创建ArrayList采用数组的方式来存放对象,创建一个大小为10Object数组。

插入对象

问题:传入对象数组满了,怎么办?

当调用add方法时,首先基于ArrayList中已有的元素加1,产生minCapacity变量,然后比较此值和Object数组的大小,如果此值大于Object数组值,将Object数组值赋给新的数组对象,产生一个新的数组容量值。此值的计算方法是当前数组值x 1.5+1,如果容量值仍然小于minCapacity,那么就以minCapacity作为新的容量值。得出容量值后,调用Arrays.copyOf来生成新的数组对象。(如果想调整容量的增长策略,可继承ArrayList

Arrays.copyOf方法实现:创建一个新数组对象,该数组对象的类型和之前的ArrayList中的元素的类型一致。(JDK优化,如果是Object类型,直接通过new Object[newLength]创建,如果不是,则通过Array.newInstance调用native方法创建相同类型的数组;创建完数组对象之后,调用System.arraycopy通过native方法将之前数组中的对象复制到新的数组中)

Collection中增加对象,ArrayList提供一个add(intE)这样的方法,允许元素直接插入指定的int位置上(这个方法要确保插入的位置存在,确保容量够用)。但与add()方法不同,他要将当前数组的对象进行复制,将其后的数据都往后挪动一位,然后才能将指定的index位置的赋值为传入的对象。

除了add()ArrayList还提供了set(int ,E)方法替换原来指定位置的对象。

删除对象:

   remove(E):遍历数组,将找到的相同对象删除(如果有重复的只删除一个),将index后面的对象往前复制一位。remove(int)删除指定位置的对象,它比remove(E):多一个数组范围的检测,但少了对象位置的查找,性能更好。

获取单个对象:

获得数组元素的位置,先做范围检测,然后可直接返回数组中位于此位置的对象。

遍历对象:

IteratorArrayList的父类AbstractList实现,当每次调用iterator方法时,都会创建一个新的AbstractList内部Itr的实例。当调用此实例的hasNext方法时,比较指定位置的数组是否和数组中已有的元素大小相等。如果相等放回false,否则返回true

判断对象是否存在:

Contains(E):遍历ArrayList已有元素。

indexOflastIndexOfArrayList用于获取对象所在位置的方法,IndexOf从前往后寻找,lastIndexOf从后向前。

注意

1.ArrayList基于数组,无容量限制。

2.ArrayList插入元素可能需要扩容,删除元素并不会减少数组的容量(如果希望相应的缩小数组容量,可以调用ArrayListtrimToSize()),在查找元素时需要遍历数组,对于非null元素采用equals的方式寻找。

3.ArrayList非线程安全。

1.2LinkedList

实现方式:基于双向链表机制,就是集合中的每个元素都知道其前一个元素及其后一个元素的位置。在LinkedList中,内部类Entry类来代表集合中的元素,元素值赋给element属性,Entrynext属性指向后一个元素,Entry中的previous属性指向元素的前一个原理,这样可以快速实现集合中元素的移动。

add(E):

LinkedList中增加元素,就要创建Entry对象,完成添加操作链表的处理,始终保持双向链表的闭环。LinkedList add方法不需要考虑扩容及复制数组的问题。

remove(E)

删除LinkedList的一个元素也要遍历LinkedList中的元素,遍历和寻找匹配的元素的方法和ArrayList基本相同,但是删除元素的方法比ArrayList简单。

get(int)

由于LinkedList的元素并没有存储在一个数组中,因此get操作复杂。执行get操作的时候,首先要判断传入的index值是否合理。如果不符合,抛出IndexOutOfBoundsException(如果值小于一半,则从头一直找到index位置所对应的next元素,如果大于,则从尾部往前,一直找到index位置所对应的previous元素)

Iterator()

当调用Iterator()返回的hasnext方法时,判断当前cursor的位置是否等同于LinkedListsize变量,等于返回true,不等于返回false。如在遍历中增加或删除,则会抛出ConcurrentModificationException异常。也可以通过hasPreviousprevoius来完成遍历。

contains(E)

LinkedList也是采用的遍历所有元素的方法。

注意:

1.LinkedList基于双向链表机制实现

2.LinkedList插入与删除原理

3.LinkedList是非线程安全的

 

1.3Vector

Vector() 默认创建一个大小为10Object数组,设定一个参数capacityIncrement设置为0

add(E):Vectoradd方法加了synchorized关键字,因此方法线程安全,除此与ArrayList基本相同。除扩充数组:如果capacityIncrement大于0,则将Object数组大小扩大为size加上capacityIncrement的值。如果capacityIncrement <=0 ,在将Object数组扩大为现在size的两倍。这种容量的控制策略比ArrayList更为可控。

remove(E)

除了调用removeElement方法上有synchorized关键字外,其他和ArrayList完全相同。

get(int)

此方法同样有synchorized

Iterator

ArrayList完全一样

contains(E)

Indexof放有synchorized方法

注意

Vector是基于synchorized实现的线程安全ArrayList

1.4Stack

实现方式

Stack继承于Vector,在其基础上实现LIFO的弹出和压入,提供了pushpoppeek三个主要的方法。

push

通过调用Vector中的addElement来完成。

pop

调用peek获取元素,并同时删除数组的最后一个元素。

peek

Peek根据当前Object数组的大小,并取得最后一个元素

1.5HashSet

HashSetSet接口的实现,与List明显的区别在于Set不允许元素重复,而List允许。Set为了做到不允许元素重复,采用的是基于HashMap来实现。

HashSet

要创建一个HashMap对象。

add()

调用HashMapput()方法来完成此操作,将需要增加的元素作为mapkeyvalue则传入一个之前已创建的Object对象。

remove(E)

使用HashMapremove(E)方法来完成此操作。

Iterator

调用HashMapkeySetiterator方法来完成此操作。HashSet不支持通过get(int)获取指定位置的元素,只能通过iterator方法获取。

注意要点:

对于HashSet而言,需要注意以下几点:

1.HashSet基于HashMap实现,无容量限制

2.HashSet是非线程安全的。

 

1.6TreeSet

TreeSetHashSet主要不同在于TreeSet对于排序的支持,TreeSet基于TreeMap实现

 

Iterator

调用TreeSetnavigableKeySetiterator方法完成此操作。

TreeSetHashSet一样都是基于Map完成,也不支持get(int)操作获取指定位置的元素。TreeSet基于TreeMapTreeSet还提供了一些排序方面的支持。TreeSet非线程安全。

 

1.7HashMap

HashMapMap最常用的实现

HashMap(): loadFactor设置为0.75threshold设置为12,并创建一个大小为16Entry对象数组。

put(key,value):keynull时,HashMap的做法为获取Entry数组中的第一个Entry对象,并基于Entry对象的next属性遍历。若找到keynullEntry对象,则将value赋值为新的value

若没有keynullEntry,则增加一个Entry对象。如果此时Entry数组已用的大小>=threshold,则将Entry数组扩大为当前大小的两倍。扩大时对当前Entry对象数组中的元素重新hash,并填充数组,最后重新设置threshhold值。

解决hash冲突,来看看HashMap的解决方法。如果找到hash值相等的Entry对象,替换此Entry对象的值,并返回旧的值。如未找到,向对应的数组位置增加新的Entry对象,增加时采取的方法和keynull的情况基本相同,只是它替换指定位置的Entry对象。所以hashmap解决冲突的是链表的方式,而不是开放定址法。

get(key)

keynull的情况,直接获取数组中的第一个Entry对象,并且基于next属性进行遍历,寻找keynullEntry对象,如找到则返回null,对于key为非null的情况,则对key进行hash和按位与操作,找到对应的存储位置,然后获取次位置对应的Entry对象,基于next属性遍历,寻找hash值相等,且key相等的Entry对象,返回其value,如果未找到,则返回null

remove()

get相似,只是在找到匹配的key后,将数组上的元素的值置为其next元素的值。

containsKey()

通过getEntry方法来完成,getEntryget过程基本相同,知识找到匹配饿的key后,直接返回Entry对象,containsKey返回false或者true

keySet()

调用keySet()返回一个HashMap中的keySet实例。HashMap无法保证顺序输出,若要按顺序,使用TreeMapHashMap非线程安全的。

注意要点

HashMap

1HashMap采用数组方式存储keyvalue构成的Entry对象,无容量限制。

2HashMap基于key hash寻找Entry对象存放到数组的位置,对于hash冲突采用链表的方式解决。

3HashMap在插入元素时可能会要扩大数组的容量,在扩大容量时,要重新计算hash,并复制到新的数组。

4HashMap线程非安全

 

1.8TreeMap

实现方式:支持排序的Map实现,但是实现方式与HashMap并不相同。

TreeMap()

comparator属性赋值为null,控制存储顺序需要使用Comparator参数的构造器。

put(key,value)

基于红黑树的方式遍历,基于comparator来比较应放在左边还是右边,如果key相等,则替换其value,并返回结束put操作。如果没找到相等的key,则一直寻找左边或右边节点为null的元素,如comparator实现为null,则判断key是否为null,则抛出NullPointerException

TreeMap是典型的红黑树实现,因此它要求一定要有key比较的方法,要么传入Comparator实现,要么key实现Comparatable接口

get()

红黑树查找

remove()

首先要getEntry,然后将此Entry从红黑树上删除,并重新调整树上的相关的节点。

containsKey()

get方法一样,都是通过getEntry方法来完成,因此过程和get方法一样,只是containsKey直接判断返回的Entry是否为null,为null返回false,否则,返回true

keySet()

Iterator的遍历从跟开始,基于红黑树顺序完成。

注意要点

1.TreeMap基于红黑树,无容量限制

2.TreeMap非线程安全。