【Java】三大集合容器概述

                  什么是集合

集合和数组的区别

使用集合框架的好处

常用的集合类有哪些？

 List，Set，Map三者的区别？

什么是List?

ArrayList

LinkedList

什么是Set?

HashSet

LinkedHashSet

TreeSet

 什么是Map?

HashMap

HashMap存储元素的过程：

LinkedHashMap

HashTable

TreeMap

---

什么是集合

集合就是一个放数据的容器，准确的说是放数据对象引用的容器集合类存放的都是对象的引用，而不是对象的本身集合类型主要有3种：set(集）、list(列表）和map(映射)。

集合和数组的区别

数组是固定长度的；集合可变长度的。数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

使用集合框架的好处

1.容量自增长；

2.提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量；

3.可以方便地扩展或改写集合，提高代码复用性和可操作性。

4.通过使用JDK自带的集合类，可以降低代码维护和学习新API成本。

常用的集合类有哪些？

Map接口和Collection接口是所有集合框架的父接口：

1.Collection接口的子接口包括：Set接口和List接口

2. Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

3. Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

4. List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

 List，Set，Map三者的区别？

Java容器分为Collection和Map两大类，Collection集合的子接口有Set、List、Queue三种子接口。我们比较常用的是Set、List，Map接口不是collection的子接口。

Collection集合主要有List和Set两大接口List：

一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有ArrayList、LinkedList和Vector。

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set接口常用实现类是HashSet、LinkedHashSet以及TreeSet。

Map:Map是一个键值对集合，存储键、值和之间的映射。Key无序，唯一；value不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap 

---------------------------------------------------------------------------------------------------------------------------------

什么是List?

List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

ArrayList

Arraylist：Arraylist就是存入一个Object动态数组，也是我们常用的集合，它允许任何元素的插入，甚至包括null。每一个ArrayList都有一个初始化的容量（10），该容量代表了数组的大小，随着容器中容量的不断增加，容器的大小也会随着增加。在每次向容器中增加元素时，会进行容量检查，当快溢出时，会进行扩容操作。

特性

•    允许插入的元素重复
•    插入的元素是有序的
•    动态扩容
•    非线程安全，异步
•    基于动态数组的数据结构
•    擅长随机访问(get set)

代码练习：

    @Test
    public void Test() {
        ArrayList list = new ArrayList();                      
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3); 
        list.add(0, 4); //  在指定位置插入元素
         System.out.print("list", list); //  此时list ；4 0 1 2 3
        List newList = list.subList(2, 4); //截取list ，不包含最后一位
         System.out.print("newList", newList); //  此时 newList ： 1 2
        list.addAll(2, newList); //新增list，新的list元素默认排在原来元素的后面 ,此时newList 不能再使用了
        print("list", list); // 此时，list : 4 0 1 2 1 2 3
        System.out.println("list" + list.size());
        list.set(0, 1); //在指定位置替换元素
        print("list", list); // 此时 list : 1 0 1 2 1 2 3
        System.out.println(list.indexOf(1));
        System.out.println(list.lastIndexOf(1));
        System.out.println(list.isEmpty());
 
    }
 
    private void print(String flag, List list) {
        System.out.print(flag + ":");
        list.forEach(System.out::print);
        System.out.println();
    }

LinkedList

LinkedList：LinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（stack），这样看来，linkedList简直就是无敌的，当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（只是一个接口的名字）。关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）更好的性能。

什么是Set?

Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

HashSet

HashSet（无序，唯一）：基于HashMap实现的，底层采用HashMap来保存元素

代码块练习：

public class HashSetTest {
 
  public static void main(String[] args) {
 
   // HashSet常用API
 
   testHashSetAPIs() ;
 
  }
 
  /*
  * HashSet除了iterator()和add()之外的其它常用API
  */
 
  private static void testHashSetAPIs() {
 
   // 新建HashSet
 
   HashSet set = new HashSet();
 
   // 将元素添加到Set中
 
   set.add("a");
 
   set.add("b");
 
   set.add("c");
 
   set.add("d");
 
   set.add("e");
 
   // 打印HashSet的实际大小
 
   System.out.printf("size : %d\n", set.size());
 
   // 判断HashSet是否包含某个值
 
   System.out.printf("HashSet contains a :%s\n", set.contains("a"));
 
   System.out.printf("HashSet contains g :%s\n", set.contains("g"));
 
   // 删除HashSet中的“e”
 
   set.remove("e");
 
   // 将Set转换为数组
 
   String[] arr = (String[])set.toArray(new String[]);
 
   for (String str:arr)
 
    System.out.printf("for each : %s\n", str);
 
   // 新建一个包含b、c、f的HashSet
 
   HashSet otherset = new HashSet();
 
   otherset.add("b");
 
   otherset.add("c");
 
   otherset.add("f");
 
   // 克隆一个removeset，内容和set一模一样
 
   HashSet removeset = (HashSet)set.clone();
 
   // 删除“removeset中，属于otherSet的元素”
 
   removeset.removeAll(otherset);
 
   // 打印removeset
 
   System.out.printf("removeset : %s\n", removeset);
 
   // 克隆一个retainset，内容和set一模一样
 
   HashSet retainset = (HashSet)set.clone();
 
   // 保留“retainset中，属于otherSet的元素”
 
   retainset.retainAll(otherset);
 
   // 打印retainset
 
   System.out.printf("retainset : %s\n", retainset);
 
   // 遍历HashSet
 
   for(Iterator iterator = set.iterator();
 
    iterator.hasNext(); )
 
    System.out.printf("iterator : %s\n", iterator.next());
 
   // 清空HashSet
 
   set.clear();
 
   // 输出HashSet是否为空
 
   System.out.printf("%s\n", set.isEmpty()?"set is empty":"set is not empty");
 
  }
 
 }

LinkedHashSet

LinkedHashSet：LinkedHashSet继承与HashSet，并且其内部是通过LinkedHashMap来实现的。有点类似于我们之前说的LinkedHashMap其内部是基于Hashmap实现一样，不过还是有一点点区别的。

TreeSet

TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树。)

 什么是Map?

Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等 

HashMap

HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间，数组的特点：查询效率高，插入，删除效率低。链表的特点：查询效率低，插入删除效率高。

HashMap存储元素的过程：

 
HashMap map = new HashMap();
map.put("李四","王二");
map.put("张三","牛牛");

第一步：计算出键“李四”的hashcode，该值用来定位要将这个元素存放到数组中的什么位置.

什么是hashcode？

在Object类中有一个方法:

public native int hashCode();

调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象地址和内容有关.

哈希码的特点是:

对于同一个对象如果没有被修改（使用equals比较返回true）那么无论何时它的hashcode值都是相同的

对于两个对象如果他们的equals返回false,那么他们的hashcode值也有可能相等

明白了hashcode我们再来看元素如何通过hashcode定位到要存储在数组的哪里，通过hashcode值和数组长度取模我们可以得到元素存储的下标。

 数组索引为1的地方是空的，这种情况很简单，直接将元素放进去就好了。

2. 已经有元素占据了索引为1的位置，这种情况下我们需要判断一下该位置的元素和当前元素是否相等，使用equals来比较。

如果使用默认的规则是比较两个对象的地址。也就是两者需要是同一个对象才相等，当然我们也可以重写equals方法来实现我们自己的比较规则最常见的是通过比较属性值来判断是否相等。

如果两者相等则直接覆盖，如果不等则在原元素下面使用链表的结构存储该元素

LinkedHashMap

LinkedHashMap：LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

HashTable

HashTable：数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap

TreeMap：红黑树（自平衡的排序二叉树）