大家好，又见面了，我是你们的朋友全栈君。

通俗的说，集合就是一个存放数据的容器，准确的说，就是放数据对象引用的容器

• 数组和集合都是容器，有何不同?
  数组长度固定，集合长度可变
  数组只能存放相同类型的数据，集合可以存放不同类型的数据
  数组可存放简单数据类型和类类型的数据，集合只能存放类类型数据

JAVA集合框架：java中用来表示集合，和操作集合的所有类库的统称
JAVA中的集合从大方向分有两种：Collection 集合，Map 集合，它们都继承自Object

泛型

Java中因为类型参数会被替换为object，所以泛型中不能用基本数据类型Pair minmax = new Pair(1,100)不合法; 泛型的本质是参数化类型，所操作的数据类型被指定为一个参数
泛型方法：方法在调用时可以接收不同类型的参数。根据传递给泛型方法的参数类型，编译器适当地处理每一个方法调用
好处：更好的安全性、更好的可读性

定义泛型方法的规则：

● 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前
● 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用指定一个泛型类型名称的标识符
● 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符
● 泛型方法体的声明和其他方法一样。注意类型参数只能代表引用型类型

public class Demo3{ 
   
  // 泛型方法 printArray 
  public static < E > void printArray( E[] inputArray ){ 
   
     // 输出数组元素 
        for ( E element : inputArray ){ 
           
           System.out.printf( "%s ", element );
        }
        System.out.println();
   }

 public static void main( String args[] ){ 
   
       // 创建不同类型数组： Integer, Double 和 Character
       Integer[] intArray = { 
    1, 2, 3, 4, 5 };
       Double[] doubleArray = { 
    1.1, 2.2, 3.3, 4.4 };
       Character[] charArray = { 
    'H', 'E', 'L', 'L', 'O' };
 System.out.println( "整型数组元素为:" );
       printArray( intArray  ); // 传递一个整型数组
 System.out.println( "\n双精度型数组元素为:" );
       printArray( doubleArray ); // 传递一个双精度型数组
  System.out.println( "\n字符型数组元素为:" );
       printArray( charArray ); // 传递一个字符型数组
   } 
}

泛型类

泛型类的声明和非泛型类的声明类似，除了在类名后面添加了类型参数声明部分
和泛型方法一样，泛型类的类型参数声明部分也包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符，接受一个或多个参数，这些类被称为参数化的类或参数化的类型

public class Demo4<T> { 
     
 private T t;
public void add(T t) { 
   
   this.t = t;
 }
 public T get() { 
   
   return t;
 }
 public static void main(String[] args) { 
   
   Demo4<Integer> integerDemo = new Demo4<Integer>();
   Demo4<String> stringDemo = new Demo4<String>();
  integerDemo.add(new Integer(10));
   stringDemo.add(new String("泛型类"));
   System.out.printf("整型值为 :%d\n\n", integerDemo.get());
   System.out.printf("字符串为 :%s\n", stringDemo.get());
  }
}

列表和队列

迭代的陷阱：在迭代的中间调用容器的删除方法

public void remove(ArrayList<Integer> list) { 
   
    for (Integer a : list) { 
   
        if (a <= 100) { 
   
            list.remove(a) //抛出ConcurrentModificationException
            }
        }
    }
/** 迭代器内部会维护一些索引位置相关的数据，迭代过程中容器不能发生结构性变化（添加、插入、删除），否则索引位置就失效。 */

集合框架

Collection接口

Java提供了一套实现了Collection接口的标准集合类。其中一些是具体类，这些类可以直接拿来使用，而另外一些是抽象类，提供了接口的部分实现。
Collection又有两个分支
1.List(列表)，2.Set(集合)，List和Set也都是接口
List接口的特点: 集合中的元素有顺序，能重复
集合中分为三大接口:
Collcction、Map(映射)、Itcrator(迭代的父类接口)
集合框架的接口和类在java.util包中
Collcction分支为两个子接口list(列表接口),set(集合接口)

List

集合框架List接口
有序的接口，此接口的用户可以对列表中的每个元素的插入位置进行
精确的控制，用户可以根据元素的整数索引(在列表中的位置)访问元素，并索列表中的元素
List实现类：ArrayList，Vector，LinkedList
1.ArrayList是底层用数组实现的List
特点：查询效率高,增删效率低, 线程不安全
2.LinkedList是底层用双向循环链表实现的List
特点：查询效率低，增删效率高
3.Vector: 底层用数组实现List接口的另一个类
特点：重量级,占据更多的系统开销,线程安全

• ArrayList不是线程安全的，内部采用动态数组实现
  1、可随机访问，按照索引访问效率高
  2、除非数组已排序，否则按照内容查找元素效率低，性能与数组长度成正比
  3、添加N个元素效率为O(N)，N为数组长度
  4、插入和删除元素效率低，因为需要移动元素，具体为O(N)

• LinkedList内部是双向链表实现，每个元素在内存都是单独存放
  1、按需分配空间
  2、不可以随机访问，按照索引访问效率低
  3、不管是否排序，按照内容查找元素效率都低
  4、两端添加、删除元素效率高
  5、中间插入、删除元素要先定位，效率较低，但修改本身效率很高

• ArrayDeque实现了双端队列，内部使用循环数组实现
  1、两端添加、删除效率很高
  2、根据元素内容查找和删除的效率较低
  3、没有索引位置的概念，不能根据索引进行操作

Set

集合框架Set接口
Set接口特点是集合中的元素无顺序（存入和取出的顺序不一定一致），不能重复
Set接口一个不包含重复元素的collection,更确切的讲，set不包含满足e1.euuals(e2)的元素
对e1和e2，并且最多包含一个null元素，正如其名称所暗示的，此接口模仿了数学上的ste抽象
HashSet类实现Set接口，由哈希表(实际上是一个HashMap实例)支持，它不保证set的迭代顺序，特别是它不保证该顺序恒久不变，此类允许使用null元素 。

Set分支的常用类有：HashSet，TreeSet

1. HashSet：底层数据结构是哈希表 ；特点：增、删集合中的元素速度快 。
2. TreeSet集合中的元素除了没有顺序和不能重复外，还会自然排序，这便是该集合的特点。

• HashSet
  set是没有重复元素，不保证顺序的容器接口
  与HashMap类似，HashSet要求元素重写hashCode和equals方法
  实现set接口，内部利用HasnMap实现：1、没有重复元素；2、高效添加、删除元素以及判断元素是否存在；3、没有顺序
• TreeSet
  实现了：排重和有序。排重是基于比较结果的
  基于TreeMap
  没有重复元素
  添加、删除元素，判断元素是否存在效率较高
  有序
  要求Comparable接口或者通过构造方法提供一个Comparator对象
• EnumSet：用位向量实现
  位向量就是用一个位表示一个元素的状态，一组位表示一个集合的状态，每个位对应一个元素，状态只有两种

Map

集合框架Map接口
Map接口
特点：K与V，键值对，映射所维护的键的类型，映射值得类型
将键映射到值得对象，一个映射不能包含重复的键，每个键最多只能映射一个值
HashMap，Hashtable，TreeMap，LinkedHashMap
1.HashMap：特点:线程不安全 允许key或者value是null值
2.TreeMap特点:按照键值排序，线程不安全

• HashMap：实现Map接口，内部有一个哈希表即数组table，每个table[i]指向一个单向链表，根据键存取值，用键算出hash值，取模得到数组中的索引位置buketIndex，然后操作table[buketIndex]指向的单向链表
  1、根据键存取值效率很高
  2、键值对没有顺序，因为hash值是随机的
  3、线程不安全

• 排序二叉树
  TreeMap和TreeSet的实现基础
  顺序特点：左子树所有节点小于该节点，右子树所有节点大于gai
  基本的保存、删除、查找效率为O(h),h为树的高度
  AVL树保证树的高度平衡，红黑树保证大致平衡

• TreeMap
  按键而不是按值有序，它要么键实现Comparable接口，要么创建时传递一个Comparator对象
  内部是红黑树实现的
  根据键保存、查找、删除效率较高，O(h)

• LinkedHashMap
  是HashMap的子类，内部还有一个双向链表维护键值对的顺序
  插入顺序：先添加的在前面，后添加的在后面，修改操作不影响顺序
  访问顺序：最末尾的是最近访问的，最开始的是最久没被访问的，因为对一个键执行get/put操作后对应的键值对会移到链表末尾
  用于缓存
  1、缓存就是用来保存常用的数据，容量小访问快
  2、LRU是缓存里一种流行的替换算法，即当缓存满了，最近最少使用的先被清理出去
  内部维护一个单独的双向链表，默认是插入顺序

Set和List的区别

1. Set 接口实例存储的是无序的，不重复的数据。List 接口实例存储的是有序的，可以重复的元素
2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>
3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector>

堆与优先级队列

堆

是完全二叉树（给定任意一个节点可以根据其编号直接快速计算出其父节点和孩子节点编号）
逻辑概念上是一颗完全二叉树，物理存储上使用数组，还有一定的顺序要求
根据顺序分为：最大堆和最小堆
最大堆：每个节点都不大于其父节点。最小堆相反
添加和删除元素的时候有两个关键的过程以保持堆的性质，一个是向上调整一个是向下调整

PriorityQueue优先级队列

队列长度没有限制，每个元素都有优先级，队头的元素优先级最高
内部用堆实现，内部元素不是完全有序的，不过逐个出队会得到有序的输出
查看头部元素效率很高，O(1),入队出队效率较高，O(log2(N))
根据值查找和删除元素效率比较低，O(N)
求中值：元素是动态添加（用一个最大堆一个最小堆）
步骤：
1、设当前中位数为m，最大堆维护<=m的元素，最小堆维护>=m的元素，但两个堆都不包含m
2、当新元素e到达与m进行比较，若e<=m将其加入最大堆，反之加入最小堆
3、第2步之后如果最大堆和最小堆元素个数差>=2，则将m加入元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给m

迭代器

遍历一个集合中的元素，例如，显示集合中的每个元素 ；一般遍历数组都是采用for循环或者增强for，这两个方法也可以用在集合框架，但是还有一种方法是采用迭代器遍历集合框架，它是一个对象，实现了Iterator 接口或ListIterator接口
迭代器，使你能够通过循环来得到或删除集合的元素
ListIterator 继承了Iterator，以允许双向遍历列表和修改元素

迭代器方法：
使用 Java Iterator，通过实例列出Iterator和listIterator接口提供的所有方法

遍历ArrayList

public class Demo{ 
   
//三种方法都是用来遍历ArrayList集合 
//第三种方法是采用迭代器的方法，该方法可以不用担心在遍历的过程中会超出集合的长度
public static void main(String[] args) { 
   
    List<String> list=new ArrayList<String>(); //实例化List集合
    list.add("Hello"); //添加元素
    list.add("World");
    list.add("HAHAHAHA");
    //第一种遍历方法使用foreach遍历List
    for (String str : list) { 
               
    //也可以改写for(int i=0;i<list.size();i++)这种形式
       System.out.println(str);
    }
    //第二种遍历，把链表变为数组相关的内容进行遍历
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(int i=0;i<strArray.length;i++) //这里也可以改写为 foreach(String str:strArray)这种形式{ 
   
       System.out.println(strArray[i]);
    }
  //第三种遍历 使用迭代器进行相关遍历
  Iterator<String> ite=list.iterator();
    while(ite.hasNext()){ 
    //判断下一个元素之后有值
        System.out.println(ite.next());
   }
}
}

遍历Set：

//对 set 的遍历 
  
//1.迭代遍历： 
Set<String> set = new HashSet<String>();  
Iterator<String> it = set.iterator();  
while (it.hasNext()) { 
     
  String str = it.next();  
  System.out.println(str);  
}  
  
//2.for循环遍历： 
for (String str : set) { 
     
      System.out.println(str);  
}  
  
  
//优点还体现在泛型 假如 set中存放的是Object 
Set<Object> set = new HashSet<Object>();  
//for循环遍历： 
for (Object obj: set) { 
     
      if(obj instanceof Integer){ 
     
                int aa= (Integer)obj;  
             }else if(obj instanceof String){ 
     
               String aa = (String)obj  
             }  
              ........  
}

遍历 Map：

public class Demo2{ 

//集合是一个对象，可容纳其他对象的引用。集合接口声明对每一种类型的集合可以执行的操作，集合框架的类和接口均在java.util包中 
//任何对象加入集合类后，自动转变为Object类型，所以在取出的时候，需要进行强制类型转换
public static void main(String[] args) { 

Map<String, String> map = new HashMap<String, String>(); //实例化Map集合
map.put("1", "value1"); //添加元素
map.put("2", "value2");
map.put("3", "value3");
//NO1.：普遍使用，二次取值
System.out.println("通过Map.keySet遍历key和value：");
for (String key : map.keySet()) { 

System.out.println("key= "+ key + " and value= " + map.get(key));
}
//NO2.
System.out.println("通过Map.entrySet使用iterator遍历key和value：");
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) { 

Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//NO3.：容量大时推荐使用此方法
System.out.println("通过Map.entrySet遍历key和value");
for (Map.Entry<String, String> entry : map.entrySet()) { 

System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//NO4.
System.out.println("通过Map.values()遍历所有的value，但不能遍历key");
for (String v : map.values()) { 

System.out.println("value= " + v);
}
}
}

相关连接：
Java程序设计（基础）- 数组