本文共 6548 字，大约阅读时间需要 21 分钟。
引言：在Java语言中，Java语言的设计者对常用的数据结构和算法做了一些规范（接口）和实现（具体实现接口的类）。所有抽象出来的数据结构和操作（算法）统称为Java集合框架（JavaCollectionFramework）。
Java集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection接口又有3种子类型，List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。
结构:集合框架的顶层接口，定义了操作对象集合的共同方法,其中几个方法可能会引发一个 UnsupportedOperationException 异常，这些发生在当类集合不能被修改时。当一个对象与另一个对象不兼容，例如，当企图增加一个不兼容的对象到一个集合中时，将产生一个ClassCastException异常。
Collection的一些通用方法
增：public boolean add(E e);
删：public void remove（E e）；
改：无
查：无
其他方法：
public void clear（）；//清空集合中的元素
public int size（）；获取集合的长度（元素的个数）；
public boolean contains（E e）；//判断当前集合中是否包含指定对象
public boolean isEmpty（）；//判断集合是否为元素
public Object[] toArray（）;//将集合元素转换为数组
containsAll(Collection c)：//是否包含集合c中的所有元素
iterator()：//返回Iterator对象，用于遍历集合中的元素
remove(Object o)：//移除元素
removeAll(Collection c)：//相当于减集合
其中，有几个比较常用的方法，比如方法add()添加一个元素到集合中，addAll()将指定集合中的所有元素添加到集合中，contains()方法检测集合中是否包含指定的元素，toArray()方法返回一个表示集合的数组。Collection接口有三个子接口，list,set,queue.下面详细介绍。
1.1.List
1.1.1 ArrayList ：通过构造方法得知。在创建ArrayList类的过程中。实际上是创建了一个数组。这个数据根据构造方法进行判断。
（1）如果传入的是长度。则根据长度构造空数组。如果传入的是集合。则将集合元素拷贝进创建的数组结构中。 （2）这里有个需要注意的是elementData变量，它是用transient 进行了修饰。我们知道这个关键字的作用是不被序列化。 （3）为什么这个变量特意用这个修饰呢。由于在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去,所以需要手动的序列化数组对象,所以使用了transient来禁止自动序列化这个数组.添加元素add(E e)：
在ArrayList进行添加元素的时候。先进行判断集合长度是否为0，如果为0则传入默认值10进行扩容。如果长度不为0.则进行长度判断。如果数组未饱和则至今将元素放入。如果长度超出则进行扩容。查看grow（）方法我们可以看出通过 Arrays.copyOf（）方法将创建一个原来长度1.5倍的新数组，并将元素复制进去。
同时常用的方法add(int index, E element)：
也是先进行扩容。然后再将插入位置往后的所有元素复制到扩容后的数组里面。索引之后的所有元素都发生了位置改变， // 所以如果是频繁的进行索引插入而且集合长度非常大的话。会极度降低效率。
1.1.2LinkedList
LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用。
将每个新的元素都加入到原来锁链的下一个元素中也就是尾部。并将集合的last变量赋值为最新的元素Node。 如果是按位置进行插入
1.1.3 Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步。
1.2 set
1.2.1 HashSet是一个没有重复元素的集合，它其实是由HashMap实现的，HashMap保存的是建值对，然而我们只能向HashSet中添加Key，原因在于HashSet的Value其实都是同一个对象，这是HashSet添加元素的方法，可以看到辅助实现HashSet的map中的value其实都是Object类的同一个对象。下面我们看下它的源码
class HashSet implements Set{ private static final Object PRESENT = new Object(); private transient HashMap map; public HashSet() { map = new HashMap<>(); } public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node [] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode )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; } } 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; } public boolean add(E e) { return map.put(e, PRESENT)==null; }} 1.3 queue
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 最常用的Queue实现是LinkedList，ArrayBlockingQueue和PriorityQueue。
1.3.1 add 与 offer 区别
add 和 offer 方法都是向队列中添加一个元素。当一个大小受限制的队列满时，使用 add 方法将会抛出一个 unchecked 异常；使用 offer 方法会返回 false。
1.3.2 remove 与 poll 区别
remove() 和 poll() 方法都是删除并返回队列头部的第一个元素。确切地说，从队列中删除哪个元素是队列排序策略的一个功能，该策略因实现而异。remove（）和 poll（）方法的不同之处仅在于队列为空时的行为：remove（）方法抛出异常，而poll（）方法返回null。
1.3.3 有界队列（Bounded Queues）和无界队列（Unbounded Queues）
有界队列是有容量限制的队列，这意味着我们需要在创建时设置队列的最大大小。 例如：ArrayBlockingQueue。界队列是不受容量限制的队列，这意味着我们不需要设置队列的大小。 例如：LinkedList
1.3.4 阻塞队列（BlockingQueue） 和 非阻塞队列（Non-Blocking Queues）
我们可以将它们大致分为以下两种类型：阻塞队列、非阻塞队列阻塞队列（BlockingQueue）
实现 BlockingQueue 接口的所有队列都是 阻塞队列，其余的都是 非阻塞队列。BlockingQueues阻塞直到它完成它的工作或超时，但Non-BlockingQueues不会。
BlockingQueue 操作
除了Queue的两种操作形式之外，BlockingQueue 还支持另外两种形式，如下所示：
| Operation | Throws exception | Special value | Blocks | Times out |
| Insert | add(e) | offer(e) | put(e) | offer(e, time, unit) |
| Remove | remove() | poll() | take() | poll(time, unit) |
| Examine | element() | peek() | N/A | N/A |
Map中的常用方法：
void clear():删除该Map对象中所有键值对；
boolean containsKey(Object key):查询Map中是否包含指定的key值； boolean containsValue(Object value):查询Map中是否包含一个或多个value; Set entrySet():返回map中包含的键值对所组成的Set集合，每个集合都是Map.Entry对象。 Object get()：返回指定key对应的value，如果不包含key则返回null； boolean isEmpty():查询该Map是否为空； Set keySet():返回Map中所有key组成的集合； Collection values():返回该Map里所有value组成的Collection。 Object put(Object key,Object value):添加一个键值对，如果集合中的key重复，则覆盖原来的键值对； void putAll(Map m):将Map中的键值对复制到本Map中； Object remove(Object key):删除指定的key对应的键值对，并返回被删除键值对的value，如果不存在，则返回null； boolean remove(Object key,Object value):删除指定键值对，删除成功返回true； int size():返回该Map里的键值对个数；2.1hashmap
hashmap 在java1.8中是一个数组+链表+红黑树的数据结构。
它的存储过程：如果数组没有初始化，先进行初始化操作。在hashmap中会根据hash值&(数组长度-1)来计算元素在数组中的位置，如果位置中没有值，会将数据放入数组对应的位置中，如果数组中这个位置已经有值了，那么会比较hash值和key值。如果hash值相同，key值相同，会覆盖原值。如果hash值相同，key不同，会根据尾插法，将值插入链表的尾部。如果数组长度大于64，并且链表长度大于8，会将链表转换成红黑树结构进行存储。如果进行删除操作。在链表长度小于6时，才会将红黑树结构转换成链表进行存储。
2.2 LinkedHashMap ：使用双向链表来维护键值对的次序，迭代顺序和插入顺序保持一致。
2.3 TreeMap：红黑树数据结构，每个键值对作为红黑树的一个节点。存储键值对时根据key对节点进行排序。可以保证所有键值对处于有序状态。
2.4 ConcurrentHashMap : 线程安全的hashmap，在java1.8之后，通过大量使用cas操作和synchronized配合使用，对数据进行增删改操作。
参考文章：
转载地址：http://gaeji.baihongyu.com/