Java集合类简介
Java集合框架的基本接口、类层级结果如下:
java.util.Collection[接口]
- java.util.List[接口]
- java.util.AarrayList
- java.util.LinkedList
- java.util.Vector
- java.util.Stack
- java.util.Set[接口]
- java.util.HashSet
- java.util.SortedSet[接口]
- java.util.TreeSet
- java.util.Queue
java.util.Map[接口]
- java.util.SortedMap[接口]
- java.util.TreeMap
- java.util.HashMap
- java.util.HashTable
- java.util.LinkedHashMap
- java.util.WeakHashMap
1、Collection
是最基本的集合类型，所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个共的Collection，有一个collection参数的构造函数用于创建一个新的collection，这个新的collection与传入的collection有相同的元素。
若要检查collection中的元素，可以使用foreach进行遍历，也可以使用迭代器，Collection支持iterator()方法，通过该方法可以访问Collection中的每一个元素。
用法如下:1
2
3
4Iterator it=collection.iterator();
while(it.hasNext()){
Object obj=it.next();
}
是不是有点像java从mysql取数据，差不多意思一样。
Set和List是由Collection派生的两个接口。
1.1、List接口
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引的位置来访问List中的元素，类似于Java数组。
List允许有相同的元素存在。
除了具有Collection接口必备的iterator()方法外，还提供了listIterator()方法，返回一个ListIterator接口。
实现List接口的常用类有LinkedList(链表)、ArrayList(数组)、Vector和Stack(栈)
1.1.1、LinkedList类
LinkedList实现了List类接口，允许null元素。此外LinkedList提供额外的get、remove、insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack)，队列(queue)或双向队列(deque)。
LinkedList没有同步方法。如果多个线程想访问同一个List，则必须自己实现访问同步。一种解决办法是在创建List时构造一个同步的List:1
List list=Collection.synchronizedList(new LinkedList())
1.1.2、ArrayList类
ArrayList实现了可变大小的数组。他允许所有元素，包括null。ArrayList没有同步。size(),isEmpty(),get(),set()方法运行时间为常数。但是add()方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量，即用于存储元素的数组大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity()方法来增加ArrayList容量已提高插入效率。
1.2、Vector类
Vector非常类似ArrayList，但是Vector是同步的。当一个iterator被创建而且这正在被使用，另一个线程改变了Vector状态，这时调用iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。
1.3、stack类
Stack继承自Vector，实现了一个后进先出的堆栈。Stack提供了5个额外的方法使得Vector得以被当做堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，serach方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
1.4、Set接口
Set是一种不包含重复元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。
很明显，Set的构造函数有一个约束条件，传入的collection参数不能包含重复的元素。
请注意：必须小心操作可变对象。如果一个Set中的可变元素改变了自身的状态导致Object.equals(Object)=true将导致一些问题。
1.4.1 HashSet
HashSet调用对象的hashCode(),获得哈希码，然后再集合中计算存放对象的位置。通过比较哈希码与equals()方法来判别是否重复。所以，重载了equals()方法同时也要重载hashCode()
1.4.2TreeSet
TreeSet继承了SortedSet接口，能够对集合中对象排序。默认排序方式是自然排序，但该方式只能对实现了Comparable接口的对象排序，java中的integer、byte、double、character、string等数值型和字符型对象都实现了该接口。
2、Map接口
Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供了3中集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者key–value映射。
2.1 HashTable类
HashTable继承Map接口，实现了一个key–value映射的哈希表。任何非空的对象都可以作为key或者value。
添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数。HashTable通过initial caoacity和load factor两个参数调整性能。通常缺省的load factor0.75较好地实现了时间和空间的均衡。增大了load factor可以节省空间但相应的查找时间将增大，这回影响像get和put这样的操作。
HashTable是同步的。
2.2HashMap类
HashMap和HashTable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，但是将HashMap视为Collection时，其迭子操作时间开销和HahMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设的过高，或者load factor过低
2.3WeakHashMap类
WeakHashMap是一种改进的HashMap，他对key实行弱引用，如果一个key不再被外部所引用，那么该key可以被GC回收。
结合图说明集合类
从上面的集合框架图可以看到，java集合框架主要包括两种类型的容器，一种是集合(collection),存储一个元素集合，另一种图(Map)，存储键/值对映射。
Collection接口又有三种子类性，List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。
Collection接口图说明
有几个比较常用的方法，比如方法add()添加一个元素到集合中，addAll()将指定集合中的所有元素添加到集合中，contains()方法检测集合中是否包含指定的元素，toArray()方法返回一个表示集合的数组。
Map接口图说明
从上面这张图中我们可以看到接口Map提供了很多查询、更新和获取存储的键值对的方法，更新包括方法clear()、put()、putAll()、remove()等等，查询方法包括containsKey、containsValue等等。
ArrayList深入理解
上源码 哈哈1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
371、方法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输入理解
其实学过数据结构的都知道数组和链表。也知道如果经常有大量的删除和操作最好使用链表，如果不经常删除和操作元素，且在末尾处不能再其他位置插入或删除元素，那么ArrayList最适合。
Set深入理解
Set有三个具体实现的类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet
1、散列集HashSet
可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。
在散列集中，有两个名词需要关注，初始容量和客座率。客座率是确定在增加规则集之前，该规则集的饱满程度，当元素个数超过了容量与客座率的乘积时，容量就会自动翻倍。
看例子:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public class TestHashSet {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("11111");
set.add("22222");
set.add("33333");
set.add("44444");
set.add("22222");
System.out.println(set.size());
for (String e : set) {
System.out.println(e);
}
}
}
从输出结果我们可以看到，规则集里最后有4个元素，而且在输出时元素还是无序的。
2、链式散列集LinkedHashSet
LinkedHashSet是用一个链表实现来扩展HashSet类，它支持对规则集内的元素排序。HashSet中的元素是没有被排序的，而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。
3、树形集TreeSet
能从Set里面提取一个有序序列了
在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序
例子:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class TestSet {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
set.add(1111);
set.add(2222);
set.add(3333);
set.add(4444);
set.add(5555);
System.out.println(set.first()); // 输出第一个元素
System.out.println(set.lower(3333)); //小于3333的最大元素
System.out.println(set.higher(2222)); //大于2222的最大元素
System.out.println(set.floor(3333)); //不大于3333的最大元素
System.out.println(set.ceiling(3333)); //不小于3333的最大元素
System.out.println(set.pollFirst()); //删除第一个元素
System.out.println(set.pollLast()); //删除最后一个元素
System.out.println(set);
}
}
Queue深入理解
队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。
看类图
方法offer表示向队列添加一个元素，poll()与remove()方法都是移除队列头部的元素，两者的区别在于如果队列为空，那么poll()返回的是null，而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素，不删除。
接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，拥有高优先级的先被删除。
例子:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class TestQueue {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.offer("aaaa");
queue.offer("bbbb");
queue.offer("cccc");
queue.offer("dddd");
while (queue.size() > 0) {
System.out.println(queue.remove() + "");
}
}
}
HashMap深入理解
HashMap是基于哈希表的Map接口的非同步实现,，继承自AbstractMap，AbstractMap是部分实现Map接口的抽象类。
ArrayList主要是用数组来存储元素的，LinkedList是用链表来存储的，那么HashMap的实现原理是什么呢？
看图
HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间.
HashMap存储元素的数组1
transient Node<K,V>[] table;
数组的元素类型是Node<K,V>，Node<K,V>继承自Map.Entry<K,V>，表示键值对映射。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//构造函数 ( Hash值键值下一个节点 )
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
接下来我们看下HashMap的put操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //如果没有初始化则初始化table
if ((p = tab[i = (n - 1) & hash]) == null)
//这里 (n-1)&hash 是根据hash值得到这个元素在数组中的位置（即下标）
tab[i] = newNode(hash, key, value, null);
//如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上
else {
Node<K,V> e; K k;
//第一节节点hash值同，且key值与插入key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//属于红黑树处理冲突
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/链表处理冲突
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//新增节点后如果节点个数到达阈值，则将链表转换为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//更新hash值和key值均相同的节点Value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
接下来我们看下HashMap的get操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突
//遍历红黑树，得到节点值
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null &&
key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用hash(int h)方法所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中，(n - 1) & hash用于计算对象应该保存在table数组的哪个索引处。HashMap底层数组的长度总是2的n次方，当数组长度为2的n次幂的时候，(n - 1) & hash 算得的index相同的几率较小，数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
LinkedHashMap深入了解
LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。
TreeMap深入了解
TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。
在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。
总结
- Java集合框架主要包括Collection和Map两种类型。其中Collection又有3种子类型，分别是List(ArrayList,LinkedList)、Set(HashSet,LinkedHashSet,TreeSet)、Queue。Map中存储的主要是键值对映射,有HashMap,LinkedHashMap,TreeMap。
- 规则集Set中存储的是不重复的元素，线性表中存储可以包括重复的元素，Queue队列描述的是先进先出的数据结构，可以用LinkedList来实现队列。
- 效率上，规则集比线性表更高效。
- ArrayList主要是用数组来存储元素，LinkedList主要是用链表来存储元素，HashMap的底层实现主要是借助数组+链表+红黑树来实现。
- Vector、HashTable等集合类效率比较低但都是线程安全的。包java.util.concurrent下包含了大量线程安全的集合类，效率上有较大提升。
- 说了这么多，搭建应该都ok不？其实跑来跑去就在数组，链表，树之间在转，所以数据结构很重要，数据结构就是根据某种结构去设计这些东西，要从效率上去体会，还有就是各有优点。比如ArrayList，LinkedList采用了数组和链表，都知道数组和链表都是有序的，那么我能不能先无序的放，然后再排序呢，当然是可以的，不就有HashSet了吗？然后又有LinkedHashSet，你们可能有疑问，为什么不是ArrayHashSet，那你学了数据结构就知道，数组是连在一起分配内存的，而链表是有内存就行，因为我存的有下一个数据的地址。那么Set本来就是无序放的，你用数组难道重新创建空间吗？所以咯就是LinkedHashSet，是不是明朗了。为什么要有个TreeSet呢？学过二叉树的都知道，二叉树有先序遍历，中序遍历，后序遍历，那么树是不是又强大了一些呢？就是这样，连后面人们想Map的时候也是这样创建的。很牛。