前言
在PHP中，集合是很简单的，就一个Array，既可以做数组，又可以做map，对比JAVA常用的List，Map，Set来说只有Set是在PHP中需要封装的,本文就Java中常用的几个集合类来做一个总结。
常用的集合类介绍
List
List的特点是有序，元素可重复
ArrayList
ArrayList的实现其实是对一个数组的封装，实现了一个动态的数组，它的构造器有三种：
ArrayList arrayList = new ArrayList();
ArrayList arrayList1 = new ArrayList(5000);
ArrayList arrayList2 = new ArrayList(linkedList);
如果不指定初始大小，ArrayList默认大小是10，如果添加的元素超过10，则ArrayList会扩容。扩容的源代码如下：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
可以看出，扩容最少是目前容量的1.5倍，如果我们需要一个5000的ArrayList，初始化的时候不指定大小，使用默认容量10，那么一个一个地往里面添加元素，它将会扩容N次：
10 * 1.5 ^ N = 5000
算出来N至少为16才能完成任务，也就是执行了16次copy动作，这是非常耗时的，所以建议是在知道大小时多申请一些容量，这样就不会频繁的扩容。
从ArrayList的实现也能看出ArrayList适合查询，不适合频繁执行添加删除元素的操作。
Vector
Vector与ArrayList的实现方式基本一致，只是它很多方法用了synchronized来修饰，也就是线程安全的，一个时间只有一个线程可以修改，其他细节与ArrayList类似。
Stack
Stack是基于Vector实现的一个集合，它的特点是先入后出，与Vector一样也是线程安全的。
LinkedList
LinkedList的实现可以看做是一个链表，节点之间是通过指针来连接的，所以LinkedList与ArrayList互补，适合频繁地删除添加元素，而不适合查找。
LinkedList的初始化如下：
LinkedList linkedList = new LinkedList();
LinkedList linkedList1 = new LinkedList(arrayList);
只有两种初始化方式，不需要指定大小。
Map
Map的特点是存储键值对
HashMap
HashMap采用的是将“键”的HashCode对应的存储区域存储上键和值，本质上是一个数组，只不过可以通过“键”计算出应该存在数组的哪个位置，它的key，value可以为null，无序。
看一下它的几个构造方法：
public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap();
public HashMap(Map<? extends K, ? extends V> m);
看出来HashMap是有大小的，也是有一个扩容的过程。网上看到一个概括put的过程直接引用过来：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
HashTable
与HashMap类似，但是是线程安全的，键和值都不能是null，他们使用的hashCode也是不一样的，HashTable直接使用HashCode，而HahMap会在HashCode上再做一次Hash，且他们的扩容方式也不尽相同，HashTable中hash数组默认大小是11，增加的方式是old*2+1，HashMap中hash数组的默认大小是16，而且一定是2的指数
LinkedHashMap
LinkedHashMap与HashMap基本相同，只是在定义节点时增加了前后指针，这也就意味着遍历时能保证顺序，其他与HashMap无异。
TreeMap
TreeMap实际上是一个红黑树的实现，与HashMap使用HashCode实现不一样，它的查找效率没有HashMap那么高效，但是也达到了O(logn)，它的元素是有序的且不能为null。
Set
Set的特点是不能存储相同的元素
HashSet
HashSet的实现是对HashMap的封装，只不过是将需要add进set的元素当成是HashMap的key，这样实现了set的不重复。
LinkedHashSet
底层采用了LinkedHashMap来实现，也是在HashSet的基础上增加了有序，读LinkedHashSet源代码没有发现和LinkedHashMap有关？仔细看，所有的LikedHashSet都是调用了HashSet的这个构造方法来初始化的：
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
藏的够深，原来HaSet中有一个专门为LinkedHashMap提供的构造方法。
TreeSet
TreeSet是基于TreeMap实现的，也是一个红黑树，也是有序的且不依赖Hash实现的一种Set,同理也是将要加入到set中的元素当做键插入到TreeMap中去。
总结
- Java的集合类丰富多彩，在选择和使用时需谨慎思考
- 编写多线程程序需要注意线程安全问题，Vector、Stck和HashTable是线程安全的，其他集合都是线上不安全的。
- Java集合涵盖了很多数据结构的知识，如红黑树就是可以展开的一个知识点
- 另外还有其他不常用的如Queue等集合在这里没有做介绍
网友评论