java集合里面的函数_java集合【1】——— 从集合接口框架说起
百里方欣
原创
关注
0点赞·155人阅读
(一) java集合分类
之前大概分为三种,Set,List,Map三种,JDK5之后,增加Queue.主要由Collection和Map两个接口衍生出来,同时Collection接口继承Iterable接口,所以我们也可以说java里面的集合类主要是由Iterable和Map两个接口以及他们的子接口或者其实现类组成。我们可以认为Collection接口定义了单列集合的规范,每次只能存储一个元素,而Map接口定义了双列集合的规范,每次能存储一对元素。
Iterable接口:主要是实现遍历功能
Collection接口: 允许重复
Set接口:无序,元素不可重复,访问元素只能通过元素本身来访问。
List接口:有序且可重复,可以根据元素的索引来访问集合中的元素。
Queue接口:队列集合
Map接口:映射关系,简单理解为键值对,Key不可重复,与Collection接口关系不大,只是个别函数使用到。
整个接口框架关系如下(来自百度百科):
(1) Iterable接口
1. 内部定义的方法
java集合最源头的接口,实现这个接口的作用主要是集合对象可以通过迭代器去遍历每一个元素。
源码如下:
// 返回一个内部元素为T类型的迭代器(JDK1.5只有这个接口)
Iterator iterator()
// 遍历内部元素,action意思为动作,指可以对每个元素进行操作(JDK1.8添加)
default void forEach(Consumer super T>action) {}
// 创建并返回一个可分割迭代器(JDK1.8添加),分割的迭代器主要是提供可以并行遍历元素的迭代器,可以适应现在cpu多核的能力,加快速度。
default Spliterator spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0)
}
从上面可以看出,foreach迭代以及可分割迭代,都加了default关键字,这个是Java 8 新的关键字,以前接口的所有接口,具体子类都必须实现,而对于deafult关键字标识的方法,其子类可以不用实现,这也是接口规范发生变化的一点。
下面我们分别展示三个接口的调用:
1.1 iterator方法
public static void iteratorHasNext(){
List list=new ArrayList()
list.add("Jam")
list.add("Jane")
list.add("Sam")
// 返回迭代器
Iterator iterator=list.iterator()
// hashNext可以判断是否还有元素
while(iterator.hasNext()){
//next()作用是返回当前指针指向的元素,之后将指针移向下个元素
System.out.println(iterator.next())
}
}
当然也可以使用for-each loop方式遍历
for (String item : list) {
System.out.println(item)
}
但是实际上,这种写法在class文件中也是会转成迭代器形式,这只是一个语法糖。class文件如下:
public class IterableTest {
public IterableTest() { }
public static void main(String[] args) {
iteratorHasNext()
}
public static void iteratorHasNext() {
List list = new ArrayList()
list.add("Jam")
list.add("Jane")
list.add("Sam")
Iterator iterator = list.iterator()
Iterator var2 = list.iterator()
while(var2.hasNext()) {
String item = (String)var2.next()
System.out.println(item)
}
}
}
需要注意的一点是,迭代遍历的时候,如果删除或者添加元素,都会抛出修改异常,这是由于快速失败【fast-fail】机制。
public static void iteratorHasNext(){
List list=new ArrayList()
list.add("Jam")
list.add("Jane")
list.add("Sam")
for (String item : list) {
if(item.equals("Jam")){
list.remove(item)
}
System.out.println(item)
}
}
从下面的错误我们可以看出,第一个元素是有被打印出来的,也就是remove操作是成功的,只是遍历到第二个元素的时候,迭代器检查,发现被改变了,所以抛出了异常。
Jam
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at IterableTest.iteratorHasNext(IterableTest.java:15)
at IterableTest.main(IterableTest.java:7)
1.2 forEach方法
其实就是把对每一个元素的操作当成了一个对象传递进来,对每一个元素进行处理。
default void forEach(Consumer super T>action) {
Objects.requireNonNull(action)
for (T t : this) {
action.accept(t)
}
}
```java
当然像ArrayList自然也是有自己的实现的,那我们就可以使用这样的写法,简洁优雅。forEach方法在java8中参数是`java.util.function.Consumer`,可以称为**消费行为**或者说**动作**类型。
```java
list.forEach(x ->System.out.print(x))
同时,我们只要实现Consumer接口,就可以自定义动作,如果不自定义,默认迭代顺序是按照元素的顺序。
public class ConsumerTest {
public static void main(String[] args) {
List list=new ArrayList()
list.add("Jam")
list.add("Jane")
list.add("Sam")
MyConsumer myConsumer = new MyConsumer()
Iterator it = list.iterator()
list.forEach(myConsumer)
}
static class MyConsumer implements Consumer {
@Override
public void accept(Object t) {
System.out.println("自定义打印:" + t)
}
}
}
输出的结果:
自定义打印:Jam
自定义打印:Jane
自定义打印:Sam
1.3 spliterator方法
这是一个为了并行遍历数据元素而设计的迭代方法,返回的是Spliterator,是专门并行遍历的迭代器。以发挥多核时代的处理器性能,java默认在集合框架中提供了一个默认的Spliterator实现,底层也就是Stream.isParallel()实现的,我们可以看一下源码:
// stream使用的就是spliterator
default Stream stream() {
return StreamSupport.stream(spliterator(), false)
}
default Spliterator spliterator() {
return Spliterators.spliterator(this, 0)
}
public static Stream stream(Spliterator spliterator, boolean parallel) {
Objects.requireNonNull(spliterator)
return new ReferencePipeline.Head<>(spliterator,
StreamOpFlag.fromCharacteristics(spliterator),
parallel)
}
使用的方法如下:
public static void spliterator(){
List list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10")
// 获取可迭代器
Spliterator spliterator = list.spliterator()
// 一个一个遍历
System.out.println("tryAdvance: ")
spliterator.tryAdvance(item->System.out.print(item+" "))
spliterator.tryAdvance(item->System.out.print(item+" "))
System.out.println("\n-------------------------------------------")
// 依次遍历剩下的
System.out.println("forEachRemaining: ")
spliterator.forEachRemaining(item->System.out.print(item+" "))
System.out.println("\n------------------------------------------")
// spliterator1:0~10
Spliterator spliterator1 = list.spliterator()
// spliterator1:6~10 spliterator2:0~5
Spliterator spliterator2 = spliterator1.trySplit()
// spliterator1:8~10 spliterator3:6~7
Spliterator spliterator3 = spliterator1.trySplit()
System.out.println("spliterator1: ")
spliterator1.forEachRemaining(item->System.out.print(item+" "))
System.out.println("\n------------------------------------------")
System.out.println("spliterator2: ")
spliterator2.forEachRemaining(item->System.out.print(item+" "))
System.out.println("\n------------------------------------------")
System.out.println("spliterator3: ")
spliterator3.forEachRemaining(item->System.out.print(item+" "))
}
tryAdvance() 一个一个元素进行遍历
forEachRemaining() 顺序地分块遍历
trySplit()进行分区形成另外的 Spliterator,使用在并行操作中,分出来的是前面一半,就是不断把前面一部分分出来
结果如下:
tryAdvance:
1 2
-------------------------------------------
forEachRemaining:
3 4 5 6 7 8 9 10
------------------------------------------
spliterator1:
8 9 10
------------------------------------------
spliterator2:
1 2 3 4 5
------------------------------------------
spliterator3:
6 7
还有一些其他的用法在这里就不列举了,主要是trySplit()之后,可以用于多线程遍历。理想的时候,可以平均分成两半,有利于并行计算,但是不是一定平分的。
2. Collection接口 extend Iterable
Collection接口可以算是集合类的一个根接口之一,一般不能够直接使用,只是定义了一个规范,定义了添加,删除等管理数据的方法。继承Collection接口的有List,Set,Queue,不过Queue定义了自己的一些接口,相对来说和其他的差异比较大。
2.1 内部定义的方法
源码如下:
boolean add(Object o) //添加元素
boolean remove(Object o) //移除元素
boolean addAll(Collection c) //批量添加
boolean removeAll(Collection c) //批量移除
void retainAll(Collection c) // 移除在c中不存在的元素
void clear() //清空集合
int size() //集合大小
boolean isEmpty() //是否为空
boolean contains(Object o) //是否包含在集合中
boolean containsAll(Collection c) //是否包含所有的元素
Iterator iterator() // 获取迭代器
Object[] toArray() // 转成数组
default boolean removeIf(Predicate super E>filter) {} // 删除集合中复合条件的元素,删除成功返回true
boolean equals(Object o)
int hashCode()
default Spliterator spliterator() {} //获取可分割迭代器
default Stream stream() {} //获取流
default Stream parallelStream() {} //获取并行流
里面获取并行流的方法parallelStream(),其实就是通过默认的ForkJoinPool(主要用来使用分治法(Divide-and-Conquer Algorithm)来解决问题),提高多线程任务的速度。我们可以使用ArrayList来演示一下平行处理能力。例如下面的例子,输出的顺序就不一定是1,2,3...,可能是乱序的,这是因为任务会被分成多个小任务,任务执行是没有特定的顺序的。
List list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)
list.parallelStream()
.forEach(out::println)
2.2 继承Collection的主要接口
graph LR
Collection -->List-有顺序,可重复
List-有顺序,可重复 -->LinkedList-使用链表实现,线程不安全
List-有顺序,可重复 -->ArrayList-数组实现,线程不安全
List-有顺序,可重复 -->Vector-数组实现,线程安全
Vector-数组实现,线程安全 -->Stack-堆栈,先进后出
Collection-->Set-不可重复,内部排序
Set-不可重复,内部排序-->HashSet-hash表存储
HashSet-hash表存储-->LinkHashSet-链表维护插入顺序
Set-不可重复,内部排序-->TreeSet-二叉树实现,排序
Collection-->Queue-队列,先进先出
2.2.1 List extend Collection
继承于Collection接口,有顺序,取出的顺序与存入的顺序一致,有索引,可以根据索引获取数据,允许存储重复的元素,可以放入为null的元素。
最常见的三个实现类就是ArrayList,Vector,LinkedList,ArrayList和Vector都是内部封装了对数组的操作,唯一不同的是,Vector是线程安全的,而ArrayList不是,理论上ArrayList操作的效率会比Vector好一些。
里面是接口定义的方法:
int size()//获取大小
boolean isEmpty()//判断是否为空
boolean contains(Object o)//是否包含某个元素
Iterator iterator()//获取迭代器
Object[] toArray()// 转化成为数组(对象)
T[] toArray(T[] a)// 转化为数组(特定位某个类)
boolean add(E e)//添加
boolean remove(Object o)//移除元素
boolean containsAll(Collection>c)// 是否包含所有的元素
boolean addAll(Collection extends E>c)//批量添加
boolean addAll(int index, Collection extends E>c)//批量添加,指定开始的索引
boolean removeAll(Collection>c)//批量移除
boolean retainAll(Collection>c)//将c中不包含的元素移除
default void replaceAll(UnaryOperator operator) {}//替换
default void sort(Comparator super E>c) {}// 排序
void clear()//清除所有的元素
boolean equals(Object o)//是否相等
int hashCode()//计算获取hash值
E get(int index)//通过索引获取元素
E set(int index, E element)//修改元素
void add(int index, E element)//在指定位置插入元素
E remove(int index)//根据索引移除某个元素
int indexOf(Object o)//根据对象获取索引
int lastIndexOf(Object o)//获取对象元素的最后一个元素
ListIterator listIterator()// 获取List迭代器
ListIterator listIterator(int index)// 根据索引获取当前的位置的迭代器
List subList(int fromIndex, int toIndex)//截取某一段数据
default Spliterator spliterator(){} //获取可切分迭代器
上面的方法都比较简单,值得一提的是里面出现了ListIterator,这是一个功能更加强大的迭代器,继承于Iterator,只能用于List类型的访问,拓展功能例如:通过调用listIterator()方法获得一个指向List开头的ListIterator,也可以调用listIterator(n)获取一个指定索引为n的元素的ListIterator,这是一个可以双向移动的迭代器。
操作数组索引的时候需要注意,由于List的实现类底层很多都是数组,所以索引越界会报错IndexOutOfBoundsException。
说起List的实现子类:
ArrayList:底层存储结构是数组结构,增加删除比较慢,查找比较快,是最常用的List集合。线程不安全。
LinkedList:底层是链表结构,增加删除比较快,但是查找比较慢。线程不安全。
Vector:和ArrayList差不多,但是是线程安全的,即同步。
2.2.2 Set extend Collection
Set接口,不允许放入重复的元素,也就是如果相同,则只存储其中一个。
下面是源码方法:
int size()//获取大小
boolean isEmpty()//是否为空
boolean contains(Object o)//是否包含某个元素
Iterator iterator()//获取迭代器
Object[] toArray()//转化成为数组
T[] toArray(T[] a)//转化为特定类的数组
boolean add(E e)//添加元素
boolean remove(Object o)//移除元素
boolean containsAll(Collection>c)//是否包含所有的元素
boolean addAll(Collection extends E>c)//批量添加
boolean retainAll(Collection>c)//移除所有不存在于c集合中的元素
boolean removeAll(Collection>c)//移除所有在c集合中存在的元素
void clear()//清空集合
boolean equals(Object o)//是否相等
int hashCode()//计算hashcode
default Spliterator spliterator() {} //获取可分割迭代器
主要的子类:
HashSet
允许空值
通过HashCode方法计算获取hash值,确定存储位置,无序。
LinkedHashSet
HashSet的子类
有顺序
TreeSet
如果无参数构建Set,则需要实现Comparable方法。
亦可以创建时传入比较方法,用于排序。
2.2.3 Queue extend Collection
队列接口,在Collection接口的接触上添加了增删改查接口定义,一般默认是先进先出,即FIFO,除了优先队列和栈,优先队列是自己定义了排序的优先顺序,队列中不允许放入null元素。
下面是源码:
boolean add(E e)//插入一个元素到队列,失败时返回IllegalStateException (如果队列容量不够)
boolean offer(E e)//插入一个元素到队列,失败时返回false
E remove()//移除队列头的元素并移除
E poll()//返回并移除队列的头部元素,队列为空时返回null
E element()//返回队列头元素
E peek()//返回队列头部的元素,队列为空时返回null
主要的子接口以及实现类有:
Deque(接口):Queue的子接口,双向队列,可以从两边存取
ArrayDeque:Deque的实现类,底层用数组实现,数据存贮在数组中
AbstractQueue:Queue的子接口,仅实现了add、remove和element三个方法
PriorityQueue:按照默认或者自己定义的顺序来排序元素,底层使用堆(完全二叉树)实现,使用动态数组实现,
BlockingQueue: 在java.util.concurrent包中,阻塞队列,满足当前无法处理的操作。
(2) Map接口
定义双列集合的规范Map,每次存储一对元素,即key和value。
key的类型可以和value的类型相同,也可以不同,任意的引用类型都可以。
key是不允许重复的,但是value是可以重复的,所谓重复是指计算的hash值系统。
下面的源码的方法:
V put(K key, V value)// 添加元素
V remove(Object key)// 删除元素
void putAll(Map extends K, ? extends V>m)// 批量添加
void clear() // 移除所有元素
V get(Object key)// 通过key查询元素
int size()// 查询集合大小
boolean isEmpty()// 集合是否为空
boolean containsKey(Object key)// 是否包含某个key
boolean containsValue(Object value)// 是否包含某个value
Set keySet()// 获取所有key的set集合
Collection values()// 获取所有的value的set集合
Set>entrySet()// 返回键值对的set,每一个键值对是一个entry对象
boolean equals(Object o)// 用于比较的函数
int hashCode()// 计算hashcode
default V getOrDefault(Object key, V defaultValue) // 获取key对应的Value,没有则返回默认值()
default void forEach(BiConsumer super K, ? super V>action) {} // 遍历
default void replaceAll(BiFunction super K, ? super V, ? extends V>function) {} // 批量替换
// 缺少这个key的时候才会添加进去
// 返回值是是key对应的value值,如果不存在,则返回的是刚刚放进去的value
default V putIfAbsent(K key, V value) {}
default boolean remove(Object key, Object value) {} // 移除元素
default boolean replace(K key, V oldValue, V newValue) {} // 替换
default V replace(K key, V value) {} //替换
// 和putIfAbsent有点像,只不过传进去的mappingFunction是映射函数,也就是如果不存在key对应的value,将会执行函数,函数返回值会被当成value添加进去,同时返回新的value值
default V computeIfAbsent(K key,Function super K, ? extends V>mappingFunction) {}
// 和computeIfAbsent方法相反,只有key存在的时候,才会执行函数,并且返回
default V computeIfPresent(K key,BiFunction super K, ? super V, ? extends V>remappingFunction) {}
// 不管如何都会执行映射函数,返回value
default V compute(K key,BiFunction super K, ? super V, ? extends V>remappingFunction) {}
default V merge(K key, V value,BiFunction super V, ? super V, ? extends V>remappingFunction) {}
值得注意的是,Map里面定义了一个Entry类,其实就是定义了一个存储数据的类型,一个entry就是一个.
Map的常用的实现子类:
HashMap:由数组和链表组成,线程不安全,无序。
LinkedHashMap:如果我们需要是有序的,那么就需要它,时间和空间效率没有HashMap那么高,底层是维护一条双向链表,保证了插入的顺序。
ConcurrentHashMap:线程安全,1.7JDK使用锁分离,每一段Segment都有自己的独立锁,相对来说效率也比较高。JDK1.8抛弃了Segment,使用Node数组+链表和红黑树实现,在线程安全控制上使用Synchronize和CAS,可以认为是优化的线程安全的HashMap。
HashTable:对比与HashMap主要是使用关键字synchronize,加上同步锁,线程安全。
(二)总结
这些集合原始接口到底是什么?为什么需要?
我想,这些接口其实都是一种规则/规范的定义,如果不这么做也可以,所有的子类自己实现,但是从迭代以及维护的角度来说,这就是一种抽象或者分类,比如定义了Iterator接口,某一些类就可以去继承或者实现,那就得遵守这个规范/契约。可以有所拓展,每个子类的拓展不一样,所以每个类就各有所长,但是都有一个中心,就是原始的集合接口。比如实现Map接口的所有类的中心思想都不变,只是各有所长,各分千秋,形成了大千集合世界。
【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。
平日时间宝贵,只能使用晚上以及周末时间学习写作,关注我,我们一起成长吧~
JAVA集合框架特征介绍(详细的去看看动力节点的java基础大全301集就知道了)
数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构通常称为Java集合框架。在平常的学习开发中,灵活熟练地使用这些集合框架,可以很明显地提高我们的开发效率,当然仅仅会用还是不够的,理解其中的设计思想与原理才能更好地提高我们的开发水平。下面是自己对Java集合框架方面的学习总结。
一、概述
二、Collection接口 1.List 2.Set 3.Queue
三、Map接口 1.HashMap实现原理 2.其它Map实现类
四、其它集合类
五、总结
一、概述
在Java 2之前,Java是没有完整的集合框架的。它只有一些简单的可以自扩展的容器类,比如Vector,Stack,Hashtable等。这些容器类在使用的过程中由于效率问题饱受诟病,因此在Java 2中,Java设计者们进行了大刀阔斧的整改,重新设计,于是就有了现在的集合框架。需要注意的是,之前的那些容器类库并没有被弃用而是进行了保留,主要是为了向下兼容的目的,但我们在平时使用中还是应该尽量少用。
Java集合框架
从上面的集合框架图可以看到,Java集合框架主要包括两种类型的容器,一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。Collection接口又有3种子类型,List、Set和Queue,再下面是一些抽象类,最后是具体实现类,常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。
二、Collection接口
Collection接口是处理对象集合的根接口,其中定义了很多对元素进行操作的方法,AbstractCollection是提供Collection部分实现的抽象类。下图展示了Collection接口中的全部方法。
Collection接口结构
其中,有几个比较常用的方法,比如方法add()添加一个元素到集合中,addAll()将指定集合中的所有元素添加到集合中,contains()方法检测集合中是否包含指定的元素,toArray()方法返回一个表示集合的数组。Collection接口有三个子接口,下面详细介绍。
1.List
List接口扩展自Collection,它可以定义一个允许重复的有序集合,从List接口中的方法来看,List接口主要是增加了面向位置的操作,允许在指定位置上操作元素,同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现,AbstractSequentialList扩展自AbstractList,主要是提供对链表的支持。下面介绍List接口的两个重要的具体实现类,也是我们可能最常用的类,ArrayList和LinkedList。
ArrayList
通过阅读ArrayList的源码,我们可以很清楚地看到里面的逻辑,它是用数组存储元素的,这个数组可以动态创建,如果元素个数超过了数组的容量,那么就创建一个更大的新数组,并将当前数组中的所有元素都复制到新数组中。假设第一次是集合没有任何元素,下面以插入一个元素为例看看源码的实现。
1、方法add(E e)向集合中添加指定元素。 public boolean add(E e) {
ensureCapacityInternal(size + 1) // Increments modCount!!
elementData[size++] = e return true
}2、此方法主要是确定将要创建的数组大小。 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)
}
ensureExplicitCapacity(minCapacity)
} private void ensureExplicitCapacity(int minCapacity) {
modCount++ if (minCapacity - elementData.length >0)
grow(minCapacity)
}3、最后是创建数组,可以明显的看到先是确定了添加元素后的大小之后将元素复制到新数组中。 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length int newCapacity = oldCapacity + (oldCapacity >>1) if (newCapacity - minCapacity <0)
newCapacity = minCapacity if (newCapacity - MAX_ARRAY_SIZE >0)
newCapacity = hugeCapacity(minCapacity) // minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity)
}
LinkedList
同样,我们打开LinkedList的源文件,不难看到LinkedList是在一个链表中存储元素。
在学习数据结构的时候,我们知道链表和数组的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同,同样,ArrayList与LinkedList也是如此,实际使用中我们需要根据特定的需求选用合适的类,如果除了在末尾外不能在其他位置插入或者删除元素,那么ArrayList效率更高,如果需要经常插入或者删除元素,就选择LinkedList。
2.Set
Set接口扩展自Collection,它与List的不同之处在于,规定Set的实例不包含重复的元素。在一个规则集内,一定不存在两个相等的元素。AbstractSet是一个实现Set接口的抽象类,Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。
散列集HashSet
散列集HashSet是一个用于实现Set接口的具体类,可以使用它的无参构造方法来创建空的散列集,也可以由一个现有的集合创建散列集。在散列集中,有两个名词需要关注,初始容量和客座率。客座率是确定在增加规则集之前,该规则集的饱满程度,当元素个数超过了容量与客座率的乘积时,容量就会自动翻倍。
一、List接口List是一个继承于Collection的接口,即List是集合中的一种。List是有序的队列,List中的每一个元素都有一个索引;第一个元素的索引值是0,往后的元素的索引值依次+1。和Set不同,List中允许有重复的元素。实现List接口的集合主要有:ArrayList、LinkedList、Vector、Stack。
ArrayList
ArrayList是一个动态数组,也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量:
private static final int DEFAULT_CAPACITY = 10
随着容器中的元素不断增加,容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查,当快溢出时,就会进行扩容操作。所以如果我们明确所插入元素的多少,最好指定一个初始容量值,避免过多的进行扩容操作而浪费时间、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行,也就是说,添加 n 个元素需要 O(n) 时间(由于要考虑到扩容,所以这不只是添加元素会带来分摊固定时间开销那样简单)。
ArrayList擅长于随机访问。同时ArrayList是非同步的。
LinkedList
同样实现List接口的LinkedList与ArrayList不同,ArrayList是一个动态数组,而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get,remove,insert方法在LinkedList的首部或尾部。
由于实现的方式不同,LinkedList不能随机访问,它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端,节约一半时间)。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
与ArrayList一样,LinkedList也是非同步的。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:
List list = Collections.synchronizedList(new LinkedList(…))
Vector
与ArrayList相似,但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。
Stack
Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
二、Set接口
Set是一个继承于Collection的接口,Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行null的存在但是仅有一个。由于Set接口的特殊性,所有传入Set集合中的元素都必须不同,关于API方面。Set的API和Collection完全一样。实现了Set接口的集合有:HashSet、TreeSet、LinkedHashSet、EnumSet。
HashSet
HashSet堪称查询速度最快的集合,因为其内部是以HashCode来实现的。集合元素可以是null,但只能放入一个null。它内部元素的顺序是由哈希码来决定的,所以它不保证set的迭代顺序;特别是它不保证该顺序恒久不变。
TreeSet
TreeSet是二叉树实现的,基于TreeMap,生成一个总是处于排序状态的set,内部以TreeMap来实现,不允许放入null值。它是使用元素的自然顺序对元素进行排序,或者根据创建Set时提供的 Comparator 进行排序,具体取决于使用的构造方法。
LinkedHashSet
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet。
三、Map接口
Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value,所以它不能存在相同的key值,当然value值可以相同。实现map的集合有:HashMap、HashTable、TreeMap、WeakHashMap。
HashMap
以哈希表数据结构实现,查找对象时通过哈希函数计算其位置,它是为快速查询而设计的,其内部定义了一个hash表数组(Entry[] table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用散列链表的形式将所有相同哈希地址的元素串起来,可能通过查看HashMap.Entry的源码它是一个单链表结构。
HashTable
也是以哈希表数据结构实现的,解决冲突时与HashMap也一样也是采用了散列链表的形式。HashTable继承Dictionary类,实现Map接口。其中Dictionary类是任何可将键映射到相应值的类(如 Hashtable)的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中,每个键至多与一个值相关联。Map是”key-value键值对”接口。 HashTable采用”拉链法”实现哈希表不过性能比HashMap要低。
TreeMap
有序散列表,实现SortedMap接口,底层通过红黑树实现。
WeakHashMap
谈WeakHashMap前先看一下Java中的引用(强度依次递减)
强引用:普遍对象声明的引用,存在便不会GC
软引用:有用但并非必须,发生内存溢出前,二次回收
弱引用:只能生存到下次GC之前,无论是否内存足够
虚引用:唯一目的是在这个对象被GC时能收到一个系统通知
以弱键实现的基于哈希表的Map。在 WeakHashMap 中,当某个键不再正常使用时,将自动移除其条目。更精确地说,对于一个给定的键,其映射的存在并不阻止垃圾回收器对该键的丢弃,这就使该键成为可终止的,被终止,然后被回收。丢弃某个键时,其条目从映射中有效地移除,因此,该类的行为与其他的 Map 实现有所不同。null值和null键都被支持。该类具有与HashMap类相似的性能特征,并具有相同的效能参数初始容量和加载因子。像大多数集合类一样,该类是不同步的。
四、总结
1、List、Set都是继承自Collection接口,Map则不是。
2、List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉,(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set 的Object必须定义equals()方法 ,另外list支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。)
3、Set和List对比:
Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。
4、Map适合储存键值对的数据
5、线程安全集合类与非线程安全集合类 :
LinkedList、ArrayList、HashSet是非线程安全的,Vector是线程安全的
HashMap是非线程安全的,HashTable是线程安全的
StringBuilder是非线程安全的,StringBuffer是线程安全的。