Java基础—集合框架总结

Collection类

类的相关方法 14个接口

LIST集合

LinkedList类

　　LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比 ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比 ArrayList 差。LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）.

        LinkedList 是基于链表结构实现，所以在类中包含了 first 和 last 两个指针(Node)。Node 中包含了上一个节点和下一个节点的引用，这样就构成了双向的链表。每个 Node 只能知道自己的前一个节点和后一个节点，但对于链表来说，这已经足够了。

1.7JDK中结构 1.6JDK中结构

增加方法：

        该方法是在链表的 end 添加元素，其调用了自己的方法 linkLast(E e)。    该方法首先将 last 的 Node 引用指向了一个新的 Node(l)，然后根据l新建了一个 newNode，其中的元素就为要添加的 e；而后，我们让 last 指向了 newNode。接下来是自身进行维护该链表。其余方法基本都是操作链表进行修改。

ArrayList类

         对于 ArrayList 而言，它实现 List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。public ArrayList()可以构造一个默认初始容量为10的空列表；其容量也自动增长。自动增长会带来数据向新数组的重新拷贝。每次数组容量的增长大约是其原容量的 1.5 倍。也采用了快速失败机制。

SET集合

hashSet类

       HashSet 而言，它是基于 HashMap 实现的，底层采用 HashMap 来保存元素,默认情况下采用的是 initial capacity为16，load factor 为 0.75。对于HashSet中保存的对象，主要要正确重写equals方法和hashCode方法，以保证放入Set对象的唯一性. 其他的看hashmap完全就够了。保存的数据进行hash，当做了key    

TreeSet类

           TreeSet中存放的元素是有序的（不是插入时的顺序，是有按关键字大小排序的），且元素不能重复。 而如何实现有序存储，就需要有一个比较器，其实说起来，TreeSet更受关注的是不重复且有序，这个有序就需要有一个compare的过程，因此会需要参数实现Comparable接口。TreeSet集成Treemap，Treemap底层是红黑树。TreeSet存的数据必须实现Comparable```接口，并重写接口中的compareTo方法，比较大小，采用二叉树算法存储，有序，读取慢，每次需要遍历。    

LinkedHashSet类

           LinkedHashSet 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序 。它继承与 HashSet、又基于 LinkedHashMap 来实现的。LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同。LinkedHashMap调用父类构造方法初始化时，还顺便设置了变量accessOrder = false，看上面得源码可以知道，这是给了迭代器一个参数，false代表迭代时使用插入得顺序 .

Map集合

hashMap类

      hashMap，开始是一个数组，长度16， 扩展因子是0.75. 例如如果到了12的时候，就会翻倍增长。 hashMap先根据key值进行hash,找到数组的下标， 然后根据 key，value 组成一个entrry进行hashCode,equals的判断，进行存储到一个线性链表中。这样有效避免hash冲突。

hashMap在并发执行put时，可能多线程导致HashMap的entry链表变成环形结构，这样永远循环。导致CPU 100%打满。

TreeMap类

        treeMap是红黑树算法的实现， treeset底层也是由Treemap实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。一样是红黑树，entry,root,size比较重要。

LinkedHashMap类

       LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。有序， hashMap无序。key,value都允许为空。

LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定义了数组中保存的元素 Entry，该 Entry 除了保存当前对象的引用外，还保存了其上一个元素 before 和下一个元素 after 的引用，从而在哈希表的基础上又构成了双向链接列表。如下图所示。

LinkedHashMap中entry结构 结构图

循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口。

hashTable类

使用Synchronized保证线程安全， 在put的时候，不能使用get获取。底层原理【实际是一个散列表】