第七章 集合

泛型

为什么用泛型：

早期的Object类型可以接收任意的对象类型，但是在实际的使用中，会有类型转换的问题。也就存在这隐患，所以Java提供了泛型来解决这个安全问题

什么是泛型：

●泛型，即“参数化类型”。一提到参数，最熟悉的就是定义方法时有形参，然后调用此方法时传递实参

●参数化类型，就是将类型由原来的具体的类型参数化，类似于方法中的变量参数，此时类型也定义成参数形式，然后在使用/调用时传入具体的类型

public class Demo{ //T可以为任意标识符，常见的如T、E、K、V等形式的参数常用于表示泛型            private T key; //key这个成员变量的类型为T,T的类型由外部指定 
       public Generic(T key) {//泛型构造方法形参key的类型也为T，T的类型由外部指定 
              this.key = key; 
       } 
       public T getKey(){ //泛型方法getKey的返回值类型为T，T的类型由外部指定 
              return key; 
       }
}

泛型的类型参数只能是类类型（包括自定义类

泛型的类型参数可以有多个。

如果没有定义具体类型,默认为Object

集合的概念

当我们需要保存一组一样（类型相同）的元素的时候，我们应该使用一个容器来存储，数组就是这样一

个容器，但是数组一旦定义，长度将不能再变化，然而在我们的开发实践中，经常需要保存一些变长的

数据集合，于是，我们需要一些能够动态增长长度的容器来保存我们的数据，而我们需要对数据的保存

的逻辑可能各种各样，于是就有了各种各样的数据结构。Java中对于各种数据结构的实现，就是我们用

到的集合。

集合的体系 Collection 接口

Collection 接口－定义了存取一组对象的方法，其子接口Set和List分别定义了存储方式

Set 中的数据对象没有顺序且不可以重复

List 中的数据对象有顺序且可以重复

Collection 接口中的一些方法：

    add(E e)//添加元素
    addAll(Collection c) //将制定集合添加到此集合
    clear() //清空集合
    contains(Object o) //如果刺激和包含指定元素，则返回true
    containsAll(Collection c) //如果此集合包含指定 集合中的所有元素，则返回true。 
    isEmpty() //如果此集合不包含元素，则返回 true 。 
    remove(Object o) //从集合中删除某个元素
    removeAll(Collection c) //删除指定集合中包含的所有此集合的元素（可选操作）。 
    size() //集合中的元素数
    retainAll(Collection c) //;求交集,集合数据发生变化返回true, 不变返回false

List 接口及实现类

List继承了Collection接口,有三个实现的类

ArrayList ：底层是数组,查询快,从中间删除,添加慢

linkedList： 底层是双向链表,查询慢,从中间删除,添加快

Vector ：底层是数组,查询快,从中间删除,添加慢,线程安全

ArrayList

构造方法

ArrayList();默认不创建底层数组,当添加第一个元素时,创建一个长度10的数组 ArrayList(int length); 创建对象时,创建一个指定长度的数组 ArrayList(Collection collection); 把一个实现了Collection接口的子类,构造成一个ArrayList

扩容

         //ArrayList<>()创建一个长度为10的底层数组,第一次添加元素时,真正创建数组
         //ArrayList alist1 = new ArrayList<>(20); 
         
                   public boolean add(E e) {
                        ensureCapacityInternal(size + 1);  //检查元素能否放得进去
                        elementData[size++] = e;
                        return true;
                    }
                        放进去后容量大小 - 底层数组长度 >0 
                  if (minCapacity - elementData.length > 0)
                          grow(minCapacity); 扩容
                          
                   private void grow(int minCapacity) {
                        // overflow-conscious code
                        int oldCapacity = elementData.length;
                        int newCapacity = oldCapacity + (oldCapacity >> 1); 新数组容量为原来的1.5倍
                        if (newCapacity - minCapacity < 0)
                            newCapacity = minCapacity;
                        if (newCapacity - MAX_ARRAY_SIZE > 0)
                            newCapacity = hugeCapacity(minCapacity);
                        // minCapacity is usually close to size, so this is a win:
                         * 数组复制,创建一个新数组,将原来的数组内容复制到新数组中
                        elementData = Arrays.copyOf(elementData, newCapacity); 
                    }       

ArrayList一些方法

        //System.out.println(list.get(3));//查询快，直接返回指定位置的值
        //System.out.println(list.remove(3));//删除并返回指定位置的值
​
        list.removeIf(new Predicate() {//条件删除
            @Override
            public boolean test(String s) {
                return s.equals("e");//删除符合条件的元素
            }
        });
​
        list.set(0,"W");//替换指定位置的元素
        list.sort(new Comparator() {//排序 指定排序的规则
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        List li =  list.subList(0, 4);//从原集合中复制一段返回新集合,原集合不变

       public class ArrayListChild extends ArrayList{
        public static void main(String[] args) {
        ArrayListChild a = new ArrayListChild();
                      a.add("a");//0
                      a.add("a");
                      a.add("a");
                      a.add("a");
                      a.add("b");//4
                      a.add("c");
                      a.add("d");
                      a.removeRange(0, 4);//在ArrayList的子类中使用
                      System.out.println(a);
        }
​
    }

ArrayList遍历方法

for循环

length (数组) length()(字符串) size()(集合) 循环时允许删除元素,但是我们需要注意索引与集合长度之间关系

for(int i=0;i

增强for循环 循环时不允许从中删除元素

for(String s : alist){
                     System.out.println(s);
                 }

迭代器遍历

                           
                 
                                
                           //listIterator() 只能对List接口下的实现类进行遍历
               ListIterator lit =   alist.listIterator(alist.size());
                                while(lit.hasPrevious()){
                                    System.out.println(lit.previous());
                                }

linkedList

linkedList与ArrayList方法大致相同

linkedList采用链表存储方式，插入、删除元素时效率比较高。查询效率比较慢

       
        linkedList list = new linkedList<>();
        list.add("a");
        list.add("a");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list.contains("a"));
        list.get(3);
        System.out.println(list.peek());//检索但不删除此列表的头（第一个元素）。
        System.out.println(list.pop());//从此列表表示的堆栈中弹出一个元素。
        list.push("d");//将元素推送到由此列表表示的堆栈上。
        list.remove();//检索并删除此列表的头（第一个元素）。
        list.remove(3);//删除该列表中指定位置的元素。
        list.set(1,"X");//用指定的元素替换此列表中指定位置的元素。
        System.out.println(list.size());//返回此列表中的元素数。

​

Vector

底层也是数组 查询快,中间增删慢,是线程安全的

          public synchronized(同步锁) boolean add(E e) {
                    modCount++;
                    ensureCapacityHelper(elementCount + 1);
                    elementData[elementCount++] = e;
                    return true;
                } 

Set接口及实现类

Set接口继承了Collection接口

Set中所存储的元素是不重复的,但是是无序的, Set中的元素是没有索引的

HashSet：无序，底层数据结构是哈希表+链表

TreeSet：有序，底层数据结构是二叉树(红黑树是一种自平衡的二叉树)

HashSet

HashSet添加时如何判断值是否重复

添加时会调用hashCode(),equals() 添加时要比较内容是否相等,既要保证效率,又要保证安全 先调用hashCode()计算出一个哈希值,比较哈希值非常快,但是不安全 当哈希值相同时,再调用equals()方法比较

        HashSet set = new HashSet<>();
         
​
     "s".hashCode();//字符串.Integer....这些类重写了hashCode()都是根据对象中包含的内容来计算哈希值

HashSet遍历

listIterator()和iterator()区别

listIterator()只能遍历实现了List接口的类

iterator() 遍历list,set

         
           for(Integer it : set){
               System.out.println(it);
           }

      //Iterator 遍历
      Iterator it =  set.iterator();
              while(it.hasNext()){
                Integer n = it.next();
                   System.out.println(n);
                   // it.remove();
              }
      
     
      Stream stream =  set.stream();
      stream.forEach(new Consumer(){
          @Override
            public void accept(Integer t) {
                      System.out.println(t);                            
            }
      });

TreeSet

可以给Set集合中的元素进行指定方式的排序。存储的对象必须实现Comparable接口

TreeSet底层数据结构是红黑树

Map接口 三个实现类

HashMap

TreeMap

Hashtable（线程安全）

方法

clear();//从该地图中删除所有的映射（可选操作）
​
containsKey(Object key);//如果此映射包含指定键的映射，则返回 true 
​
containsValue(Object value);//如果此地图将一个或多个键映射到指定的值，则返回 true 
​
remove(Object key);//如果存在（从可选的操作），从该地图中删除一个键的映射
​
get(Object key);//返回到指定键所映射的值，或 null如果此映射包含该键的映射
​
put(K key, V value);//将指定的值与该映射中的指定键相关联（可选操作）
​
putAll(Map m);//将指定地图的所有映射复制到此映射（可选操作）
​
size();//返回此地图中键值映射的数量
​
isEmpty();//如果此地图不包含键值映射，则返回 true 
​
replace(K key, V value);//只有当目标映射到某个值时，才能替换指定键的条目
​
keySet();//返回此地图中包含的键的Set视图
​
entrySet();//返回此地图中包含的映射的Set视图
​
forEach(BiConsumer action);//对此映射中的每个条目执行给定的操作，
​
直到所有条目都被处理或操作引发异常

HashMap

HashMap中元素的key值不能重复， 排列顺序是不固定的,可以存储一个为null的键。

HashMap的底层是哈希表+链表+红黑树

用key计算出哈希值，再用哈希值计算出元素在哈希表中的位置。当相同位置有元素加入进来后，才用链表存储（拉链法），当元素个数达到8时，采用红黑树存储。

哈希表的默认长度为8，负载因子为0.75，每次触发扩容机制，扩容为原来的1.5倍

        HashMap hashMap = new HashMap<>();
        hashMap.put("a","a");
        hashMap.put("a","b");
        hashMap.put("b","b");
        hashMap.put("j","i");
        hashMap.put("i","j");
        System.out.println(hashMap);
        //hashMap.clear();
        System.out.println(hashMap.containsKey("i"));//包含键
        System.out.println(hashMap.containsValue("i"));//包含值
​
​
        System.out.println(hashMap.get("o"));//根据键查找值，键不存在，返回null
        hashMap.remove("i");
        hashMap.replace("a","m");//替换已有的键，如果键不存在，不能替换
        hashMap.replace("s","s");

TreeMap

TreeMap中所有的元素都保持着某种固定的顺序，如果需要得到一个有序的Map就应该使用TreeMap，

key值所在类必须实现Comparable接口

Hashtable

底层也是哈希表+链表(红黑树)实现

是线程安全 synchronized Stringbuffer,Vector

和HashMap相似

Collections类

方法

        ArrayListlist = new ArrayList<>();
        list.add("c");
        Collections.addAll(list,"d","b","a");//将后面的元素添加进list集合
        Collections.sort(list);//排序
        int index = Collections.binarySearch(list,"a");//二分查找，返回一个int类型的索引
        Collections.swap(list,1,3);//将第一个位置的元素和第三个位置的元素交换
        ArrayList list1 = new ArrayList<>();
        list1.add("a");
        list1.add("a");
        list1.add("a");
        list1.add("a");
        list1.add("a");
        Collections.copy(list1,list);//把后面的集合复制到前一个集合中去并覆盖。前面的集合元素必须必后面的集合元素多
            List