java中集合的学习与总结

集合与数组：

数组：长度固定，可以存储基本类型。

集合：长度可变，不能存储基本类型（只能存储对象）。

 

集合类框架图：

 

Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口，就是Set和List。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。

Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。

Iterator，所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：

1. hasNext()是否还有下一个元素。
2.next()返回下一个元素。
3.remove()删除当前元素。

两个主要的集合类接口：

List:实现了collection接口的接口；元素可以重复，元素有序，使用索引可以找到元素。

Set:实现了collection接口的接口；元素不可以重复，元素无序，只能通过遍历查找元素。

几个主要的List实现类：

ArrayList:内部使用数组来存储元素，每次扩容，会增加0.5倍的长度。（最适合查询）

LinkedList：内部使用链表来存储元素。（最适合频繁的增删）

Vector：线程安全。内部使用数组来存储元素，每次扩容，会增长1倍的长度。

几个主要的Set实现类：

HashSet：内部使用HashMap的key来存储数据，value都是相同的默认值。

LinkedHashSet：内部使用LinkedHashMap来存储数据。继承自HashSet。

TreeSet:内部使用TreeMap来存储数据。没有继承HashSet，有很多自己独有的导航方法。

几个主要的Map实现类：

HashMap：内部使用HashTable来存储数据；通过HashCode来确定key在哈希数组中的位置，然后再用equals方法确定该位置的单向链表中又没有该key，从而保证key唯一；因此，key可以为null，但只能有一个null。

             HashTable：

  数组的特点是：寻址容易，插入和删除困难；

  而链表的特点是：寻址困难，插入和删除容易。

  那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

 

 

LinkedhashMap:内部使用带双向链表的HshTable来存储数据，就是说在原来基础的HashTable上，每个元素又多了after，befor两个成员来维护双向链表的结构，通过这个双向链表结构来维护元素插入的顺序。

带双向链表的HashTable：

  本质上，HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表双向链表的HashMap。在LinkedHashMapMap中，所有put进来的Entry都保存在如下面第一个图所示的哈希表中，但由于它又额外定义了一个以head为头结点的双向链表(如下面第二个图所示)，因此对于每次put进来Entry，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。

 

 

以上两者结合起来，就是linkedHashMap了。

 

每一个节点的示意图：

 

TreeHashMap：内部使用红黑树来存储数据；存储的对象，必须实现compareTo方法，或者，创建TreeHashMap对象时，实现一个Comparable接口作为参数传入构造方法中。

红黑树插入删除比较复杂，下图简单展示一下查找方法。