Java编程思想读书笔记－3（第9章-1容器的使用及其工作原理）

一.    容器简介 1.    容器的分类 1.1.    Collection：一组各自独立的元素，即其内的每个位置仅持有一个元素。 1)    List：以元素安插的次序来放置元素，不会重新排列。 2)    Set：不接爱重复元素，它会使用自己内部的一个排列机制 1.2.    Map：一群成对的key-value对象，即所持有的是key-value pairs。 Map中不能有重复的key，它拥有自己的内部排列机制。 2.    容器中的元素类型都为Object。从容器取得元素时，必须把它转换成原来的类型。 二.    容器的详细介绍 1．    Collection Collection不提供get()方法。如果要遍历Collectin中的元素，就必须用Iterator。 1.1.    List 1.1.1    List（interface）：List为Collectin加入了一些函数，使它可以在List内进行安插和移除动作。List会产生ListIterator，通过它可以从两个方向来对List进行走访，也可以在List之内进行元素的安插和移除。 1.1.2    ArrayList：可以快速随机访问；但当元素的安插或移除发生在List中央位置时，效率很差。不宜用ArrayList来进行安插和移除操作。 1.1.3    LinkedList：与ArrayList相反，适合用来进行安插和移除，但随机访问的速度较慢。此外，可以通过LinkedList来实现stack、queue、deque。 1)    LinkedList中的addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()函数未定义于任何一个interface或base　class中，所以只能用于LinkedList中。 1.2.    Set 1.2.1    Set（interface）：Set具有和Collection一模一样的interface（区别：List加入了自己的函数），所以Set就是一个Collection，只不过其行为不同罢了。加至Set内的每个元素都必须独一无二，不与其他元素重复；Set不允许持有重复元素，每个元素都必须定义equals()以判断所谓的独一性。 1.2.2    HashSet：一种把查找时间看得很重要的Sets。所有元素都必须定义hashCode()。 1.2.3    TreeSet：底层结构为tree的一种有序的Set。 2．    Map 2.1.    Map：维护key-value的关联性，使你可以使用key来查找value。 1)    KeySet()函数和values()函数 import java.util.*; public class ExplicitStatic{         public static void printKeys(java/util/Map.java.html" target="_blank">Map m){         java/lang/System.java.html" target="_blank">System.out.print("Size = " + m.size()); java/lang/System.java.html" target="_blank">System.out.println(" , Keys: " + m.keySet());      }        public static void printValues(java/util/Map.java.html" target="_blank">Map m){         java/lang/System.java.html" target="_blank">System.out.println("Values: " + m.values());      }     public static void test(java/util/Map.java.html" target="_blank">Map m){         for( int i=1; i<10; i++)             m.put("km" + i, "m" + i);         printKeys(m);         printValues(m);         java/lang/System.java.html" target="_blank">System.out.println("km1 - " + m.get("km1"));         java/util/Set.java.html" target="_blank">Set keys = m.keySet();  //（1）         java/util/Collection.java.html" target="_blank">Collection values = m.values();  //（2）         keys.remove("km2");  //（3）         values.remove("m1");  //（4）         java/lang/System.java.html" target="_blank">System.out.println("km1 - " + m.get("km1"));         printKeys(m);         printValues(m);     }     public static void main(java/lang/String.java.html" target="_blank">String[] args){         java/lang/System.java.html" target="_blank">System.out.println("Testing HashMap");         test(new java/util/HashMap.java.html" target="_blank">HashMap());     } } 结果为： Testing HashMap Size = 9 , Keys: [km5, km4, km3, km2, km1, km9, km8, km7, km6] Values: [m5, m4, m3, m2, m1, m9, m8, m7, m6] km1 - m1  //执行（3）（4）之前 km1 - null Size = 7 , Keys: [km5, km4, km3, km9, km8, km7, km6]  //（5） Values: [m5, m4, m3, m9, m8, m7, m6]  //（6） 在（1）（2）处代码分别得到了Map中的keys和values。从执行（3）（4）前后的代码可知，对通过keySet()和values()函数取得的值进行修改会反映到Map本身。 （3）中删除的是值为“km2”的key，（4）删除的是值为“m1”的value，且它们是同一个key-value pair，但结果（5）（6）表明，Map中删除的是两个key-pair。从而可知，只要删除了Map中的key或value中的一个，那么整个key-value　pair就会被删除。      2.2.    HashMap：可在常量时间内安插元素，或找出一组key-value　pair。通过其构造函数，使用者可以调整效能表现，因为它允许你设定capacity（容量）和loadfactor（负载因子）。 2.3.    TreeMap：当你检视其中的key或key-value　pairs时，会以排序形式出现，让你得到以排序形式得到结果。TreeMap是惟一具有subMap()的一个Map，这个函数让你得以返回tree中的部分组成。 三.    HashMap的工作原理 1．    如何实现一个Map 1.1    与Map相关的知识 1.1.1    Map.Entry接口 一个实现了Map.Entry接口的类代表的是一个Map中的条目（一个key-value　pair）。所以一个Map中必须要有一个实现了Map.Entry接口的类，并用这个类来存放Map中的key-value　pair。 1.1.2    public abstract Set entrySet()函数 1)    entrySet()函数返回一个Set，并且Set中的每一个元素都是一个Map.Entry类型的对象。在entrySet()函数中要把Map中所有的key-value　pair以Map.Entry封装后存入Set中的。 2)    当对Map进行修改操作后，entrySet()函数都会被调用。所以对Map的修改也会产生对这个Set的修改。 3)    当用这个Set的iterator进行操作时，不能进行add和addAll的操作。 1.2    实现一个简单的Map的实例 import java.util.*; /**  * MPair类实现了Map.Entry  */ class MPair     implements java/util/Map.java.html" target="_blank">Map.Entry, java/lang/Comparable.java.html" target="_blank">Comparable{     java/lang/Object.java.html" target="_blank">Object key, value; //key和value分别用来存放Map中的key和value     MPair(java/lang/Object.java.html" target="_blank">Object k, java/lang/Object.java.html" target="_blank">Object v){         key = k;         value = v; } //下面方法实现了Map.Entry接口中的方法     public java/lang/Object.java.html" target="_blank">Object getKey() { return key; }     public java/lang/Object.java.html" target="_blank">Object getValue() { return value; }     public java/lang/Object.java.html" target="_blank">Object setValue(java/lang/Object.java.html" target="_blank">Object v){         java/lang/Object.java.html" target="_blank">Object result = value;         value = v;         return result; } //下面方法实现了Comparable接口中的方法     public boolean equals(java/lang/Object.java.html" target="_blank">Object o){         return key.equals(((MPair)o).key);     }     public int compareTo(java/lang/Object.java.html" target="_blank">Object rv){         return ((java/lang/Comparable.java.html" target="_blank">Comparable)key).compareTo(((MPair)rv).key);     } } class SlowMap extends java/util/AbstractMap.java.html" target="_blank">AbstractMap{     private java/util/ArrayList.java.html" target="_blank">ArrayList         keys = new java/util/ArrayList.java.html" target="_blank">ArrayList(),         values = new java/util/ArrayList.java.html" target="_blank">ArrayList();     public java/lang/Object.java.html" target="_blank">Object put(java/lang/Object.java.html" target="_blank">Object key, java/lang/Object.java.html" target="_blank">Object value){         java/lang/Object.java.html" target="_blank">Object result = get(key);         if(!keys.contains(key)){ //（1）             keys.add(key);             values.add(value);         }         else             values.set(keys.indexOf(key), value);         return result;     }     public java/lang/Object.java.html" target="_blank">Object get(java/lang/Object.java.html" target="_blank">Object key){         if(!keys.contains(key)){             return null;         }         else             return values.get(keys.indexOf(key)); } //用Mpair封装Map中的key-value　pair并存入Set中     public java/util/Set.java.html" target="_blank">Set entrySet(){         java/util/Set.java.html" target="_blank">Set entries = new java/util/HashSet.java.html" target="_blank">HashSet();         java/util/Iterator.java.html" target="_blank">Iterator             ki = keys.iterator(),             vi = values.iterator();         while(ki.hasNext())             entries.add(new MPair(ki.next(), vi.next()));         return entries;     } } public class ExplicitStatic{             public static void main(java/lang/String.java.html" target="_blank">String[] args){         SlowMap m = new SlowMap();         for( int i=1; i<10; i++)             m.put("km" + i, "m" + i);         java/lang/System.java.html" target="_blank">System.out.println(m);             } }     在上面代码的（1）处，我们要从ArrayList中查找出是否具有key值，而这个查找过程线性查找，且key不具任何顺序，所以速度会很慢。 2．    与HashMap相关的几个函数 1)    hashCode()函数 Object.hashCode()函数会为对象产生hash code。如果一个类没有实现hashCode()函数，那么在缺省情况下将返回它的对象的内存地址。 2)    equals()函数 Object.equals()在比较两个对象时，比较的是两个对象的内存地址。 3．    HashMap的工作原理 3.1    用array来表现key的信息。每个key的hashCode()函数会为key产生一个hash　code，而key的hash 　code作为array的索引。如假设有一个名为bucket的arrsy，姥一个hash　code为2的key就被索引到bucket[2]，key所对应的值也在bucket[2]中。 3.1    由于array中存放的是value值，而HashMap的元素个数可以是无限的，所以array中的元素指向的不是某个key的value，而是指向具有相同的hash　code的key的value值（也就是说指向的是一串values值）。如假设array被定义为LinkedList []bucket = new LinkedList[10]，那么bucket[2]中存放的是所有hash　code值为2的key的value。