1. 数组与集合的共同点和区别
2. 集合框架
3. --Set元素存取无序不可重复无索引
4. Iterator 接口
5. Stack 是 Vector的子类
6. 泛型
7. Map 接口
8. Collections 类
9. 关于数组 集合的总结

 

一 、集合架构

• 数组与集合的共同点和区别

  • 相同点：数组或集合都是容器都可以存储对象
  • 区别是：
        --数组是长度固定的,一旦指定长度则不能再改变；数组除了可以存储对象，还可以存储基本数据类型；数组只能存储一种类型的数据
        --集合是长度可变的,可以随着使用自动增加容量；集合只可以存储对象 ； 集合可以存放不同类型的对象。

 

• 集合框架

  
  
  
  
  • Collection --集合架构的根接口

 

• • 集合的共性抽取为 Collection 接口
      

  集合用来存放对象，集合中的对象称为集合的元素。有的集合可以有序存放元素，有的集合无序存放元素 ；有的集合允许重复元素，有的集合不允许重复元素

  Collection接口是所有集合的顶层接口，继承了Iterable,集合都有迭代性 ,JDK没有直接的Collection实现类，但派生很多子接口，其中List接口和Set接口是两大 

  基本子接口

 

• Collection 的基本给功能:

   增:add(E e) --添加单个元素  添加失败返回假 添加成功返回真 有的集合不允许重复元素，所以调用该方法就会返回false

                          如果是集合不支持add操作或不允许添加指定类的元素或不允许添加null元素等而导致添加 失败，则会抛出异常

       addAll(集合) --添加一个集合  添加失败返回假 添加成功返回真

   删:remove(Object o)  --移除指定单个元素 ，如果集合而存在一个或多个（可重复元素）指定元素的则移除符合的一个元素并返回true，如果不存在返回false
        removeAll(集合) --移除交集  ， 移除该集合中存在的与指定集合中相同的所有元素 ， 如果存在交集则移除成功返回true
        retainAll(集合) --保留交集 ，移除此集合中未包含指定集合相同的元素的所有元素
        clear() --清空集合中所有元素 ，如果集合不支持clear则抛出异常

   换:toArray() --集合转换成数组，Object类型数组       

      <T> T[]  toArray(T[] a) --返回指定类型的数组

   查:contains(Object o) --包含指定元素返回真 

        containsAll(集合) --此集合包含指定子集（所有元素）
        isEmpty() 此集合不包含任何元素返回true

       hashCode() 集合的哈希码值 

       size() --集合元素个数 ，如果集合包含的元素个数超过 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。
       equals(Object o) --比较此collection是否与指定对象相等

   取: Iterator<E> iterator()  返回以恰当顺序在此列表的元素上进行迭代的迭代器。 集合特有的元素的获取方式
        

• Collection 的两个常见子接口 List Set 分别是元素有序可重复,元素无序不可重复的集合

 

• •  1 |--List:元素有序,可重复,有索引

          因为List的有序性和索引可以精确的快速访问List集合中的元素

          List集合允许元素重复,判断元素重复的依据是e1.equals(e2) = true 或e1 = e2 =null;

          List 遍历方式: for循环 和 迭代 ,可以像数组一样根据索引搜索或访问元素

          List提供了获取特殊的ListIterator迭代器,除了具有Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问

                提供了一个方法来获取从列表中指定位置开始的列表迭代器。

          List集合继承了Collection接口的所有方法并根据列表的索引扩展了一些列表特有的方法

               分别添加了按位置添加,删除,更改,搜索,获取元素的功能

               还提供了获取指定列表迭代器功能

          List默认添加元素的特点是add(元素/集合)是将元素添加到列表结尾处

               而删除元素remove(元素)则是删除列表中第一次出现的存在的元素

 

• • •  1.1 List 特有方法

      增:void add(int index, E element) --按指定位置插入指定元素
          boolean addAll(int index, Collection<? extends E> c)   --从List列表集合中的指定位置开始插入指定 collection中的所有元素

      删: E remove(int index) --删除指定位置元素

      改: E set(int index, E element)   -- 用指定元素替换列表中指定位置的元素       

      取: E get(int index) --返回列表中指定位置的元素。 
           List<E> subList(int fromIndex, int toIndex)
                             --返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分 的子列表

      查: ListIterator<E> listIterator()
                             --返回此列表元素的列表迭代器（按适当顺序）。
           ListIterator<E> listIterator(int index)
                              --返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。
           int indexOf(Object o)

                              --返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。

     int lastIndexOf(Object o)

              --返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1。

   

• • •  1.2 List 几个常见子类 

       ArrayList , LinkedList , Vector

       三类都不是List的直接实现类,他们都是继承自实现了一部分List方法的抽象类AbstractList,

      1.2.1 ArrayList  :底层数据结构为数组结构,特点是查询速度快,增删慢 线程同步 ,效率高

      1.2.2 LinkedList :底层数据结构使用链表数据结构,特点是增删速度快,查询慢
         └--LinkedList 常见的特有方法 在首部或尾部插入 获取 删除的操作
         addFirst();--将指定元素插入此列表的开头。
         addLast();--将指定元素添加到此列表的结尾。
         getFirst();--返回此列表的第一个元素。
         getLast();--返回此列表的最后一个元素。
         removeFirst();--移除并返回此列表的第一个元素。
         removeLast();--移除并返回此列表的最后一个元素。
        JDK1.6出现的替代方法
         offerFirst();--在此列表的开头插入指定的元素。
         offerLast();--在此列表的开头插入指定的元素。
         peekFirst();--获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
         peekLast();--获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
         pollFirst();--获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
         pollLast();--获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。

      1.2.3 Vector   :底层是数组数据结构,类似于 ArrayList 但线程同步 ,vector在 JDK1.0后出现,JDK1.2后出现ArrayList
         ├ 
         └ Stack  类Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，
             还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

          --Vector 特有的取出方式是枚举 枚举跟迭代器很像 
            枚举的功能跟迭代器一样,其缺点是枚举名和方法名都很长,故逐渐被迭代器取代

 

• • • 1.3 ArrayList  LinkedList 以及 Vector 它们三者的区别与联系
            
           

 1.3.1 同步性
                  ArrayList,LinkedList 是线程不同步的，而 Vector 线程同步,但性能差.如果不要求线程安全的话，可以

          使用 ArrayList 或 LinkedList ，可以节省为同步而耗费开销。

          但在多线程的情况下，应使用 Vector .

1.3.2 查询 修改 删除 效率

                    ArrayList 和 Vector 是数组结构 向其中添加对象速度慢 你创建数组时并不能确定其容量，所以当改变这个

          数组时就必须在内存中做很多事情。当你要想数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。

          当然如果按默认的add方式添加元素是添加到列表的结尾处 .

                    LinkedList 双向链表实现存储 每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当

          一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可，当删除记录时也一样。        

          但缺点是：不能随即访问 虽然存在get()方法，但是这个方法是通过遍历接点来定位的所以速度慢。

                   所以，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。

          如果是对其它指定位置的插入、删除操作，最好选择LinkedList

 

1.3.3 数据增长
                   ArrayList 和 Vector 都是使用数组形式来存储的对象,当你向这两种类型中增加元素的时候，如果元素的数目

超出了内部数组目前的长度它 们都需要扩展内部数组的长度，Vector 默认自动增长原来一倍的数组长度，ArrayList是原

来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。 所以如果你要在集合中保存大量的数据那么

使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

• •  2 |--Set:元素(存取)无序,不可重复,无索引

   Set 接口下常见实现子类 HashSet 和 TreeSet

   Set集合元素是无序不可重复的

        
    2.1 HashSet :底层数据结构为哈希表,线程是非同步的
          哈希算法可以提高从集合中查找元素的效率，这种方法将集合分成若干个存储区域，
          每个对象可以计算出一个哈希码，可以将哈希码分组，每组分别对应某个存储区域，
          根据一个对象的哈希码就可以确定该对象应该存储在哪个区域

         HashSet 就是采用哈希算法存取对象,内部采用对某个数字n进行取余的方式对哈希码进行分组
          和划分对象的存储区域。Object类中定义了一个hashCode()方法来返回每个Java对
          象的哈希码，当从HashSet集合中查找某个对象时，Java系统首先调用对象的hashCode()
          方法获得该对象的哈希码，然后根据哈希码找到相应的存储区域，最后取出该存储区
          域内的每个元素与该对象进行equals方法比较，这样不用遍历集合中的素有元素就可以
          判断集合中是否已存在相同元素

       HashSet 保证集合元素的唯一性的实现过程:

              通过两个方法完成 hashCode 和 equals 
             如果元素的 HashCode值相同,才会判断equals是否为true
             如果元素的 HashCode值不同,不会调用equals方法

             1)，判断两个对象的hashCode是否相等  如果不相等，认为两个对象也不相等，equals的结果必为false. 如果相等，转入2) 
             2)，判断两个对象用equals运算是否相等  如果不相等，认为两个对象也不相等  如果相等，认为两个对象相等
       

       为什么要先判断HashCode?

       因为equals方法需要向下转型,效率很低,hash值是对象相等的必要条件,而equals相等是对象相等的充分条件
       所以判断必要条件成立就没必要判断完全条件

       

       为什么都重写hashcode和equals
       对于判断是否存在,删除元素操作,依赖的方法是元素的hashcode和equals
      equals是Object类提供的方法之一，每一个java类都继承自Object类，
      所以说每一个对象都有equals这个方法。而我们在用这个方法时却一般都重写这个方法
      
      Object类中equals()方法的源代码：
      public boolean equals(Object obj) {
       return (this == obj);
      }
      当实例等于它本身时,equals返回true,此时比较的是两个引用是否指向内存中同一个对象,我们常常要比较的
      是他们是否在"内容"上相等,而不是指向同一对象,所以我们要重写这个方法
      String s1 = new String(“sss”);
      String s2 = new String(“sss”);
      s1.equals(s2) //返回true
      s1 ==s2 //返回false 
      s1.equals(s2)为ture，说明String类中已经重写了equals()方法，如果不重写equals()方法，
      那么s1.equals(s2)默认比较两个对象所指向的内存地址是否相同，返回值必然为false。

       了解了equals重写，我们再看hashCode()这个方法，hashcode()这个方法也是从object类中继承过来的，
       在object类中定义如下：
      public native int hashCode(); 表明是一个本地方法
      hashCode()返回该对象的哈希码值，该值通常是一个由该对象的内部地址转换而来的整数，它的实现主要是
      为了提高哈希表的性能,在每个重写了equals方法的类中，你必须也要重写hashCode方法。如果不这样做的话，
      就会违反Object.hashCode的通用约定，从而导致该类无法与所有基于散列值(hash)的集合类结合在一起正常运行。
      

      如果我们对一个对象重写了euqals，意思是只要对象的成员变量值都相等那么euqals就等于true，但不重写hashcode，
      那么我们再new一个新的对象，当原对象.equals（新对象）等于true时，两者的hashcode却是不一样的，由此将产生
      了理解的不一致，如在存储散列集合时（如Set类），将会存储了两个值一样的对象，导致混淆，因此，就也需要重写
      hashcode。为了保证这种一致性，必须满足以下两个条件：

      (1)当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()必须为true
      (2)当obj1.hashCode() == obj2.hashCode()为false时，obj1.equals(obj2)必须为false

       hashCode()的返回值和equals()的关系如下：
       如果x.equals(y)返回“true”，那么x和y的hashCode()必须相等。
       如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等。
      equals比较结果不相等的对象,可以有相等或不等的的hash值,
     

 

• 内存溢出

     当一个对象被存储进HashSet集合中以后，就不能修改这个对象的那些参与计算哈希值的字段了，
     否则，对象修改后的哈希值与最初存储进HashSet集合中的哈希值就不同了，在这种情况下，即使
     在contains方法使用该对象的当前引用作为的参数去HashSet集合中检索对象，也将返回找不到对
     象,导致无法从HashSet集合中单独删除当前对象, 在不断的修改删除增加对象的操作 ,表面上在不
     断增加对象，删除对象，但实际内存中并没有删除，该对象以后不再用了，可是内存中却一直存在，
     造成浪费，集合中的元素不断增加,直到内存用光 , 最终导致内存泄露。
                    
    Set set = new HashSet();
    Person p1 = new Person(3,"b");
    set.add(p1);
    set.add(new Person(31,"b"));
    set.add(new Person(3,"b"));
    System.out.println(set.contains(p1));//true
    p1.i=23;
    System.out.println(set.contains(p1));//false
    System.out.println(set.remove(p1));//false,说明原来的元素没有被删除,因为改完以后hash值改变了,
    //所以传入了hash结构的集合,再对其进行修改操作,会导致其hash码值不断改变,在不断的修改删除增加对象的操作会
    //集合中的元素不断增加,直到内存用光 , 导致内存的泄露或溢出
    System.out.println(set.size());

在内存对象明明已经不需要的时候，还仍然保留着这块内存和它的访问方式（引用）。内存泄露的两个条件：无用，无法回收。
    1 Vector v=new Vector(10);
    2 for (int i=1;i<100; i++){
    3 Object o=new Object();
    4 v.add(o);
    5 o=null;
    6 }
Java的一个重要优点就是通过垃圾收集器(Garbage Collection，GC)自动管理内存的回收，程序员不需要通过调用函数来释放内存
在这个例子中，代码栈中存在Vector对象的引用v和Object对象的引用o。在For循环中，
我们不断的生成新的对象，然后将其添加到Vector对象中，之后将o引用置空。问题是当
o引用被置空后，如果发生GC，我们创建的Object对象是否能够被GC回收呢？答案是否定
的。因为，GC在跟踪代码栈中的引用时，会发现v引用，而继续往下跟踪，就会发现v引用
指向的内存空间中又存在指向Object对象的引用。也就是说尽管o引用已经被置空，但是Object
对象仍然存在其他的引用，是可以被访问到的，所以GC无法将其释放掉。如果在此循环之后，
Object对象对程序已经没有任何作用，那么我们就认为此Java程序发生了内存泄漏。
随着越来越多的服务器程序采用Java技术，例如JSP，Servlet， EJB等，服务器程序往往长期运行。

另外，在很多嵌入式系统中，内存的总量非常有限。内存泄露问题也就变得十分关键，即使每次运行

少量泄漏，长期运行之后，系统也是面临崩溃的危险。

 

• • •     2.2 TreeSet :可以对 Set集合元素进行自然排序

         底层数据结构为二叉树
         保证元素唯一性的依据是compareTo\compare方法return 是不是零
         public boolean add(E e)将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。
         如果该 set 不包含满足 (e==null ? e2==null : e.equals(e2)) 的元素 e2，则将指定元素 e
         添加到此 set 中。如果此 set 已经包含这样的元素，则该调用不改变此 set 并返回 false。

         2.2.1 TreeSet 排序的第一种方式:让元素自身具备比较性
                   存入集合中的元素的类需要实现 Comparable 接口,覆盖compareTo方法
                   接口Comprable强行对实现它的每个类的对象进行整体排序也称为元素的自然顺序,或者默认顺序

         2.2.2 TreeSet 排序的第二种方式
                  当元素不具备比较性时,或者具备比较性不是所要比较的, 此时需要让集合自身具备比较性
         在集合初始化时,将一个自定义的实现了 Comparator 的比较器传入该集合,让集合具备比较性
         该比较器复写了 Comparator 中的compare方法

• • •     Comparable 与  Comparator 的区别

    java.lang包的 Comparable 与 java.util包的 Comparator 都是接口
    Comparable :此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，
      该接口的 int compareTo (T o ) 方法被称为它的自然比较方法。比较此对象与指定对象的顺序。
      如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。
    Comparator :此接口强行对某个对象 collection 进行整体排序 的比较函数
      该接口的  int compare(T o1, T o2) 方法比较用来排序的两个参数。根据第一个参数小于、等于
      或大于第二个参数分别返回负整数、零或正整数。

    区别: 都是用来实现集合中元素的排序的，只是Comparable是在集合内部定义的方法实现的排序，Comparator是在
    集合外部实现的排序, 如想实现排序，就需要在集合外定义实现Comparator接口的比较器并复写方法compare()或在
    集合内实现Comparable接口复写方法compareTo()。
    如果两者都存在时，以比较器为主

•  Iterator 接口

 

Iterator 是 对 collection 进行迭代的迭代器--取出集合元素的共性抽取

  因为不同集合容器的数据结构不同,所以取出数据元素动作细节也不一样
  但都有判断和取出的共性,故不同集合容器将取出方式定义为内部类,将这些内部类
  的共性抽取即为 Iterator 接口
  1 迭代器三个方法
    ├ boolean hasNext() 如果集合中仍有元素可以迭代，则返回 true。
    ├ E next()  返回迭代的下一个元素。
    ├ void remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。
  2 如何遍历Collection中的每一个元素？
    不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子
    即可逐一访问Collection中每一个元素。典型的用法如下：
　　　　Iterator it = collection.iterator(); // 获得一个迭代子
　　　　while(it.hasNext()) {//检查还有没有元素
　　　　　　Object obj = it.next(); // 得到下一个元素
     //每次获取一个元素就可以对其进行操作了
　　　　}

• • 迭代器 , 可迭代接口 , 可迭代接口的实现, 迭代器的实现

 

public interface Iterator<E> {//迭代器 , 具备三个方法
    boolean hasNext();
    E next();
    void remove();
}   

 

public interface Iterable<T> {//可迭代接口
    Iterator<T> iterator();//获取迭代器 , Collection接口已经继承了该接口 ,所以所有的集合都具有可迭代性
}

 

public interface Collection<E> extends Iterable<E> {//Collection继承可迭代接口
...
Iterator<E> iterator();//获取迭代器
...
}

 

public interface List<E> extends Collection<E> {
 ...
    Iterator<E> iterator();
 ...
}

 

 public abstract class AbstractCollection<E> implements Collection<E> 
                            

                                                             ↓

public abstract class  AbstractList<E> extends AbstractCollection<E> implements List<E> {
 ...
        public Iterator<E> iterator()//接口Iterable的iterator方法在该抽象类中实现

         {
           return new Itr();//Itr是AbstractList的内部类 , Iterator 接口根据各种集合的数据结构特点而以集合内部类的形式实现
         }

                private class Itr implements Iterator<E> //实现迭代器 Iterator 的内部类

         { 
                            ...                   //该内部类分别实现了 迭代器的hashNext remove 和 next方法
         }
                            ...



          public ListIterator<E> listIterator() //实现ListIterator接口的listIterator方法

         {
            return listIterator(0); 
         }

          public ListIterator<E> listIterator(int paramInt)
        {
           rangeCheckForAdd(paramInt);

            return new ListItr(paramInt);//ListItr同样是一个内部类,实现了ListIterable接口
         }

         private class ListItr extends AbstractList<E>.Itr implements ListIterator<E> 

          {

                    ListItr(int arg2) {
                       super(null);
                       int i;
                       this.cursor = i;
                   }
             .....          //该内部类 分别实现了ListIterator的set(int i) previousIndex() previous() hasPrevious()
           }
 ...

 }

 List 为有序集合除了具备 iterator()方法返回Iterator迭代器 还具备具有更多功能的迭代器 ListIterator 他是 Iterator 的子接口
    在迭代时,不可以通过集合对象的方法操作集合中的元素
    因为会发生 ConcurrentModificationException 异常
    Iterator 的方法有限,只有对元素的正向判断 hasNext()方法 正向取出next()方法 和删除 remove()方法
    故为了使用添加,修改等操作,还能向后向前遍历,使用了 List 特有的子接口 ListIterator
    该接口提供了特有的方法如:
    增:void add(E e)   将指定的元素插入列表
      boolean hasPrevious() --逆向遍历列表，列表迭代器还有元素，则返回 true。
      E previous() --返回列表中的前一个元素。
      int previousIndex()   返回对 previous 的后续调用所返回元素的索引。
      int nextIndex() --返回对 next 的后续调用所返回元素的索引。
    改: void set(E e) --用指定元素替换 next 或 previous 返回的最后一个元素

    ArrayList集合示例:

import java.util.*;
class ArrayListDemo
{
 public static void main(String[] args)
 {
  //创建集合容器,使用Collection子类
  ArrayList al = new ArrayList();
  ArrayList al1 = new ArrayList();
  //增
  al.add("java1");
  al.add("java2");
  al.add("java3");
  al.add("java4");
  sop(al);
  al.add(2,"java0");//在第二个位置后添加元素java0
  sop(al);

  al1.add("java1");
  al1.add("java2");
  al1.add("java4");
  al1.add("java8");
  //删
  al.remove(2);//删除第三个位置元素
  al1.remove("java4");//删除指定元素
  //al1.removeAll(al);//调用者去掉交集
  al1.retainAll(al);//调用者保留交集
  //al.clear();//清空元素
  
  //改
  al.set(2,"java8")
  //查
  sop(al.size());//获取集合长度
  sop(al.isEmpty());//判断集合是否为空
  sop(al.contains("java9"));//判断集合是否包含指定元素
  //取
  sop(al1.get(3));//返回第四个位置上的元素
  sop(al1.indexOf("java4");//返回第一次出现元素java4的位置
  sop(al1.subList(1,3));//返回第二个位置到第四个位置以前的所有元素
  sop(al1.clone());//拷贝一个集合副本

  //获取迭代器,取出集合元素
  Iterator it = al1.iterator();
  while(it.hasNext())
   {
    sop(it.next());
   }
   /*//获取迭代器,取出集合元素的另一种写法,优点是it定义为局部的,循环结束就在内存释放
   for(Iterator it = al1.iterator(); ithasNext();)
  {
   sop(it.next());
  }

*/


   ListIterator li = al1.listIterator();
   while(it.hasNext())
  {
   Object o = li.next();
   if(o.equals("java2"))
    li.add("java9");
    //li.set("java00");

}


  public static void sop(Object o)
  {
    System.out.println(o);
  }

}

}



 

 

• • Stack 是 Vector的子类

                        Stack 类表示后进先出（LIFO）的对象堆栈 , 通过五个操作对类Vector 进行了扩展 ，允许将向量视为堆栈。

                        它提供了通常的 push 和pop 操作，以及取堆栈顶点的peek 方法、测试堆栈是否为空的empty 方法、在堆

                        栈中查找项并确定到堆栈顶距离的 search 方法。

                        

boolean	empty()           测试堆栈是否为空。
E	peek()           查看堆栈顶部的对象，但不从堆栈中移除它。
E	pop()           移除堆栈顶部的对象，并作为此函数的值返回该对象。
E	push(E item)           把项压入堆栈顶部。
int	search(Object o)           返回对象在堆栈中的位置，以 1 为基数。

 

 

LinkedList 模拟一个堆栈或队列数据结构
堆栈: 后进先出 Last in First out --LIFO  如同杯子
队列: 先进先出 First in First out --FIFO 如同水管

/*自定义的容器,将原有的容器功能封装*/

import java.util.*;
class DuiLie
{
 private LinkedList lk;

  DuiLie()
  {
   lk = new LinkedList();//一初始化就有对象lk
  }

  public void adds(Object o)
  {
   lk.addFirsrt(o);
   
  }
  public Object gets()
  {
   return lk.removeLast(); //模拟先进先出
   //return lk.removeFirst(); //模拟先进后出
   
  }
  public boolean isNull()
  {
   return lk.isEmpty();
  }
}

class LinkedListDemo
{
 public static void main(String[] args)
 {
  DuiLie dl = new DuiLie();
  dl.adds("java1");
  dl.adds("java2");
  dl.adds("java3");
  dl.adds("java4");
  dl.adds("java5");
  while(!dl.isNull())
  {
   System.out.println(dl.gets());
  }
 }
}

/*定义一个功能,将集合中重复元素剔除只保留一个*/

import java.util.*;
class SingleElement
{
   public static ArrayList singleE(ArrayList al)
   {
     ArrayList newA = new ArrayList();//定义一个临时容器
     Iterator it = al.iterator();
     while(it.hasNext())
    {
      Object o = it.next();//取要处理的容器中的元素
      if(!newA.contains(o))//判断取出的元素是否 已经存在临时容器,存在则丢弃,不存在则放进去
       newA.add(o);
    }
    return newA;
   }
 public static void main(String[] args)
 {
   ArrayList al = new ArrayList();
   al.add("java1");
   al.add("java2");
   al.add("java4");
   al.add("java2");
   al.add("java1");
   al.add("java5");
  System.out.println(al);
  
  System.out.println(singleE(al));
 }

}

 
    

• 泛型

 

  JDK1.5后出现的新特性,用于解决安全问题(升级主要考虑三要素:安全,高率,简化)是一个安全机制

  JDK1.5之前,没有泛型的情况下,通过对Object引用来实现参数的任意化,但其缺点是需要做显式的强制类型转换
  对于强制转换错误,编译器可能不提示错误,在运行的时候才出现异常,这就带来了安全隐患
  泛型是提供给Javac编译器使用的。可以限定集合中输入的类型，让编译器挡住原始程序的非法输入，
  编译器编译带类型说明的集合时会去掉“类型”信息，使程序运行效率不受影响，对于参数化的泛型类型，
  getClass()方法的返回值和原始类型完全一样，由于编译生成的字节码会去掉泛型的类型信息，只要能跳过
  编译器，就可以往某个泛型集合中加入其它类型的数据
  
  ArrayList<E>类定义和ArrayList<Integer>类引用  中涉及如下术语：

整个称为 ArrayList<E>泛型类型，ArrayList<E> 中的E称为类型变量或类型参数，

整个ArrayList<Integer>称为 参数化的类型，ArrayList<Integer>中的Integer称为类型参数的实例或实际类型参数，
       ArrayList<Integer>中的<>念着typeof，ArrayList称为原始类型。
      

•   泛型的好处:

                     1)将运行时期出现的问题ClassCastException 转移到编译时期方便于程序员解决问题,让运行时问题减少,更安全
                     2)避免了强转的麻烦

       泛型类与一般的Java类基本相同，只是在类和接口定义上多出来了用<>声明的类型参数。

•    
    泛型的规则: 
    1)通过<>来定义要操作的参数为引用数据类型(类类型,数组类型),而不是简单类型,
    2)泛型的类型参数可以有多个，如 MyClass<X, Y, Z>。在该类内不同的方法会被不同的类约束
    3)泛型的类型参数可以使用extends语句做类型上限限定，<E extends  Number>则E类型限定为Number及其子类
     泛型的类型参数可以使用super语句在类型下限限定 , <T super Number>,表示T限定为Number或其父类
    4)泛型的类型参数可以是通配符类型.如:Class<?>  type =Class.forName("java.lang.String");
    5)所声明的类型参数在Java类中可以像一般的类型一样作为方法的参数和返回值，或是作为域和局部变量的类型。     
    6)定义在类上的泛型 不能用在静态变量上, 普通静态方法不可以访问类上定义的泛型,静态方法要操作的数据类型
       不确定 , 应将泛型定义在该方法上

• •      java在使用提供的对象时,什么时候写泛型呢?

     早期是通过定义Object来扩展,现在定义泛型来完成扩展
     在集合架构中很常见,只要见到<>就是了定义泛型
     <>是用来接收类型的,当使用集合时,将集合中要存储的数据类型作为函数参数

  泛型使用示例

   

import java.util.ArrayList;
   import java.util.Iterator;
   class Person 
   {
    private String name ;
    private int age;
    
    public void Person(String name,int age )
    {
     this.name=name;
     this.age = age;
    }
    public void setName(String name)
    {
     this.name = name;
    }
    public void setAge (int age)
    {
     this.age = age ;
    }
    public String getName()
    {
     return name;
    }
    public int getAge()
    {
     return age;
    }
   }
    
     

 

public class PrintDemo
     { 
      public static void main(String[] args )
      {
      ArrayList<Person> al = new ArrayList<Person>();
      al.add(new Person("abc1",21));
      al.add(new Person("abc3",23));
      al.add(new Person("abc4",25));
      al.add(new Person("abc2",22));
      printD(al);
      }
      public static void printD(Person p)
      {
       Iterator<Person> it =p.iterator();

       while (it.hasNext())
       {
        System.out.println(it.next());
       }
        

     }

 

 

• Map 接口

 

跟 Collection 接口一样Map接口是集合框架中的顶层接口
 

 Map<K,V>   K- key  V- value  Map集合存储键值对,一对一对的存储,而且要保证唯一性 ,是将键映射到值的对象。

一个映射Map不能包含重复的键；每个键最多只能映射到一个值 , 每个值可以被多个键所映射。
 

• • Map 基本操作:

   1,添加  V put(K key, V value)  将指定的值与此映射中的指定键关联
       void putAll(Map<? extends K,? extends V> m) 从指定映射中将所有映射关系复制到此映射中
    
         

   2,判断/查询 boolean equals(Object o) 比较指定的对象与此映射是否相等。
        boolean isEmpty()   如果此映射未包含键-值映射关系，则返回 true。
        boolean containsKey(Object key)      判断此映射是否包含指定键的映射关系，包含则返回 true。
        boolean containsValue(Object value)   如果此映射将一个或多个键映射到指定值，则返回 true。
       

         
   3,删除 clear()  从此映射中移除所有映射关系
      V remove(Object key)  从此映射中移除指定一个键(如果存在)的映射关系 , 返回以前与 key 关联的值,如果不存在key的映射关系返回null
                                           如果此映射允许 null 值，则返回 null 值并不一定 表示该映射不包含该键的映射关系；也可能该映射将该键显示地映射到null。
     
   4,修改
   5,获取 

       V get(Object key)    返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。
      int size() 返回此映射中的键-值映射关系数。
      int hashCode()    返回此映射的哈希码值。

      Collection<V> values() 返回此映射中包含的值的Collection 集合。
      Set<K> keySet() 返回此映射中包含的键的 Set 集合
      Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的 Set 集合

 

 

•  Map 的常见子类
    ├ Hashtable :底层数据结构为哈希表,不可以存入null键null值 .该集合线程同步, JDK1.0效率低
    ├ HashMap : 底层数据结构是哈希表, 允许使用 null键和null值 该集合线程不同步 JDK1.2效率高
    ├      （除了非同步和允许使用 null 键值之外，HashMap 类与 Hashtable 大致相同。）
    ├      HashMap<K,V> 继承了 AbstractMap<K,V>抽象类 此抽象类提供Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作。
    ├      Hashtable<K,V> 继承了 Dictionary<K,V> 抽象类 Dictionary 类是任何可将键映射到相应值的类（如Hashtable）的抽象父类
    ├      HashMap 的内部实现是采用的是hash表这种数据结构。
    ├      hash表是根据关键码值(Key value)而直接进行访问的数据结构。
    ├      它通过把关键码值通过hash映射函数映射到表中一个位置来访问记录，以加快查找的速度
    ├      hash表就是一个数组与链表的集合。集成了数组遍历快和链表方便插入删除的优点。
    └ TreeMap  :底层数据结构为二叉树,线程不同步.可以用于给Map集合中的键进行排序
           跟 Set 集合很像 ,Set底层使用了Map集合
           V get(Object key)    返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回 null。
           Object clone()  返回此 TreeMap 实例的浅表副本。
           Comparator<? super K> comparator()     返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
           Map.Entry<K,V> firstEntry()    返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
           K firstKey() 返回此映射中当前第一个（最低）键。
           Map.Entry<K,V> floorEntry(K key) 返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。
           K floorKey(K key)  返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
    
• Map 集合的取出方式
     ├ Set<K> keySet()  :将map中所有的键存入到Set集合 因为Set具备迭代器
     ├     通过迭代方式取出所有的键,再根据map 集合的get方法 获取每一个键对应的值 具体过程如下例
     └ Set<Map.Entry<K,V>> entrySet() : 将map集合中的映射关系存入到set集合中,而这个关系的数据类型就是 Map.Entry
             接着用其getKey和getValue方法分别将该关系中的键和值取出

             Map.Entry 中Entry也是一个接口,映射项（键-值对）。 他是Map接口中的内部接口,为什么要将其定义在Map集合内部?
              因为现有集合才有关系,Eentry才能访问map中的元素

             Entry 接口是Map 的内部接口:

       public interface Map<K,V>
       { 
         public static interface Entry<K,V>
         {
          public abstract V getKeySet();
          public abstract V getValue();
              ... ...
         }
              ... ...
       }

     
   Map.Entry<K,V> 在 HashMap 内部类实现:

      public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
      {  
        static class Entry<K,V> implements Map.Entry<K,V> 
        { 
              final K key;  
              V value;  
              Entry<K,V> next; ///Entry类型内部有一个自己类型的引用，指向下一个Entry  
               final int hash; 
           Entry(int h, K k, V v, Entry<K,V> n) {
              value = v;
              next = n;
              key = k;
              hash = h;
             }

             public final K getKey() {
              return key;
             }

             public final V getValue() {
              return value;
             }

             public final V setValue(V newValue) {
             V oldValue = value;
              value = newValue;
              return oldValue;
             }
             ... ...
        }
       ... ...
        
      }

 

             HashMap 示例:

     import java.util.*;

     public class MapDemo
      {
       public static void main(String[] args)
       {
           Map<String,String> m= new HashMap<String,String>();
         //增    添加元素时,如果出现添加时相同的键,则在后添加的值会覆盖原键对应的值,put方法会返回被覆盖的值
          m.put("01","abc1");
          m.put("01","ab1");//添加同键不同值
          m.put("02","abc2");
          m.put("03","abc5");
          m.put("04","abc3");
          m.put("05","abc6");
          m.put("06","abc4");
          m.put(null,"a");
         //删
          m.remove("04");//若存在返回对应的值,若不存在返回null
          //m.clear();
          syso("del04?:"+m.get("04"));//null 不存在键返回null 存在键不存在映射值 也返回null
         //改
          syso("get01"+m.get("01"));//ab1 后添加的键将前面相同的键的值覆盖
         //查  
          syso("containskey:03?:"+m.containsKey("03"));//true
          syso("containskey:00?:"+m.containsKey("00"));//false
          syso("containsvalue:abc6?:"+m.containsValue("abc6"));//true
         //取
           syso("get09:"+m.get("09"));//null, 可通过get方法的返回值来判断一个键是否存在.通过返回null来判断
           syso("get null:"+m.get(null));//null 
           m.put(null,"a");
           syso("get null:"+m.get(null));//a  null键无映射值返回null null键有映射值返回该值
           m.put("08",null);
           syso("put08:"+m.get("08"));//null  此映射不包含该键的映射关系，则返回 null。
           Collection<String> cl=m.values();
           syso(cl);//结果:[null, abc6, abc4, abc1, abc2, abc5]
           syso(m);//结果:{08=null, 05=abc6, 06=abc4, 01=abc1, 02=abc2, 03=abc5}
           //获取集合中所有的值
           
           //方式一keySet
           Set<String> k = m.keySet(); //1--先用keySet方法获取map集合所有键的 Set集合
           Iterator<String> it = k.iterator(); //2--获取Set 集合的迭代器
           while(it.hasNext())
           {
            String key = it.next();//3--获取键 
            String value = m.get(key);//4--获取值
            syso("key:"+key+"\t value:"+value);
            /*结果为:
            key:null value:a
            key:08 value:null
            key:05 value:abc6
            key:06 value:abc4
            key:01 value:ab1
            key:02 value:abc2
            key:03 value:abc5
            */

           }


           //方式二 entrySet
           Set<Map.Entry<String,String>> st = m.entrySet();//1--将,map集合中的映射关系(Map.Entry关系)取出存入Set集合中
           Iterator<Map.Entry<String,String>> it1 = st.iterator();
           while(it1.hasNext())
          {   //2--对关系 用getKey()和getValue()方法分别取出键和值
            Map.Entry<String,String> me = it1.next();
            String key = me.getKey();
            String value = me.getValue();
            syso(key+"\t"+value);
            /*结果为:
            null a
            08 null
            05 abc6
            06 abc4
            01 ab1
            02 abc2
            03 abc5
            */
          }

        }
         public static void syso(Object o)
         {
          System.out.println(o);  
         }
       } 

 

 

• Collections 类

 

Collections是操作集合的工具类

 Collections的主要操作有：
1. static <T> int  binarySearch(List<? extends Comparable<? super T>> list, T key) 
  该方法是寻找T对象在List中匹配元素的位置。要求List集合中必须全部都是T对象，T对象必须实现Comparable接口，
  如果查找成功返回对象在List中的位置，否则返回负数。该方法执行前首先要对List对象中的元素排序，该方法还有一
  个重载方法是：
 static <T> int  binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 
  该方法也是查找T对象在List中的位置，List集合中必须全部是T元素，但是不要去T必须实现Comparable接口，而是要
  求传入一个比较器。

2. sort(List<T> list)
   对List中的元素按照自然排序。要按照用户自定义方式进行排序，必须实现Comparator接口。
 sort (List<T> list, Comparator<? super T> c)
   根据指定比较器产生的顺序对指定列表进行排序。
3. swap(List<?> list, int i, int j)
   在指定列表的指定位置处交换元素。
4. reverse(List<?> list)反转指定列表中元素的顺序。

 

• Collection Collections 区别

Collection 是集合架构的顶层接口

Collections 是工具类

 

• 三种基本遍历方法:

  1,普通for遍历
   for (初始条件;结束条件 ;循环控制 )

  2,增强型for遍历
   for(元素类型 元素变量: 集合/数组)

   2.1--遍历数组
   int [] arr ={1,3,5,6};
   for(int i:arr){...}

   int[][] arrs = {{1,4,7},{2,6,7,4}};
   for(int[] r : arrs)
   {
    for(int e:r)
    {
     ...
    }
     ...
   }
   2.2---遍历集合
   
   增强型for循环优点主要表现在集合的遍历上,利用了集合的泛型特性
   局限性:
    不能利用数组或有序集合的索引的进行判断操作元素,
    不能对集合本身进行操作
    底层原理还是迭代器 如:
    ArrayList<Integer> list = new ArrayList<Integer>(); 
     for (Integer i : list) { ... }
     实际是以下for的简化写法
    ArrayList<Integer> list = new ArrayList<Integer>();
     for (Iterator<Integer>  i = list.iterator(); i.hasNext();) {
       Integer value=i.next();
     }
   
 

 3,迭代遍历
   迭代法是集合提供的一种遍历方法
   Set<String> set = new HashSet<String>();
   Iterator<String> it = set.iterator();
   while (it.hasNext())
   { 
    String str = it.next(); 
    System.out.println(str);
   }

 

• 关于数组 集合的总结

  已经学完了集合和数组,下面对数据结构:  数组结构 链表结构 哈希表结构 二叉树结构
   1)数组是一直线性序列,只能存放一种类型元素,可以存放基本类型数据或引用类型数据 ,

      改查快增删慢,当数组创建完毕,其长度就固定,在生命周期内不会改变,  是顺序的存储结构

   2)集合容器List Set Map 在处理对象的时候好像没有特定类型,容器可以将所有类看成 Object类
   创建容器就可以把所有类型的对象存进去,但取出时需要对其进行强转,由于强转会带来全性问题
    故引入了泛型概念,对存入元素进行类型限定,这样集合元素被限定为某一种类型或某类型及其子类或父类或限定为某几类.
    集合容器大小是动态的,可以随着元素的添加动态开辟需要的大小,集合底层有四大基本结构,有顺序存储结构即数组结构
    显然采用数组结构在改查方面效率会高很多,
    有Set集合能实现自动按自然顺序排序,还能确保元素的唯一性
    效率
    数组的缺点是对数组的操作功能少,Arrays 工具类 提供了对数组进行操作的基本方法 fill() sort() equals() binarySearch()
    还可以将数组转换成集合来处理,而集合也可以转换成数组
    对数据的基本操作:增删改查