1.集合包
常用的是Collection与Map两个接口的实现类。
Collection常用的两种接口:List和Set。
List实现类:ArrayList、LinkedList、Vector、Stack。
Set实现类:HashSet、TreeSet。
Collection主要包括创建、增加、删除、获取单个对象、遍历对象、判断对象是否存在与Collection中、对象的排序。
1.1ArrayList
创建:ArrayList采用数组的方式来存放对象,创建一个大小为10的Object数组。
插入对象:
问题:传入对象数组满了,怎么办?
当调用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(int,E)这样的方法,允许元素直接插入指定的int位置上(这个方法要确保插入的位置存在,确保容量够用)。但与add()方法不同,他要将当前数组的对象进行复制,将其后的数据都往后挪动一位,然后才能将指定的index位置的赋值为传入的对象。
除了add(),ArrayList还提供了set(int ,E)方法替换原来指定位置的对象。
删除对象:
remove(E):遍历数组,将找到的相同对象删除(如果有重复的只删除一个),将index后面的对象往前复制一位。remove(int)删除指定位置的对象,它比remove(E):多一个数组范围的检测,但少了对象位置的查找,性能更好。
获取单个对象:
获得数组元素的位置,先做范围检测,然后可直接返回数组中位于此位置的对象。
遍历对象:
Iterator由ArrayList的父类AbstractList实现,当每次调用iterator方法时,都会创建一个新的AbstractList内部Itr的实例。当调用此实例的hasNext方法时,比较指定位置的数组是否和数组中已有的元素大小相等。如果相等放回false,否则返回true。
判断对象是否存在:
Contains(E):遍历ArrayList已有元素。
indexOf和lastIndexOf是ArrayList用于获取对象所在位置的方法,IndexOf从前往后寻找,lastIndexOf从后向前。
注意
1.ArrayList基于数组,无容量限制。
2.ArrayList插入元素可能需要扩容,删除元素并不会减少数组的容量(如果希望相应的缩小数组容量,可以调用ArrayList的trimToSize()),在查找元素时需要遍历数组,对于非null元素采用equals的方式寻找。
3.ArrayList非线程安全。
1.2LinkedList
实现方式:基于双向链表机制,就是集合中的每个元素都知道其前一个元素及其后一个元素的位置。在LinkedList中,内部类Entry类来代表集合中的元素,元素值赋给element属性,Entry的next属性指向后一个元素,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的位置是否等同于LinkedList的size变量,等于返回true,不等于返回false。如在遍历中增加或删除,则会抛出ConcurrentModificationException异常。也可以通过hasPrevious和prevoius来完成遍历。
contains(E)
LinkedList也是采用的遍历所有元素的方法。
注意:
1.LinkedList基于双向链表机制实现
2.LinkedList插入与删除原理
3.LinkedList是非线程安全的
1.3Vector
Vector() 默认创建一个大小为10的Object数组,设定一个参数capacityIncrement设置为0。
add(E):Vector中add方法加了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的弹出和压入,提供了push、pop、peek三个主要的方法。
push
通过调用Vector中的addElement来完成。
pop
调用peek获取元素,并同时删除数组的最后一个元素。
peek
Peek根据当前Object数组的大小,并取得最后一个元素
1.5HashSet
HashSet是Set接口的实现,与List明显的区别在于Set不允许元素重复,而List允许。Set为了做到不允许元素重复,采用的是基于HashMap来实现。
HashSet
要创建一个HashMap对象。
add()
调用HashMap的put()方法来完成此操作,将需要增加的元素作为map中key,value则传入一个之前已创建的Object对象。
remove(E)
使用HashMap的remove(E)方法来完成此操作。
Iterator
调用HashMap的keySet的iterator方法来完成此操作。HashSet不支持通过get(int)获取指定位置的元素,只能通过iterator方法获取。
注意要点:
对于HashSet而言,需要注意以下几点:
1.HashSet基于HashMap实现,无容量限制
2.HashSet是非线程安全的。
1.6TreeSet
TreeSet和HashSet主要不同在于TreeSet对于排序的支持,TreeSet基于TreeMap实现
Iterator
调用TreeSet的navigableKeySet的iterator方法完成此操作。
TreeSet和HashSet一样都是基于Map完成,也不支持get(int)操作获取指定位置的元素。TreeSet基于TreeMap,TreeSet还提供了一些排序方面的支持。TreeSet非线程安全。
1.7HashMap
HashMap是Map最常用的实现
HashMap(): 将loadFactor设置为0.75,threshold设置为12,并创建一个大小为16的Entry对象数组。
put(key,value):key为null时,HashMap的做法为获取Entry数组中的第一个Entry对象,并基于Entry对象的next属性遍历。若找到key为null的Entry对象,则将value赋值为新的value。
若没有key为null的Entry,则增加一个Entry对象。如果此时Entry数组已用的大小>=threshold,则将Entry数组扩大为当前大小的两倍。扩大时对当前Entry对象数组中的元素重新hash,并填充数组,最后重新设置threshhold值。
解决hash冲突,来看看HashMap的解决方法。如果找到hash值相等的Entry对象,替换此Entry对象的值,并返回旧的值。如未找到,向对应的数组位置增加新的Entry对象,增加时采取的方法和key为null的情况基本相同,只是它替换指定位置的Entry对象。所以hashmap解决冲突的是链表的方式,而不是开放定址法。
get(key)
key为null的情况,直接获取数组中的第一个Entry对象,并且基于next属性进行遍历,寻找key为null的Entry对象,如找到则返回null,对于key为非null的情况,则对key进行hash和按位与操作,找到对应的存储位置,然后获取次位置对应的Entry对象,基于next属性遍历,寻找hash值相等,且key相等的Entry对象,返回其value,如果未找到,则返回null。
remove()
与get相似,只是在找到匹配的key后,将数组上的元素的值置为其next元素的值。
containsKey()
通过getEntry方法来完成,getEntry与get过程基本相同,知识找到匹配饿的key后,直接返回Entry对象,containsKey返回false或者true。
keySet()
调用keySet()返回一个HashMap中的keySet实例。HashMap无法保证顺序输出,若要按顺序,使用TreeMap。HashMap非线程安全的。
注意要点
HashMap
1HashMap采用数组方式存储key、value构成的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非线程安全。