Java常用集合框架

 

一、 集合：集合是一个用于管理其他多个对象的对象

1、Collection  接口：集合中每一个元素为一个对象，这个接口将这些对象组织在一起，形成一维结构。 

2、List 接口：描述了线性表结构，就是集合元素有先后次序，元素有序号，元素允许重复。

3、Set 接口：是数学中集合的概念：其元素无序，且不可重复。（正好与List 对应） 

4、SortedSet  接口 ：会按照数字将元素排列，为“可排序集合”。 

5、Map  接口 ：接口中每一个元素不是一个对象，而是一个键对象和值对象组成的键值对（Key-Value）。 经常用于数据的快速查找的算法。

6、SortedMap 接口：如果一个Map 可以根据key 值排序，则称其为SortedMap。 

 注意：在“集合框架”中，Map 和Collection 没有任何亲 缘关系。  

          •Map 的典型应用是访问按关键字存储的值。它支持一系列集合操作的全部，但操作的是键-值对，而不是单个独立的元素。因此Map 需要支持get() 和put() 的基本操作，而Set 不需要。  

          •返回Map 对象的Set 视图的方法： 

              Set set ＝ aMap.keySet() 
                                                                      《常用集合列表》

                             List                    Set           SortedSet                  Map                             SortedMap

  存放元素            Object               Object        Object     Object(key)—Object(value)  Object(key)—Object(value)

  存放顺序             有序                 无序            无序                    Key 无序                            无序，有排序

元素可否重复          可                   不可            不可                 Key 不可，value 可              Key 不可，value 可

  遍历方式             迭代                  迭代            迭代                 对Key 迭代                          对 Key 迭代

  排序方式       Collections.sort()   SortedSet     已排序              SortedMap                       已对键值排序

 各自实现类 ArrayList LinkedList   HashSet     TreeSet             HashMap                              TreeMap 
  注：以上有序的意思是指输出的顺序与输入元素的顺序一致，HashSet、HashMap 通过hashCode()，equals()来判断重复元素

   在java  中指定排序规则的方式只有两种：1、实现java.util 包下的Comparator 接口  2、实现java.lang 包下的 Comparable 接口

四、 ArrayList 和LinkedList 集合

1、ArrayList 底层是object变长数组，变长增加：50%。所以ArrayList 具有数组的查询速度快的优点以及增删速度慢（增删时涉及移位）的缺点。 线程不安全。

     Vector 底层实现也是数组，变长增加：100%。但他是一个线程安全的重量级组件，故比ArrayList稍慢。 

2、而在LinkedList 的底层是一种双向循环链表。在此链表上每一个数据节点都由三部分组成：前指针（指向前面的节点的位置）， 数据，后指针（指向后面的节点的位置）。最后一个节点的后指针指向第一个节点的前指针，形成一个循环。 线程不安全。

3、双向循环链表的查询效率低但是增删效率高。所以LinkedList 有查询效率低但增删效率高的特点。 

4、ArrayList 和LinkedList 在用法上没有区别，但是在功能上还是有区别的。 

LinkedList    经常用在增删操作较多而查询操作很少的情况下：队列和堆栈。 

队列：先进先出的数据结构。 

堆栈：后进先出的数据结构。 

       （堆栈就是一种只有增删没有查询的数据结构） 

注意：使用堆栈的时候一定不能提供方法让不是最后一个元素的元素获得出栈的机会。 

LinkedList    提供以下方法：（ArrayList 无此类方法） 

addFirst();

removeFirst();

addLast();

removeLast();

在堆栈中，push 为入栈操作，pop 为出栈操作。Push 用addFirst()；pop 用removeFirst()，实现后进先出。 用isEmpty()--其父类的方法，来判断栈是否为空。 

在队列中，put 为入队列操作，get 为出队列操作。 Put  用addFirst()，get 用removeLast()实现队列。 

List  接口的实现类（Vector ）（与ArrayList  相似，区别是Vector 是重量级的组件，使用使消耗的资源比较多。） 

结论：在考虑并发的情况下用Vector （保证线程的安全）。 在不考虑并发的情况下用ArrayList  （不能保证线程的安全）。 

5、面试经验（知识点）： 

java.util.stack  （stack  即为堆栈）的父类为Vector 。可是stack  的父类是最不应该为Vector  的。因为Vector的底层是数组，且Vector 有get  方法（意味着它可能访问到并不属于最后一个位置元素的其他元素，很不安全）。 

对于堆栈和队列只能用push 类和get  类。 

Stack  类以后不要轻易使用。 

 ！！！实现堆栈一定要用LinkedList。 

  （在JAVA1.5      中，collection    有queue    来实现队列。） 

二、 HashSet 集合

1.、HashSet 是无序的，允许存null，没有下标这个概念。HashSet 集合中元素不可重复（元素的内容不可重复）；

2、HashSet  底层采用散列表实现。

3、HashSet 如何保证元素不重复？--Hash 算法和equals 方法。

    当向数组中利用add(Object o)添加对象的时候，系统先找对象的hashCode： 

    int hc=o.hashCode();    //返回的hashCode 为整数值。 

    Int I=hc%n;  //（n为数组的长度），取得余数后，利用余数向数组中相应的位置添加数据，以n 为6 为例， 

    如果I=0 则放在数组a[0]位置，如果I=1,则放在数组a[1]位置。如果equals()返回的值为true，则说明数据重复。如果equals()返回的值为false，则再找其他的位置进行比较。这样的机制就导致两个相同的对象有可能重复地添加到数组中，因为他们的hashCode不同。如果我们能够使两个相同的对象具有相同hashcode，才能在equals()返回为真。  

结论：如将自定义类用hashSet 来添加对象，一定要覆盖hashcode()和equals()，覆盖的原则是保证当两个对象hashcode返回相同的整数，而且equals()返回值为True。 如果偷懒，没有设定equals()，就会造成返回hashCode  虽然结果相同，但在程序执行的过程中会多次地调用equals()，从而影响程序执行的效率。 

我们要保证相同对象的返回的hashCode 一定相同，也要保证不相同的对象的hashCode尽可能不同 （因为数组的边界性，hashCode  还是可能相同的）。例子： 

public int hashCode(){

return name.hashcode()+age;

}

三、 TreeSet 集合

   1、  TreeSet 是 SortedSet 的实现类TreeSet 通过实现 Comparable 接口来实现元素不重复。底层采用二叉排序树实现。

    2、 TreeSet  由于每次插入元素时都会进行一次排序，因此效率不高。

    3、 从集合中以有序的方式抽取元素时，可用TreeSet，添加到TreeSet  的元素必须是可排序的。“集合框架”添加对Comparable 元素的支持。一般说来，先把元素添加到HashSet，再把集合转换为TreeSet 来进行有序遍历会更快。

 四、 HashMap 集合

        1．  HashMap 就是用hash 算法来实现的Map

        2．  在实际开发中一般不会用自定义的类型作为Map 的 Key。做Key 的无非是八种封装类。

        3．  HashMap 的三组操作：

            【1】改变操作允许您从映射中添加和除去键-值对。键和值都可以为null。但是，您不能把Map 作为一个键或值添加给自身。 

                 –Object put(Object key, Object value)  

                 –Object remove(Object key)  

                  –void clear()  

         【2】查询操作允许您检查映射内容： 

                  -Object get(Object key) 

                  –intsize() 

                  –boolean isEmpty() 

         【3】最后一组方法允许您把键或值的组作为集合来处理。 

                  –public Set KeySet();  

                  –public Collection values()  

    4、  HashMap 和HashTable 的区别等同于ArrayList 和Vector的区别。只不过HashTable 中的Key 和Value 不能为空，而HashMap 可以。

    5、  HashMap 底层也是用数组，HashSet 底层实际上也是HashMap，HashSet 类中有HashMap 属性，HashSet 实际上为(key.null)类型的HashMap。有key 值而没有value 值。

五、HashMap 类和TreeMap 类 

•集合框架提供两种常规Map 实现：HashMap和TreeMap。 

•在Map 中插入、删除和定位元素，HashMap 是最好选择。 

•如果要按顺序遍历键，那么TreeMap 会更好。 

•根据集合大小，先把元素添加到HashMap，再把这种映射转换成一个用于有序键遍历的TreeMap 可能更快。 

•使用HashMap 要求添加的键类明确定义了hashCode() 实现。 

•有了TreeMap 实现，添加到映射的元素一定是可排序的 

•HashMap 和TreeMap 都实现 Cloneable 接口。