一、Java中的容器

        容器主要有collection和map两种，collection又可分为list、set、queue三种类型，其中set为无序无重复的，而list是有序可重复的；map中存放的则是键值对，每个key值对应一个value，value可以相等， 但key值是唯一的。

1.list

  1.1 ArrayList（底层实现是数组）

              动态数组实现，容量总是大于等于元素列表的大小。当超过ArrayList的容量时，它会进行扩容。

                  数组的默认大小为10，扩容之后的大小是旧容量的1.5倍。（注意，扩容并不是在原始的数组基础上添加数据，而是将旧数组中的数据拷贝到一个新创建的数组中）

                  

                  

        1.2 LinkedList（底层实现是链表）

              以双向链表来实现，可以方便的进行插入、删除。但查找起来必须从头进行索引，原则上是不如ArrayList方便。

         1.3 Vector

              底层实现也为数组，相较上边两个，vector是线程安全的，但效率低；array与link线程不安全，但是效率高。

     2、Set

       2.1 Hashset 

                基于哈希表实现，支持快速查找，但不支持有序性的操作。

       2.2 Treeset

                基于红黑树实现，支持有序性操作，查找效率不如Hashset，Hashset的查找时间负责度为O(1),TreeSet则为O(logN）。

     3、Queue

                LinkedList实现双向队列；PriorityQueue实现优先队列。

      Map

               分为TreeMap、HashMap、HashTable (是线程安全的，同一时刻多个线程可以同时写入HashTable并且不会导致数据不一致)

              map的底层实现：数组加链表

             

             

                 链表的头插法，就是新的键值对插在链表的头部，而不是在链表的尾部