Java创建的数据结构有Collection和Map。Collection分为List、Set、Queue。
目录
List：有序集合，顺序插入元素，允许相同的值
Set：无序性集合，不允许相同的值（有序和无序不是指排序，而是遍历的时候，先插入的先遍历就是有序）
Queue：队列：是一个先入先出（FIFO）的数据结构
List：有序集合，顺序插入元素，允许相同的值
ArrayList:底层由数组实现，可以认为ArrayList是一个可改变大小的数组。随着元素增加会自动扩容，扩容策略是每次增大50%。线程不安全。如果需要线程安全，可以使用List list=Collections.synchronizedList(new ArrayList());允许插入空值null
LinkList：底层由双向链表实现，线程不安全。与ArrayList的区别就是数组和链表的区别。数组查询快，可以通过下标直接访问，而删除、插入慢，因为需要移动数据。链表相反，删除插入可以直接操作链表的指针（每一个元素含有上一个和下一个元素的引用）。允许插入空值null
Vector：底层有数组实现，线程安全，每个操作都会加锁。扩容策略，每次增加一倍。允许插入空值null。
Stack：栈，先进后出。继承于Vector，底层有数组实现。线程安全。
Set：无序性集合，不允许相同的值（有序和无序不是指排序，而是遍历的时候，先插入的先遍历就是有序）
HashSet：底层通过HashMap实现的。所有操作都是通过内部的HashMap操作的（判断值相同的原理见下面HashMap）。扩容策略，对内部维护的HashMap的加载因子是使用默认的0.75，且默认的Entry数组大小根据不同的情况确定，无参则是16，有参则是在集合数量的2倍，同16之间取最大值。允许插入空值null。线程不安全。
TreeSet：底层是通过TreeMap实现的，基本与HashSet一样。不同的是TreeSet有排序功能，分为自然排序和自定义排序两类，默认是自然排序；在程序中，我们可以按照任意顺序将元素插入到集合中，等到遍历时TreeSet会按照一定顺序输出--倒序或者升序。允许插入空值null。线程不安全。
LinkHashSet：底层是通过LinkHashMap实现的。与其他Set不同，LinkHashSet有序。同样它也允许插入空值null。线程不安全。
Queue：队列：是一个先入先出（FIFO）的数据结构
PriorityQueue：优先级队列，底层有数组实现的小顶堆实现。PriorityQueue的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。优先队列中不能存放空元素。压入元素后如果数组的大小不够会进行扩充，大小默认初始值为11的数组（也可以赋初始值）。
offer操作：将元素插入最后一个位置，然后进行siftUp操作，该方法从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
poll操作：将第一个元素弹出，然后进行siftDown操作，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
PriorityQueue关键源码解析
removeAt操作
// 移除指定位置的数据，这个位置不是优先级排列，而是数组下标private E removeAt(int i) {// assert i >= 0 && i < size;modCount++;int s = --size;// 如果是最后一个元素直接移除if (s == i)queue[i] = null;else {// 将最后一个元素放在移除的位置，将最后的位置置为nullE moved = (E) queue[s];queue[s] = null;// 进行向下调整结构siftDown(i, moved);// 调整完成之后，会判断queue[i] == moved，如果为true表示新增元素之后并没有调整结构（满足堆结构）// 那么就会尝试向上调整结构。（如果向下调整过结构自然是不需要再向上调整了），// 如果queue[i] != moved值为true表示向上调整过结构，那么将会返回moved。if (queue[i] == moved) {siftUp(i, moved);// 代表进行了向上调整if (queue[i] != moved)// 之所以要返回被移动的元素是因为迭代器的需要// 如果迭代器在迭代的过程中删除了元素。则需要讨论一些特殊的情况。// 最末未元素进行了下滤操作，不需要考虑因为迭代器是按照顺序进行的。 下滤的元素必然会被之后的迭代器迭代到// 最末未元素进行了上移。这需要用另一个堆来保存它。因为上滤的元素不会被之后的迭代器迭代到。// 所以这里返回被移动的元素，供迭代器使用。迭代器会把上移过的元素放到一个单独队列里。return moved;}}return null;}siftDown操作
// siftDown操作private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;int half = size >>> 1; // loop while a non-leaf// k代表下移元素的下标。他的左孩子下标为 2*i+1 右孩子为 2*i+2 如果k>=half 说明他没有子节点了while (k < half) {int child = (k << 1) + 1; // assume left child is leastObject c = queue[child];int right = child + 1;if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)c = queue[child = right];// c是左右孩子中的最小值 如果下移元素小于左右孩子 下移结束if (key.compareTo((E) c) <= 0)break;// 和最小的孩子节点互换，继续下移queue[k] = c;k = child;}queue[k] = key;}siftUp操作
// 上移操作private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;// 不是顶点while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];// 如果大于父节点 上移结束if (key.compareTo((E) e) >= 0)break;// 和父节点交换位置 继续上移queue[k] = e;k = parent;}queue[k] = key;}ConcurrentLinkedQueue ：一个基于链接节点的无界线程安全队列。采用cas操作，线程安全。底层用链表实现的。
offer操作：先寻找队列的尾节点，然后用cas操作，将尾节点的next指针指向插入的元素。
源码解析
// offer操作public boolean offer(E e) {checkNotNull(e);final ConcurrentLinkedQueue.Node<E> newNode = new ConcurrentLinkedQueue.Node<E>(e);for (ConcurrentLinkedQueue.Node<E> t = tail, p = t;;) {ConcurrentLinkedQueue.Node<E> q = p.next;// 寻找最后一个节点不是根据tail指针，而是根据p.next == null判断 tail指针会延迟恒心if (q == null) {// p is last node// cas操作 将最后一个节点next指针指向新节点if (p.casNext(null, newNode)) {// Successful CAS is the linearization point// for e to become an element of this queue,// and for newNode to become "live".// 不止走一次循环，更新tail指针 可能失败，失败时没关系的if (p != t) // hop two nodes at a timecasTail(t, newNode); // Failure is OK.return true;}// Lost CAS race to another thread; re-read next}// 当tail指针延迟更新，，可能指向原来的head节点 poll操作的缘故// 此时head节点next指针指向自己 让p节点恢复到新的head指针else if (p == q)// We have fallen off list. If tail is unchanged, it// will also be off-list, in which case we need to// jump to head, from which all live nodes are always// reachable. Else the new tail is a better bet.p = (t != (t = tail)) ? t : head;else// Check for tail updates after two hops.// 重新寻找tail指针 寻找为节点 继续操作p = (p != t && t != (t = tail)) ? t : q;}}poll操作：找到头节点，判断头节点中元素是否为null，不为null直接返回，未null更新头节点
源码解析
// poll操作public E poll() {restartFromHead:for (; ; ) {for (ConcurrentLinkedQueue.Node<E> h = head, p = h, q; ; ) {E item = p.item;// 如果head节点中数据不为null cas操作将里面的数据置为null 返回数据if (item != null && p.casItem(item, null)) {// 说明head节点中数据为null for循环不止走一次if (p != h) // hop two nodes at a time// 将原来head节点的next指针指向自己，将head指针指向有数据的节点。updateHead(h, ((q = p.next) != null) ? q : p);return item;}// 代表队列空了else if ((q = p.next) == null) {updateHead(h, p);return null;}// 多线程时 当自己进入for循环(此时head指针还没有变)// 其他线程走到updateHead(h, ((q = p.next) != null) ? q : p);head指针已经移走，原head节点next指针指向自己// 此时重新获取head节点 重新开始操作else if (p == q)continue restartFromHead;else// head节点的元素为null p指向下一个节点，继续操作p = q;}}}