[关闭]
@xmruibi 2015-02-15T02:23:38.000000Z 字数 8302 阅读 688

Map Interface & AbstractMap

Data_Structure

Map
NOTE that:
1) the difference between key set, value collection and the entry set;

1. Map Interface

  1. //Map接口，K为键值，V为值对象  
  2. public interface Map<K,V> { 
  4.     int size();// elements amount in map
  5.     boolean isEmpty();// if the map is empty  
  6.     boolean containsKey(Object key); // contain key
  7.     boolean containsValue(Object value);// contain value 
  9.     V get(Object key);// return the value by key
  10.     V put(K key, V value);// insert key-value map 
  11.     V remove(Object key);// remove by key 
  12.     void clear();// clear elements in map 
  14.     Set<K> keySet(); // the Set(unified key) of Map keys 
  15.     Collection<V> values(); // the Collection(duplicated allowed) of Map values  
  17.     /********** Learn more about Entry Set in HashMap ***********/
  18.     Set<Map.Entry<K, V>> entrySet(); // return entry set
  20.     //Map internal collection, coressponded to an element in map
  21.     interface Entry<K,V> {  
  22.         K getKey();  // return key   
  23.         V getValue();// return value  
  24.         V setValue(V value);// set value  
  25.         boolean equals(Object o); 
  26.         int hashCode();  
  27.     } 
  30.     boolean equals(Object o);  
  31.     int hashCode();  
  32. }

2. AbstractMap

  1. //实现了接口Map  
  2. public abstract class AbstractMap<K,V> implements Map<K,V> {  
  3.     protected AbstractMap() { 
  4.     }  
  6.     public int size() { 
  7.         return entrySet().size();
  8.         //  get size of set 
  9.     }  
  11.     public boolean isEmpty() {  
  12.         return size() == 0; 
  13.     }  
  15.     /********** Based on Iterator **********/
  16.     // through iterator to find element with given value 
  17.     public boolean containsValue(Object value) {  
  18.         Iterator<Entry<K,V>> i = entrySet().iterator();
  20.         if (value==null) { allow value is null
  21.             while (i.hasNext()) {  
  22.                 Entry<K,V> e = i.next();  
  23.                 if (e.getValue()==null)  
  24.                     return true;  
  25.             }  
  26.         } else {  
  27.             while (i.hasNext()) {  
  28.                 Entry<K,V> e = i.next();  
  29.                 if (value.equals(e.getValue()))
  30.                     return true;  
  31.             }  
  32.         }  
  33.         return false;  
  34.     }  
  35.     // through iterator to find element with given key 
  36.     public boolean containsKey(Object key) {  
  37.         Iterator<Map.Entry<K,V>> i = entrySet().iterator(); 
  39.         if (key==null) {// allow key is null 
  40.             while (i.hasNext()) {  
  41.                 Entry<K,V> e = i.next();
  42.                 if (e.getKey()==null)  
  43.                     return true;  
  44.             }  
  45.         } else {  
  46.             while (i.hasNext()) {  
  47.                 Entry<K,V> e = i.next();  
  48.                 if (key.equals(e.getKey()))
  49.                     return true;  
  50.             }  
  51.         }  
  52.         return false;  
  53.     } 
  55.     // get Value by key 
  56.     public V get(Object key) {  
  57.         Iterator<Entry<K,V>> i = entrySet().iterator();  
  58.         if (key==null) {  
  59.             while (i.hasNext()) {  
  60.                 Entry<K,V> e = i.next();  
  61.                 if (e.getKey()==null)  
  62.                     return e.getValue();  
  63.             }  
  64.         } else {  
  65.             while (i.hasNext()) {  
  66.                 Entry<K,V> e = i.next();  
  67.                 if (key.equals(e.getKey()))  
  68.                     return e.getValue();  
  69.             }  
  70.         }  
  71.         return null;  
  72.     } 
  76.     // unimplemented element insert method  
  77.     public V put(K key, V value) {  
  78.         throw new UnsupportedOperationException();  
  79.     }  
  82.     // Remove the element by key and return its value  
  83.     public V remove(Object key) {  
  84.         Iterator<Entry<K,V>> i = entrySet().iterator();//获得迭代器  
  85.         Entry<K,V> correctEntry = null;  
  86.         if (key==null) {  
  87.             while (correctEntry==null && i.hasNext()) {//找到元素  
  88.                 Entry<K,V> e = i.next();  
  89.                 if (e.getKey()==null)  
  90.                     correctEntry = e;  
  91.             }  
  92.         } else {  
  93.             while (correctEntry==null && i.hasNext()) {//找到元素  
  94.                 Entry<K,V> e = i.next();  
  95.                 if (key.equals(e.getKey()))  
  96.                     correctEntry = e;  
  97.             }  
  98.         }  
  100.         V oldValue = null;  
  101.         if (correctEntry !=null) {  
  102.             oldValue = correctEntry.getValue();  
  103.             i.remove();//通过迭代器的remove方法删除  
  104.         }  
  105.         return oldValue;  
  106.     }  
  109.     // Batch insert by iterative put   
  110.     public void putAll(Map<? extends K, ? extends V> m) {  
  111.         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
  112.             put(e.getKey(), e.getValue());
  113.     }  
  115.     public void clear() {  
  116.         entrySet().clear();  
  117.     }  
  119.     /**
  120.     * Essentially, volatile is used to indicate that a variable's value will be modified by different threads.
  121.     * The volatile keyword in Java is poorly documented, poorly understood, and rarely used!
  122.     * The value of this variable will never be cached thread-locally: all reads and writes will go straight to "main memory";
  123.     * Access to the variable acts as though it is enclosed in a synchronized block, synchronized on itself.
  124.     *
  125.     **/
  127.     transient volatile Set<K> keySet = null; //key set  
  128.     transient volatile Collection<V> values = null; //values collection  
  130.     /****************** The following implementations are for key or value set/collection **********************/
  131.     /******************* They all need iterator with anonymous inner iterator class ********************/ 
  132.     /************* They all need iterator with anonymous inner AbstractSet/Collection class **************/ 
  133.     public Set<K> keySet() {  
  134.         if (keySet == null) { 
  135.             keySet = new AbstractSet<K>() {// Anonymous Inner Class for Set!!! 
  136.                 public Iterator<K> iterator() { 
  137.                     return new Iterator<K>() {// Anonymous Inner Class for Interator!!! 
  138.                         private Iterator<Entry<K,V>> i = entrySet().iterator();
  140.                         public boolean hasNext() {
  141.                             return i.hasNext();  
  142.                         }  
  144.                         public K next() { 
  145.                             return i.next().getKey();  
  146.                         }  
  148.                         public void remove() { 
  149.                             i.remove();  
  150.                         }  
  151.                     };  
  152.                 }  
  154.                 public int size() {
  155.                     return AbstractMap.this.size();  
  156.                 }  
  158.                 public boolean isEmpty() {
  159.                     return AbstractMap.this.isEmpty();  
  160.                 }  
  162.                 public void clear() {  
  163.                     AbstractMap.this.clear();  
  164.                 }  
  166.                 public boolean contains(Object k) { 
  167.                     return AbstractMap.this.containsKey(k); 
  168.                 }  
  169.             };  
  170.         }  
  171.         return keySet;  
  172.     }  
  174.     public Collection<V> values() {  
  175.         if (values == null) {  
  176.             values = new AbstractCollection<V>() {  
  177.                 public Iterator<V> iterator() {
  178.                     return new Iterator<V>() { 
  179.                         private Iterator<Entry<K,V>> i = entrySet().iterator();
  181.                         public boolean hasNext() {  
  182.                             return i.hasNext();  
  183.                         }  
  185.                         public V next() {  
  186.                             return i.next().getValue();  
  187.                         }  
  189.                         public void remove() {  
  190.                             i.remove();  
  191.                         }  
  192.                     };  
  193.                 }  
  195.                 public int size() {  
  196.                     return AbstractMap.this.size();  
  197.                 }  
  199.                 public boolean isEmpty() {  
  200.                     return AbstractMap.this.isEmpty();  
  201.                 }  
  203.                 public void clear() {  
  204.                     AbstractMap.this.clear();  
  205.                 }  
  207.                 public boolean contains(Object v) {  
  208.                     return AbstractMap.this.containsValue(v);  
  209.                 }  
  210.             };  
  211.         }  
  212.         return values;  
  213.     }
  216.     // Get Entry Set!  
  217.     public abstract Set<Entry<K,V>> entrySet();  
  219.     public boolean equals(Object o) {  
  220.         if (o == this)  
  221.             return true;  
  223.         if (!(o instanceof Map))  
  224.             return false;  
  225.         Map<K,V> m = (Map<K,V>) o;  
  226.         if (m.size() != size())  
  227.             return false;  
  229.         try {  
  230.             Iterator<Entry<K,V>> i = entrySet().iterator(); 
  231.             while (i.hasNext()) {  
  232.                 Entry<K,V> e = i.next();  
  233.                 K key = e.getKey();  
  234.                 V value = e.getValue();  
  235.                 if (value == null) {
  236.                     if (!(m.get(key)==null && m.containsKey(key))) // ensure the key and value are both matched 
  237.                         return false;  
  238.                 } else {  
  239.                     if (!value.equals(m.get(key)))  
  240.                         return false;  
  241.                 }  
  242.             }  
  243.         } catch (ClassCastException unused) {  
  244.             return false;  
  245.         } catch (NullPointerException unused) {  
  246.             return false;  
  247.         }  
  249.         return true;  
  250.     }  
  253.     /*** the hashcode of a collection means the sum of all hashcode of its elements ***/
  254.     public int hashCode() {  
  255.         int h = 0;  
  256.         Iterator<Entry<K,V>> i = entrySet().iterator();  
  257.         while (i.hasNext())  
  258.             h += i.next().hashCode();
  259.         return h;  
  260.     }  
  263.     public String toString() {  
  264.         Iterator<Entry<K,V>> i = entrySet().iterator();  
  265.         if (! i.hasNext())  
  266.             return "{}";  
  268.         StringBuilder sb = new StringBuilder();  
  269.         sb.append('{');  
  270.         for (;;) {  
  271.             Entry<K,V> e = i.next();  
  272.             K key = e.getKey();  
  273.             V value = e.getValue();  
  274.             sb.append(key   == this ? "(this Map)" : key);  
  275.             sb.append('=');  
  276.             sb.append(value == this ? "(this Map)" : value);  
  277.             if (! i.hasNext())  
  278.                 return sb.append('}').toString();  
  279.             sb.append(',').append(' ');  
  280.         }  
  281.     } 
  284.     //Clone new AbstractMap Object
  285.     protected Object clone() throws CloneNotSupportedException {  
  286.         AbstractMap<K,V> result = (AbstractMap<K,V>)super.clone();  
  287.         // why need to be null???
  288.         result.keySet = null;  
  289.         result.values = null;  
  290.         return result;  
  291.     } 
  293.     private static boolean eq(Object o1, Object o2) {  
  294.         return o1 == null ? o2 == null : o1.equals(o2);  
  295.     }   
  297. }

3. SimpleEntry

Implementation Note: SimpleEntry and SimpleImmutableEntry are distinct unrelated classes, even though they share some code. Since you can't add or subtract finalness of a field in a subclass, they can't share representations, and the amount of duplicated code is too small to warrant exposing a common abstract class.

This class facilitates the process of building custom map implementations.

  1.     /**
  2.     * Provide some basic implementations by Entry interface
  3.     * to get key, get value and set Value...
  4.     **/
  5.     public static class SimpleEntry<K,V>  
  6.         implements Entry<K,V>, java.io.Serializable  
  7.     {  
  8.         private static final long serialVersionUID = -8499721149061103585L;  
  10.         private final K key; // key CANNNOT changed  
  11.         private V value;  
  13.         /***** Two constructors by providing key, value or an entry object ******/
  14.         public SimpleEntry(K key, V value) {  
  15.             this.key   = key;  
  16.             this.value = value;  
  17.         }  
  19.         public SimpleEntry(Entry<? extends K, ? extends V> entry) {  
  20.             this.key   = entry.getKey();  
  21.             this.value = entry.getValue();  
  22.         }  
  24.         public K getKey() {  
  25.             return key;  
  26.         }  
  29.         public V getValue() {  
  30.             return value;  
  31.         }  
  33.         public V setValue(V value) {  
  34.             V oldValue = this.value;  
  35.             this.value = value;  
  36.             return oldValue;  
  37.         }  
  39.         public boolean equals(Object o) {  
  40.             if (!(o instanceof Map.Entry))  
  41.                 return false;  
  42.             Map.Entry e = (Map.Entry)o;  
  43.             return eq(key, e.getKey()) && eq(value, e.getValue());  
  44.         }  
  46.         public int hashCode() {  
  47.             // exclusive or between key and value
  48.             return (key   == null ? 0 : key.hashCode()) ^  
  49.                    (value == null ? 0 : value.hashCode());  
  50.         }  
  52.         public String toString() {  
  53.             return key + "=" + value;  
  54.         }  
  56.     }  
  58.     /******** Only difference is ..SimpleImmutableEntry doesn't support setValue *********/
  59.     public static class SimpleImmutableEntry<K,V>  
  60.         implements Entry<K,V>, java.io.Serializable  
  61.     {  
  62.         private static final long serialVersionUID = 7138329143949025153L;  
  64.         private final K key;  
  65.         private final V value;  
  67.         public SimpleImmutableEntry(K key, V value) {  
  68.             this.key   = key;  
  69.             this.value = value;  
  70.         }  
  72.         public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {  
  73.             this.key   = entry.getKey();  
  74.             this.value = entry.getValue();  
  75.         }  
  77.         public K getKey() {  
  78.             return key;  
  79.         }  
  81.         public V getValue() {  
  82.             return value;  
  83.         }  
  85.         /****** Note HERE *******/
  86.         public V setValue(V value) {  
  87.             throw new UnsupportedOperationException();  
  88.         }  
  90.         public boolean equals(Object o) {  
  91.             if (!(o instanceof Map.Entry))  
  92.                 return false;  
  93.             Map.Entry e = (Map.Entry)o;  
  94.             return eq(key, e.getKey()) && eq(value, e.getValue());  
  95.         }  
  97.         public int hashCode() {  
  98.             return (key   == null ? 0 :   key.hashCode()) ^  
  99.                    (value == null ? 0 : value.hashCode());  
  100.         }  
  102.         public String toString() {  
  103.             return key + "=" + value;  
  104.         }  
  106.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注