GVKun编程网logo

Java之Collection/Map

9

本文将带您了解关于Java之Collection/Map的新内容，另外，我们还将为您提供关于JavaCollectionFramework-Collection接口的具体详解、JavaCollecti

本文将带您了解关于Java之Collection/Map的新内容，另外，我们还将为您提供关于Java Collection Framework -Collection接口的具体详解、Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理、java Collection-Map 之 TreeMap、Java Collection.Map的实用信息。

本文目录一览：

Java之Collection/Map

Java之Collection/Map

 

Java中容器分两类，一种是单值的Collection，一种是储存键-值对的Map

 

Collection

又分两种，Set和List，区别在于Set是不可重复的，而List是可重复的

Set

常用有两种：HashSet和TreeSet，其内部实现是一个Map，它的元素就相当于Map中的Key，而Value是一个Object常量

 


        
        

         
         
 
        
        private transient HashMap<E,Object> map;
       
       

        
        

 
       
       

        
        

         
         
 
        
        ivate static final Object PRESENT = new Object();
 
       
       

        
        

p
r
public HashSet() {
       
       

        
        

         
         
 
        
        p<E,Object>();
}
       
       

        
        

     map = new HashM
       
       

        
        

         
         
 
        
        a



 


        
        

         
         
 
        
        private transient NavigableMap<E,Object> m;
       
       

        
        

 
       
       

        
        

         
         
 
        
        ivate static final Object PRESENT = new Object();
 
       
       

        
        

p
r
public TreeSet() {
       
       

        
        

         
         
 
        
        ap<E,Object>());
}
       
       

        
        

     this ( new Tree
       
       

        
        

         
         
 
        
        M


所有对Set的操作都被最终转嫁为对Map的操作，具体细节在下面Map中讲述

 

List

对Collection接口进行了简单的扩充，你可以将任何对象放到放到一个List容器中，并在需要时从中取出。

常用的有ArrayList和LinkedList，都是有顺序，可重复的集合类型

 

ArrayList：顾名思义，数据列表，其实就是封装了一个数组，因此它的访问速度极快



        
        

         
         
 
        
        private transient Object[] elementData;
       
       

        
        

 
       
       

        
        

         
         
 
        
        ivate int size;
       
       

        
        

p
r


然后封装了一些对数组的常用操作如插入、删除等。

 

说到ArrayList不得不提下Arrays类和数组[]

 

ArrayList可以储存不同类型的对象（虽然一般不推荐这样做），而数组只能是同一类型

ArrayList可以动态增加长度，但效率不高，而数组只能是固定长度，却十分高效。每当执行add/insert等添加元素的方法，都会先检查数组长度是否足够，如果是，它就会以当前容量的3/2倍+1来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。

ArrayList提供常用方法，add/get/indexOf/remove等，而相应的Arrays没有提供add和remove方法，查询元素索引要先sort再binarySearch

ArrayList排序需外部方法Collections.sort(..),数组排序则使用Arrays.sort(..)，二者都可以使用自然顺序（实现Comparable）或用Comparator指定

 

LinkedList：很显然的是链表，内部实现是带头结点的双向链表，适合于在链表中间需要频繁进行插入和删除操作

 

 


        
        

         
         
 
        
        private transient Entry<E> header = new Entry<E>( null , null , null );
       
       

        
        

 
private transient int size = 0 ;
 
private static class Entry<E> {
 
       
       

        
        

     E element;
     Entry<E> next;
     Entry<E> previous;
 
//..
       
       

        
        

}


 

 

Map

是一种把键和值对象进行关联的容器，类比Collection，可以这样说：Collection对象中某个值的ID是它在容器中的索引值，而在Map中，某个值的ID是它对应的键。这样我们使用Map时就不用局限于int型的索引值，可以用任何类型的对象作索引。正是由于Key的索引特性，Map中不允许有同值的Key存在（前文讲到Set内部实现是Map中的Key的集合，所以Set的元素不能重复）。当然，Value是可以重复的，甚至可以是同一个Reference。Map在处理相同的Key时，将新值存入，旧值被替换并返回。

 

HashMap：采用Hash算法，以便快速查找某个元素。

将键的哈希值作为内存索引依据，内部实现是一个适当长度的链式数组，由Key的Hash值对应数组下标，再间接对应内存，是一种比较高效的存取方式。Key的hashCode()相同的情况下，放在同一个单项链表结构中。

一个HashMap中Key的类型应该重写hashCode()方法，保证在两个对象equals为true时返回相同的值，否则在重复性检查时会直接被当做不同的键，造成不可预期的后果。

Hash容器中判断重复的方式：

先比较hash(key.hashCode())是否相同，hash(int)是一个内部算法，具体细节不作讨论

　　不同，则不重复

　　相同，则

　　　　比较两个Key是否是同一引用

　　　　　　是，则重复

　　　　　　不是，再调用equals方法

　　　　　　　　返回true则重复

　　　　　　　　返回false则不重复

TreeMap：采用树型储存结构按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。

内部实现是一颗二叉排序树，其中序遍历结果为递增序列。所以要求他的Key必须是Comparable或者创建TreeMap的时候指定Comparator。

当Key实现Comparable<E>接口时，必须实现comparaTo(E e)方法，当使用外部比较器（Comparator<T>）时，需实现Comparator<T>的compare(T t1, T t2)方法

 

相关知识

 

泛型(Generic)

泛型允许Coding的时候可以定义一些可变的类型，但必须在使用前进行声明具体是哪种类型

 


        
        

         
         
 
        
        class testGeneric<T> {
       
       

        
        

     T t;
       
       

        
        

         
         
 
        
        eneric(T t) {
         
       
       

        
        

     test
Gthis .t = t;
     }
}
 
       
       

        
        

         
         
 
        
        eric<String>
       
       

        
        

class test {
     testGe
       
       

        
        

         
         
 
        
        n tgs = new testGeneric( "Hi,Gineric!" );
       
       

        
        


       
       

        
        

         
         
 
        
             testGeneric<Integer> tgi = new testGeneric( 100 ); //AutoBoxing
       
       

        
        

     {
         System.out.println(tgs.t); //Output:Hi,Gineric!
       
       

        
        

         
         
 
        
           }
}
       
       

        
        

         System.out.println(tgi.t); //AutoUnBoxing&Output:100


需要注意Java 泛型的类型参数之实际类型在编译时会被消除（upcast to Object），所以无法在运行时得知其类型参数的类型。Java 编译器在编译泛型时会自动加入类型转换的编码，故运行速度不会因为使用泛型而加快。

 

迭代器(Iterator)

提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。

对于遍历一个容器中所有的元素，Iterator模式是首选的方式

Collection定义了Iterator<E> iterator()方法，子类都各自实现了该方法，我们直接调用即可

Map中虽没有定义，我们可以利用map.entrySet()的iterator()方法

 

 


        
        

         
         
 
        
        Iterator i = someMap.entrySet().iterator();
       
       

        
        

while (i.hasNext()) {
       
       

        
        

         
         
 
        
         (Map.Entry) i.next();
     Object key = i.g
       
       

        
        

     Map.Entry entry 
=etKey();
     Object value = i.getValue();
     //something TODO
       
       

        
        

}


或者转换为Collection(Set)用增强For循环

 

 


        
        

         
         
 
        
        Set<Map.Entry> entrySet = someMap.entrySet();
       
       

        
        

for (Map.Entry entry : entrySet){
       
       

        
        

         
         
 
        
             Object value = entry.getValu
       
       

        
        

     Object key = entry.getKey();
e();
     //something TODO
       
       

        
        

}


 

ListIterator继承了Iterator，提供了对List的双向遍历的方法。

需要注意的是，调用Iterator的remove方法，删除的是最后一次调用next()（or previous(),if possible）所返回的元素

如果进行迭代时用调用此方法之外的其他方式修改了该迭代器所指向的 collection，则迭代器的行为是不确定的。

也就是说，调用Iterator时，最好不要调用Collection的add/remove等方法

另：容器类的toString()方法也是通过调用iterator()方法来实现遍历

　　对集合使用增强的for循环也是隐式地调用iterator()方法

 

还有Stack、Queue等结构，操作简单，不作赘述

Java Collection Framework -Collection接口的具体详解

Java Collection Framework -Collection接口的具体详解


一、要点

  • collection 接口

  • Collection 接口的默认实现：AbstractCollection

  • Optional operations(可选方法)

二、Collection 接口

1、JDK 对 Collection 接口的描述

　　Collection 接口是 Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection(List,Queue) 允许有重复的元素，而另一些(Set)则不允许。一些 collection (List,Queue)是有序的，而另一些(Set)则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List）实现，这些子接口继承自Collection 接口。此接口通常用来传递 collection（多态），并在需要最大普遍性的地方操作这些 collection。

立即学习“Java免费学习笔记（深入）”；

　　所有通用的 Collection 实现类（通常通过它的一个子接口间接实现 Collection）应该提供 两个“标准”构造方法： 一个是 void（无参数）构造方法，用于创建空 collection；另一个是带有 Collection 类型单参数的构造方法，用于创建一个具有与其参数相同元素新的 collection。实际上，后者允许用户复制任何 collection，以生成所需实现类型的一个等效 collection。尽管无法强制执行此约定（因为接口不能包含构造方法），但是 Java 平台库中所有通用的 Collection 实现都遵从它。

　　此接口中包含的“破坏性”方法，是指可修改其所操作的 collection 的那些方法，如果此 collection 不支持该操作，则指定这些方法抛出 UnsupportedOperationException(可选操作)。

　　Collections Framework 接口中的很多方法是根据 equals 方法定义的。

　　Collections Framework 中的各个容器均是非线程安全的。  
　　
　　Collection 接口的定义如下：

public interface Collection<E> extends Iterable<E> { ... }
登录后复制

　　　　　　　　　　　　Java Collection Framework.png-155.6kB

2、行为

　　 java.util.Collection 接口是描述 Set 和 List 集合类型的根接口，下面给出了Collection 的所有行为(不包括从Object 继承而来的方法),因此它们也刻画了 Set 或 List 执行的所有行为(List 还有额外的功能)。Collection 的行为分类和详细列表如下 ：

　　　　　Collection行为分类.png-29.5kB
　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　 表1. Collection 的操作

FunctionIntroductionNote
boolean add(T)将指定元素添加到集合中，若未将该元素添加到容器，返回 false可选操作
boolean addAll(Collection)添加参数中的所有元素，只要添加进任意元素则返回 true可选操作
Iterator iterator( )遍历容器中的元素（统一的访问、遍历方法，对外屏蔽了不同容器的差异性，迭代器模式）依赖于具体实现
boolean remove(Object)向容器移除指定元素，若移除动作发生，则返回 true（若有重复对象，一次只删除其中一个）可选操作
boolean removeAll(Collection)向容器移除参数中所有元素，若有移除动作发生，则返回 true可选操作
Boolean retainAll(Collection)只保存参数中的元素，只要Collection 发生改变，则返回 true可选操作
void clear()移除容器中所有元素可选操作
boolean contains(T)若容器持有该元素，返回 true依赖于equals()
Boolean containsAll(Collection)若容器持有参数中的所有元素，返回 true依赖于equals()
object[] toArray()返回一个包含该容器所有元素的 Object 型数组Array与Collection之间的桥梁，在 AbstractCollection 中提供默认实现，子类可以对它重写
T[] toArray(T[] a)返回一个包含该容器所有元素的 Object 型数组，且返回结果的运行时类型与参数数组 a 相同,而不单纯是objectArray与Collection之间的桥梁，在 AbstractCollection 中提供默认实现，子类可以对它重写
int size()返回容器中元素数目依赖于具体实现
boolean isEmpty()容器为空，则返回 true依赖于size()

　　 注意到，其中不包含随机访问所选择的元素 get() 方法，因为 Collection 包含 Set，而 Set 是自己维护顺序的。因此，若想访问、遍历 Collection 中的元素，则必须使用迭代器; 另外，这些方法的默认实现（AbstractCollection）均直接或间接使用了迭代器。

三、Collection 接口的默认实现：AbstractCollection

1、JDK 对 AbstractCollection 抽象类的描述

　　 此抽象类提供 Collection 接口的骨干实现，以最大限度地减少实现此接口所需的工作。 要实现一个不可修改的 collection，编程人员只需扩展此类，并提供 iterator 和 size 方法的实现。（iterator 方法返回的迭代器必须实现 hasNext 和 next。）; 要实现可修改的 collection，编程人员必须另外重写此类的 add 方法（否则，会抛出 UnsupportedOperationException），iterator 方法返回的迭代器还必须另外实现其 remove 方法（AbstractCollection 的移除方法间接调用迭代器的移除方法）。按照 Collection 接口规范中的建议，编程人员通常应提供一个 void （无参数）和 Collection 构造方法。

　　　　Iterator.png-6.6kB

　　AbstractCollection 抽象类定义如下：

public abstract class AbstractCollection<E> implements Collection<E> { ... }
登录后复制

2、行为(对上述 Collection 接口中方法的实现情况)

　　下面给出了抽象类 AbstractCollection 对 Collection 接口的实现情况：

    public boolean add(E e) {   
     throw new UnsupportedOperationException();
    }  
     public boolean addAll(Collection<? extends E> c) {  
      boolean modified = false;
    Iterator<? extends E> e = c.iterator();   
     while (e.hasNext()) {     
       if (add(e.next()))                
         // 调用了上面定义的 add 方法
        modified = true;
    }    return modified;
    }    public abstract Iterator<E> iterator();               
    //未提供具体实现，将实现延迟到具体容器


    public boolean remove(Object o) {
    Iterator<E> e = iterator();    
    if (o==null) {       
     while (e.hasNext()) {       
      if (e.next()==null) {
            e.remove();                 
            //内部使用了迭代器的 remove 方法，故具体容器的迭代器实现密切相关
            return true;
        }
        }
    } else {        
    while (e.hasNext()) {      
      if (o.equals(e.next())) {
            e.remove();           
             return true;
        }
        }
    }    return false;
    }    public boolean removeAll(Collection<?> c) {  
      boolean modified = false;
    Iterator<?> e = iterator();    
    while (e.hasNext()) {     
       if (c.contains(e.next())) {
        e.remove();                       
        //内部使用了迭代器的 remove 方法，故具体容器的迭代器实现密切相关
        modified = true;
        }
    }    return modified;
    }    public boolean retainAll(Collection<?> c) {    
    boolean modified = false;
    Iterator<E> e = iterator();   
     while (e.hasNext()) {        
    if (!c.contains(e.next())) {
        e.remove();                       
        //内部使用了迭代器的 remove 方法，故具体容器的迭代器实现密切相关
        modified = true;
        }
    }    return modified;
    }    public void clear() {
    Iterator<E> e = iterator();    
    while (e.hasNext()) {
        e.next();
        e.remove();                       
        //内部使用了迭代器的 remove 方法，故具体容器的迭代器实现密切相关
    }
    }    public boolean contains(Object o) {
    Iterator<E> e = iterator();    
    if (o==null) {        
    while (e.hasNext())        
    if (e.next()==null)            
    return true;
    } else {        while (e.hasNext())        
    if (o.equals(e.next()))                 
    //内部调用了的 equals方法，故与 equals 方法实现密切相关
            return true;
    }    return false;
    }    public boolean containsAll(Collection<?> c) {
    Iterator<?> e = c.iterator();    
    while (e.hasNext())        
    if (!contains(e.next()))                
    //内部调用了的 contains 方法，故与 contains 方法实现密切相关
        return false;    return true;
    }    //此处省略两个 toArray 方法的实现


    public abstract int size();                   
    //未提供具体实现，将实现延迟到具体容器


    public boolean isEmpty() {    return size() == 0;                      
    //内部调用了的 size 方法，故与 size 方法实现密切相关
    }
登录后复制

　　 对以上实现进行总结 ：

  • 【增】：add, addAll 两个方法的实现是可选的，此处均默认 UnsupportedOperationException ；

  • 【查】：iterator 未提供具体实现，将实现延迟到具体容器,其对外屏蔽了不同容器的差异性，以统一的方式对容器访问、遍历 ；

  • 【删】：remove(Object)，removeAll(Collection) ，retainAll(Collection) 和 clear() 四个方法的实现均直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法 ；

  • 【查】：contains(Object o) 和 containsAll(Collection c) 两个方法的实现均直接或间接调用了元素的 equals 方法 ；

  • 【基本方法】：size 方法实现与具体容器相关， isEmpty 方法的实现均直接调用了 size 方法 ；

  • 【容器与数组转换】：分别提供与泛型 toArray 方法 和 原生 toArray 方法；

　　 从源代码中我们可以知道，几乎所有方法的实现都与迭代器相关，并且有以下特点：

  • 执行各种不同的添加和移除方法在 Collection 接口中都是可选操作，因为他们会改变容器的结构;

  • Collection 接口中的读取方法都不是可选操作 ；

四、Optional operations(可选操作)

1、简述

　　 执行各种不同的添加和移除方法在 Collection 接口中都是可选操作, 这意味着实现类并不需要为这些方法提供功能定义。

　　 这是一种很不寻常的接口定义方式。正如你所看到的那样，接口是面向对象设计中的契约，它声明 “无论你选择如何实现该接口，我保证你可以向该接口发送这些消息。”但可选操作违反这个非常基本的原则，它声明调用某些方法将不会执行有意义的行为，相反，他们会抛出异常。

　　 为什么会将方法定义为可选呢？ 因为这样做可以防止在设计中出现接口爆炸的情形。容器类库中的设计看起来总是为了描述每个主题的变体，而最终患上了令人困惑的接口过剩症。甚至这么做仍不能捕获接口的各种特例，因为总是有人会发明新的接口。“未获支持的操作” 这种方式可以实现 Java 容器类库的一个重要目标：容器应易学易用。未获支持的操作是一种特例，可以延迟到需要时实现。但是，为了让这种方式能够工作：

  1. UnsupportedOperationException 必须是一种罕见事件。即，对于大多数类而言，所有操作都应该可以工作，只有在特例(例如，通过Arrays.asList()所得到的容器)中才会有未获支持的操作。在 Java 容器类库中确实如此，因为你在 99% 的时间里使用的容器类，如 ArrayList、LinkedList、HashSet 和 HashMap,以及其他的具体实现，都支持所有操作。这种设计留下了一个“后门”，如果你想创建新的 Collection， 但是没有为 Collection 接口中的所有方法都提供有意义的定义，那么它仍旧适合现有类库。

  2. 如果一个操作是未获支持的，那么在实现接口的时候可能就会导致 UnsupportedOperationException 异常，而不是将产品程序交给客户后才出现此异常，这种情况是有道理的。毕竟，他表示编程上有错误：使用了不正确的接口实现。

    　值得注意的是，未获支持操作只有在运行时才能探测到，因此他们表示动态类型检查。

2、示例

　　 最常见的未获支持的操作，都来源于背后由固定尺寸的数据结构支持的容器。当你用 Arrays.asList() 将数组转换为 List 时，就会得到这样的容器。此外，你还可以通过使用 Collection 类中“不可修改”的方法，选择创建任何会抛出会抛出 UnsupportedOperationException 的容器。

　　 请看下面的例子：

public class Unsupported {
    static void test(String msg, List<String> list) {
        System.out.println("--- " + msg + " ---");
        Collection<String> c = list;
        Collection<String> subList = list.subList(1, 8);        
        // Copy of the sublist:
        Collection<String> c2 = new ArrayList<String>(subList);    
            
        try {
            c.retainAll(c2);
        } catch (Exception e) {
            System.out.println("retainAll(): " + e);
        }        try {
            c.removeAll(c2);
        } catch (Exception e) {
            System.out.println("removeAll(): " + e);
        }        try {
            c.clear();
        } catch (Exception e) {
            System.out.println("clear(): " + e);
        }        try {
            c.add("X");
        } catch (Exception e) {
            System.out.println("add(): " + e);
        }        try {
            c.addAll(c2);
        } catch (Exception e) {
            System.out.println("addAll(): " + e);
        }        try {
            c.remove("C");
        } catch (Exception e) {
            System.out.println("remove(): " + e);
        }        // The List.set() method modifies the value but
        // doesn’t change the size of the data structure:
        try {
            list.set(0, "X");
        } catch (Exception e) {
            System.out.println("List.set(): " + e);
        }
    }    public static void main(String[] args) {
        List<String> list = Arrays.asList("A B C D E F G H I J K L".split(" "));

        test("Modifiable Copy", new ArrayList<String>(list)); // 产生新的尺寸可调的
                                                                
                                                                
                                                               // ArrayList

        test("Arrays.asList()", list); // 产生固定尺寸的 ArrayList

        test("unmodifiableList()",
                Collections.unmodifiableList(new ArrayList<String>(list))); // 产生不可修改的列表
    }
} /* Output: 
--- Modifiable Copy --- 

--- Arrays.asList() --- 
retainAll(): java.lang.UnsupportedOperationException 
removeAll(): java.lang.UnsupportedOperationException 
clear(): java.lang.UnsupportedOperationException 
add(): java.lang.UnsupportedOperationException 
addAll(): java.lang.UnsupportedOperationException 
remove(): java.lang.UnsupportedOperationException 

--- unmodifiableList() --- 
retainAll(): java.lang.UnsupportedOperationException 
removeAll(): java.lang.UnsupportedOperationException 
clear(): java.lang.UnsupportedOperationException 
add(): java.lang.UnsupportedOperationException 
addAll(): java.lang.UnsupportedOperationException 
remove(): java.lang.UnsupportedOperationException 
List.set(): java.lang.UnsupportedOperationException
登录后复制

　　 因为 Arrays.asList() 实际上会产生一个 Arraylist ,它基于一个固定大小的数组，仅支持那些不会改变数组大小的操作。所以，任何会引起对底层数据结构的尺寸进行修改的方法(add/remove 相关)都会产生一个 UnsupportedOperationException 异常，以表示对该容器未获支持操作的调用。

　　 因此，Arrays.asList() 的真正意义在于：将其结果作为构造器参数传递给任何 Collection （或者使用 addAll 方法、Collections.addAll 静态方法），这样可以生成一个动态的容器。

　　 由以上程序片段可知， Arrays.asList() 返回固定尺寸的List，而 Collections.unmodifiableList() 产生不可修改的列表。正如输出所示，前者支持 set 操作，而后者不支持。若使用接口，那么还需要两个附加的接口，一个具有可以工作的 set 方法，另一个没有，因为附加的接口对于 Collection 的各种不可修改子类型来说是必须的。因此，可选方法可以避免 接口爆炸。

　　 针对 Arrays.asList() 这种情况给出解释：

1.首先该方法的源码为：

  public static <T> List<T> asList(T... a) {    return new ArrayList<T>(a);
    }
登录后复制

2.紧接着看上述方法所返回的由固定尺寸的数据结构支持的容器源码（部分）：

private static class ArrayList<E> extends AbstractList<E>    
implements RandomAccess, java.io.Serializable
    {
    private static final long serialVersionUID = -2764017481108945198L;   
     private final E[] a;

    ArrayList(E[] array) {            
    if (array==null)                
    throw new NullPointerException();
        a = array;
    }    public int size() {       
     return a.length;
    }    public Object[] toArray() {       
     return a.clone();
    }    public <T> T[] toArray(T[] a) {       
     int size = size();        
    if (a.length < size)        
    return Arrays.copyOf(this.a, size,
                     
                     (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);        
        if (a.length > size)
        a[size] = null;        
        return a;
    }    public E get(int index) {        
    return a[index];
    }    public E set(int index, E element) {        
    //该容器支持的操作
        E oldValue = a[index];
        a[index] = element;        
        return oldValue;
    }    public int indexOf(Object o) {        
    if (o==null) {            
    for (int i=0; i<a.length; i++)                
    if (a[i]==null)                    
    return i;
                } else {                    
                for (int i=0; i<a.length; i++)                        
                if (o.equals(a[i]))                            
                return i;
                }        
                return -1;
    }    
    public boolean contains(Object o) 
    {        
    return indexOf(o) != -1;
    }
}

....
其余代码省略
....
登录后复制

针对 Add 操作： 该容器的该行为继承于 AbstractList 抽象类，直接或间接调用 add(int index, E element) 方法，抛出 UnsupportedOperationException

// AbstractList 中的方法public boolean add(E e) {
    add(size(), e);    return true;
    }public void add(int index, E element) {    throw new UnsupportedOperationException();
}public boolean addAll(int index, Collection<? extends E> c) {    boolean modified = false;
    Iterator<? extends E> e = c.iterator();    while (e.hasNext()) {
        add(index++, e.next());
        modified = true;
    }    return modified;
}
登录后复制

针对 remove 操作： 该容器的 remove 相关行为间接继承自 AbstractCollection 类, AbstractList 类并未完全重写（只重写了 clear 操作）它们，如下：

    //AbstractList 类中方法：
    //该方法继承自 List 接口的：remove(int index) 方法，是 List 特有的方法
    public E remove(int index) {    throw new UnsupportedOperationException();
    }    //AbstractList 类重写了 AbstractCollection 的 clear 方法
     public void clear() {
        removeRange(0, size());
    }   protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();           //直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法   
        }
    }
登录后复制

　　 AbstractList 类未重写 remove(Object)，removeAll(Collection) ，retainAll(Collection) ，这些方法实际上继承自 AbstractCollection 类：

    //AbstractCollection 类中方法：
    public boolean remove(Object o) {
    Iterator<E> e = iterator();    if (o==null) {        while (e.hasNext()) {        if (e.next()==null) {
            e.remove();            return true;
        }
        }
    } else {        while (e.hasNext()) {        if (o.equals(e.next())) {
            e.remove();           //直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法   
            return true;
        }
        }
    }    return false;
    }public boolean removeAll(Collection<?> c) {    boolean modified = false;
    Iterator<?> e = iterator();    while (e.hasNext()) {        if (c.contains(e.next())) {
        e.remove();           //直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法   
        modified = true;
        }
    }    return modified;
    } public boolean retainAll(Collection<?> c) {    boolean modified = false;
    Iterator<E> e = iterator();    while (e.hasNext()) {        if (!c.contains(e.next())) {
        e.remove();            //直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法          
        modified = true;
        }
    }    return modified;
    }
登录后复制

　　 由上面两段代码可知，remove(Object)，removeAll(Collection) ，retainAll(Collection) 和 clear() 这四种操作均直接调用了具体容器的迭代器(由 iterator() 方法返回)的 remove 方法 ,我们再看 AbstractList 类提供的 Iterator 中的 remove 方法：

   private class Itr implements Iterator<E> {
    /**
     * Index of element to be returned by subsequent call to next.
     */
    int cursor = 0;    /**
     * Index of element returned by most recent call to next or
     * previous.  Reset to -1 if this element is deleted by a call
     * to remove.
     */
    int lastRet = -1;    /**
     * The modCount value that the iterator believes that the backing
     * List should have.  If this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    int expectedModCount = modCount;    
    public boolean hasNext() 
    {            
    return cursor != size();
    }    public E next() 
    {
            checkForComodification();        
            try {
        E next = get(cursor);
        lastRet = cursor++;        
        return next;
        } 
        catch (IndexOutOfBoundsException e) 
        {
        checkForComodification();        
        throw new NoSuchElementException();
        }
    }    public void remove() {        
    if (lastRet == -1)        
    throw new IllegalStateException();
            checkForComodification();        
            try {
        AbstractList.this.remove(lastRet);            
        //直接调用 AbstractList 容器的 remove(int index) 方法，抛出 UnsupportedOperationException      
        if (lastRet < cursor)
            cursor--;
        lastRet = -1;
        expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {        
        throw new ConcurrentModificationException();
        }
    }    final void checkForComodification() {        
    if (modCount != expectedModCount)        
    throw new ConcurrentModificationException();
    }
    }
登录后复制

　　  综上可知，示例中的 Arrays.asList() 部分为何会导致那样的结果。

以上就是Java Collection Framework -Collection接口的具体详解的详细内容，更多请关注php中文网其它相关文章！

Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

           

Java2的集合框架，抽其核心，主要有三种：List、Set和Map。如下图所示： 

需要注意的是，这里的 Collection、List、Set和Map都是接口（Interface），不是具体的类实现。 List lst = new ArrayList(); 这是我们平常经常使用的创建一个新的List的语句，在这里， List是接口，ArrayList才是具体的类。 


常用集合类的继承结构如下： 

Collection<--List<--Vector 

Collection<--List<--ArrayList 

Collection<--List<--LinkedList 

Collection<--Set<--HashSet 

Collection<--Set<--HashSet<--LinkedHashSet 

Collection<--Set<--SortedSet<--TreeSet 

Map<--SortedMap<--TreeMap 

Map<--HashMap 

-----------------------------------------------SB分割线------------------------------------------ 

List： 

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下 >标）来访问List中的元素，这类似于Java的数组。 


Vector： 

基于数组（Array）的List，其实就是封装了数组所不具备的一些功能方便我们使用，所以它难易避免数组的限制，同时性能也不可能超越数组。所以，在可能的情况下，我们要多运用数组。另外很重要的一点就是Vector是线程同步的(sychronized)的，这也是Vector和ArrayList 的一个的重要区别。 

ArrayList： 

同Vector一样是一个基于数组上的链表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一些，但是当运行到多线程环境中时，可需要自己在管理线程的同步问题。 

LinkedList： 

LinkedList不同于前面两种List，它不是基于数组的，所以不受数组性能的限制。 

它每一个节点（Node）都包含两方面的内容： 

1.节点本身的数据（data）； 

2.下一个节点的信息（nextNode）。 

所以当对LinkedList做添加，删除动作的时候就不用像基于数组的ArrayList一样，必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了，这是LinkedList的优势。 

List总结： 

所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]

所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]

所有的List中可以有null元素，例如[ tom,null,1 ]

基于Array的List（Vector，ArrayList）适合查询，而LinkedList 适合添加，删除操作

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


Set： 

Set是一种不包含重复的元素的无序Collection。 

HashSet： 

虽然Set同List都实现了Collection接口，但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在 HashMap的基础上来实现的，这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add（Object obj）方法的实现就可以一目了然了。 

Java代码  收藏代码

public boolean add(Object obj) {   

   return map.put(obj, PRESENT) == null;   

}   

这个也是为什么在Set中不能像在List中一样有重复的项的根本原因，因为HashMap的key是不能有重复的。 

LinkedHashSet： HashSet的一个子类，一个链表。 

TreeSet： SortedSet的子类，它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。 

Set总结： Set实现的基础是Map（HashMap）

Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象

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


Map： 

Map 是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个 Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求，你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。 


Map有两种比较常用的实现：HashMap和TreeMap。 


HashMap也用到了哈希码的算法，以便快速查找一个键， 


TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。 

键和值的关联很简单，用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。 


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


其它： 

一、几个常用类的区别 

1．ArrayList: 元素单个，效率高，多用于查询 

2．Vector: 元素单个，线程安全，多用于查询 

3．LinkedList:元素单个，多用于插入和删除 

4．HashMap: 元素成对，元素可为空 

5．HashTable: 元素成对，线程安全，元素不可为空 


二、Vector、ArrayList和LinkedList 

大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以： 

如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List； 

如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList； 

如果在多线程条件下使用，可以考虑Vector； 

如果需要频繁地删除插入，LinkedList就有了用武之地； 

如果你什么都不知道，用ArrayList没错。 


三、Collections和Arrays 

在 Java集合类框架里有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF里面功能强大的工具，但初学者往往会忽视。按JCF文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。 

想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作： 

binarySearch：折半查找。 

sort：排序，这里是一种类似于快速排序的方法，效率仍然是O(n * log n)，但却是一种稳定的排序方法。 

reverse：将线性表进行逆序操作，这个可是从前数据结构的经典考题哦！ 

rotate：以某个元素为轴心将线性表“旋转”。 

swap：交换一个线性表中两个元素的位置。 

…… 

Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下： 

unmodifiableXXX：转换成只读集合，这里XXX代表六种基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作，将会抛出UnsupportedOperationException异常。 

synchronizedXXX：转换成同步集合。 

singleton：创建一个仅有一个元素的集合，这里singleton生成的是单元素Set， 

singletonList和singletonMap分别生成单元素的List和Map。 

空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。 

这次关于Java集合类概述就到这里，下一次我们来讲解Java集合类的具体应用，如List排序、删除重复元素。





java Collection-Map 之 TreeMap

java Collection-Map 之 TreeMap

TreeMap 内部定义了一个类  static final class Entry<K,V> implements Map.Entry<K,V>，（自平衡红黑二叉树）作为数据存储节点。

put方法先判断根节点是否为空，为空则在跟节点放置数据。

不为空，（调用比较器）将put的key循环比较parent节点的key，并动态修改parent的指向。最终存入数据。

然后fixAfterInsertion 自平衡调整，过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作

红黑树的5点规定

 

1、每个节点都只能是红色或者黑色

 

2、根节点是黑色

 

3、每个叶节点（NIL节点，空节点）是黑色的。

 

4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

 

5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

 

Java Collection.Map

Java Collection.Map

 1 /**
 2  * Map集合的特点：
 3  *     将键映射到值的对象，一个映射不能包含重复的键，每个键最多只能映射到一个值。
 4  *         
 5  * Map集合的功能和概述：
 6  *     1.添加功能
 7  *         V put(K key , V vlaue) 添加元素
 8  *     2.删除功能
 9  *         clear() 移除所有键值对元素
10  *     3.判断功能
11  *         ContainsKey(Object key) 判断集合是否包含指定的键
12  *         containsValue(Object value) 判断是否包含指定的值
13  *         isEmpty() 判断集合是否为空
14  *     4.获取功能
15  *         Set<Map.Entre<K,V>> entrySet():???
16  *         V get(Object key) 根据键获取值
17  *         Set<k> keySet() 获取集合中所有键的合集
18  *         Collection<v> values() 获取集合中所有值的集合
19  *     5.长度功能
20  *         int Size()
21  *
22  *
23  *    HashMap 键是哈希表结构，可以保证键的唯一性
24  *
25  *    LinkedHashMap 
26  *        键是哈希表结构，可以保证键的唯一性 
27  *        有链表保证键的有序（取出和存储一致）
28  *    TreeMap
29  *        键是红黑树结构，可以保证键的排序和唯一性    
30  */
31 
32     //面试题
33 
34 /**
35  *     HashMap和Hashtable的区别
36  *     HashMap：线程不安全，效率高，允许null键和null值
37  *     Hashtable：线程安全，效率低，不允许null键和null值
38  * 
39  * List Set Map 等接口是否都继承自 Map 接口？
40  *     List Set 不是继承自Map接口，他们继承自Collection接口
41  *     Map本身就是一个顶层接口
42  * 
43  *     Collection 和 Collections的区别
44  *     Collection ：是单列集合的顶层接口，有子接口List和Set
45  *    Collections ：是针对集合操作的工具类，有对集合进行排序和二分查找的方法，都是静态方法
46  *        public static <T> void sort(List<T> list):排序 默认自然排序
47  *        public static <T> int binarySearch(List<?> list,T k) : 二分查找
48  *        public static <T> T max(Collection<?> coll):最大值
49  *        public static void reverse(List<?> list):反转
50  *        public static void shuffle(List<?> list): 随机置换
51  *        
52  */

 

我们今天的关于Java之Collection/Map的分享就到这里，谢谢您的阅读，如果想了解更多关于Java Collection Framework -Collection接口的具体详解、Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理、java Collection-Map 之 TreeMap、Java Collection.Map的相关信息，可以在本站进行搜索。

本文标签：

上一篇android背景选择器selector用法汇总（android背景色）

下一篇DMA和cache一致性问题（dma cache一致性）

相关文章