大致梳理一下java的集合框架~

集合框架

  Java 集合框架主要包括两种类型的容器,Collection 接口又有 3 种子类型,List、Set 和 Queue,再下面是一些抽象类,最后是具体实现类,常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

  集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容:

  • 两种容器:一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。

  • Collection接口的实现类:AbstractCollection

    Collection接口的三种子接口:list、set、queue

    Map接口的实现类:AbstractMap

    Map接口没有子接口

  • list的实现类:LinkedList、ArrayList

    Set的实现类:HashSet、LinkedHashSet、TreeSet

    Queue的实现类:

    继承AbstractCollection的类:AbstractList、AbstractSet

  • 继承AbstractMap的类:HashMap、TreeMap、WeakHashMap、LinkedHashMap、IdentityHashMap

List接口的实现

  List集合的特点就是存取有序,可以存储重复的元素,可以用下标进行元素的操作

ArrayList

  1. ArrayList是List接口的可变数组非同步实现,并允许包括null在内的所有元素。
  2. 底层使用数组实现
  3. 该集合是可变长度数组,数组扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量增长大约是其容量的1.5倍,这种操作的代价很高。
  4. 采用了Fail-Fast机制,面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险
  5. remove方法会让下标到数组末尾的元素向前移动一个单位,并把最后一位的值置空,方便GC

LinkedList

LinkedList数据结构

  说明:如上图所示,LinkedList底层使用的双向链表结构,有一个头结点和一个尾结点,双向链表意味着我们可以从头开始正向遍历,或者是从尾开始逆向遍历,并且可以针对头部和尾部进行相应的操作。

  1. LinkedList是List接口的双向链表非同步实现,并允许包括null在内的所有元素。
  2. 底层的数据结构是基于双向链表的,该数据结构我们称为节点
  3. 双向链表节点对应的类Node的实例,Node中包含成员变量:prev,next,item。其中,prev是该节点的上一个节点,next是该节点的下一个节点,item是该节点所包含的值。
  4. 它的查找是二分查找,先判断index是在链表的哪一半,然后再去对应区域查找,这样最多只要遍历链表的一半节点即可找到:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 获取双向链表中指定位置的节点    
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
// 获取index处的节点。
// 若index < 双向链表长度的1/2,则从前先后查找;
// 否则,从后向前查找。
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}

注意细节:位运算与直接做除法的区别。先将index与长度size的一半比较,如果index<size/2,就只从位置0往后遍历到位置index处,而如果index>size/2,就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历

Vector

  Vector 也是一个动态数组结构,一个元老级别的类,早在 jdk1.1 就引入进来类,之后在 jdk1.2 里引进 ArrayList,ArrayList 大部分的方法和 Vector 比较相似,两者是不同的,Vector 是允许同步访问的,Vector 中的操作是线程安全的,但是效率低,而 ArrayList 所有的操作都是异步的,执行效率高,但不安全!

  关于Vector,现在用的很少了,因为里面的getsetadd等方法都加了synchronized,所以,执行效率会比较低,如果需要在多线程中使用,可以采用下面语句创建 ArrayList 对象

1
List list =Collections.synchronizedList(new ArrayList());

也可以考虑使用复制容器 java.util.concurrent.CopyOnWriteArrayList进行操作,例如:

1
final CopyOnWriteArrayList cowList = new CopyOnWriteArrayList(Object);

Stack

  Stack 是 Vector 的一个子类,本质也是一个动态数组结构,不同的是,它的数据结构是先进后出,取名叫栈。关于Stack,现在用的也很少,因为有个ArrayDeque双端队列,可以替代Stack所有的功能,并且执行效率比它高。

Set的实现

Set集合的特点:元素不重复,存取无序,无下标;

HashSet

  1. HashSet由哈希表(实际上是一个HashMap实例)支持,不保证set的迭代顺序,并允许使用null元素。
  2. 基于HashMap实现,API也是对HashMap的行为进行了封装,可参考HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 底层使用HashMap来保存HashSet中所有元素。  
private transient HashMap<E,Object> map;

// 定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。
private static final Object PRESENT = new Object();

/**
* 默认的无参构造器,构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap,并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

LinkedHashSet

  对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同。

  LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。

  对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。

  LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可。

### TreeSet

  使用TreeMap作为底层实现。

  为什么要这么设计呢?我的理解是:用空间换时间。 虽然付出了O(n)的空间,但是常规操作,如add()remove()contains()的时间界从原来的O(n)被优化到了log(n)时间界。在现在这个内存越来便宜的时代,这样的交换是非常值得的。

Map的实现

TreeMap

  SortedMap 的一种实现,与 HashMap 不同, TreeMap 的底层就是一颗红黑树,它的 containsKey()get()put()remove() 方法的时间复杂度是 log(n) ,并且它是按照 key 的自然顺序(或者指定排序)排列,与 LinkedHashMap 不同, LinkedHashMap 保证了元素是按照插入的顺序排列。

LinkedHashMap

  1. LinkedHashMap继承于HashMap,底层使用哈希表和双向链表来保存所有元素,并且它是非同步,允许使用null值和null键。
  2. 基本操作与父类HashMap相似,通过重写HashMap相关方法,重新定义了数组中保存的元素Entry,来实现自己的链接列表特性。该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而构成了双向链接列表。

 LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

 LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

LinkedHashMap和TreeMap

  LinkedHashMap 和 TreeMap 都可以保证某种顺序,但二者还是很不同的

  • linkedHashMap通常提供的是遍历顺序符合插入顺序,他的实现是通过条目维护一个双向链表。
  • 对于TreeMap他的整体顺序是由键的顺序关系决定的,通过compartoar来决定。

Hashtable

  和HashMap一样,Hashtable 也是一个散列表,它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。Hashtable 的函数都是同步的,这意味着它是线程安全的。它的key、value都不可以为null。此外,Hashtable中的映射不是有序的。

  • HashMap允许将 null 作为一个 entry 的 key 或者 value,而 Hashtable 不允许。
  • HashMap 把 Hashtable 的 contains 方法去掉了,改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。
  • HashTable 继承自 Dictionary 类,而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。
  • HashTable 的方法是 Synchronize 的,而 HashMap 不是,在多个线程访问 Hashtable 时,不需要自己为它的方法实现同步,而 HashMap 就必须为之提供外同步。
  • Hashtable 和 HashMap 采用的 hash/rehash 算法都大概一样,所以性能不会有很大的差异。
联系我

评论