Javaエンジニア面接---Mapシリーズ

9938 ワード

一、Map
public interface Map 

これはインタフェースであり、Mapのインタフェースであり、Kはキーワードのタイプを表し、Vはキー値を表す.
 int size();//  
 boolean isEmpty();//    
 boolean containsValue(Object value);//    value
 V get(Object key);//     key value
 V put(K key, V value);//  
 V remove(Object key);//     key map
 void putAll(Map extends K, ? extends V> m);//      
 void clear();//      

 //Map-->       set   
 Set keySet();//          ,          key    1 2 3  3 2 1          。

二、Mapの実現方法
1、HashMap
ハッシュ・テーブルを使用してキー値を格納します.格納された場所は追加の順序に関係なく,HasCode計算の値に関係している.
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

コンストラクション関数:(初期、ロード)
public HashMap(int initialCapacity, float loadFactor)

初期化時に配列が作成されます
new Entry[capacity];

最大長(配列の数+延長の長さ)を許可します.
threshold = (int)(capacity * loadFactor);

1、追加されたソース:
以下から分かるように、格納されている位置はhashで計算されています.
   public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);//    null    
        //hash      
        int hash = hash(key.hashCode());
        //  hash       
        int i = indexFor(hash, table.length);
        //        ,    ,   ,     
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            //  hash ---      
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //    
        modCount++;
        //      
        addEntry(hash, key, value, i);
        return null;
    }
get       hash
    void addEntry(int hash, K key, V value, int bucketIndex) {
    //        
        Entry e = table[bucketIndex];
     //              ,      
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

2、TreeMap
一、以下の継承関係から分かるように、TreeMapは間接的にmapを実現する方法である.より多くのプロパティが用意されています.
きちんとした
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
public interface NavigableMap<K,V> extends SortedMap<K,V> public interface SortedMap<K,V> extends Map<K,V> 
    private final Entry buildFromSorted(int level, int lo, int hi,
                                             int redLevel,
                                             Iterator it,
                                             java.io.ObjectInputStream str,
                                             V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {

//       
        if (hi < lo) return null;

        int mid = (lo + hi) >>> 1;

        Entry left  = null;
        if (lo < mid)
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                                   it, str, defaultVal);

        // extract key and/or value from iterator or stream
        K key;
        V value;
        if (it != null) {
            if (defaultVal==null) {
                Map.Entry entry = (Map.Entry)it.next();
                key = entry.getKey();
                value = entry.getValue();
            } else {
                key = (K)it.next();
                value = defaultVal;
            }
        } else { // use stream
            key = (K) str.readObject();
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }

        Entry middle =  new Entry<>(key, value, null);

        // color nodes in non-full bottommost level red
        if (level == redLevel)
            middle.color = RED;

        if (left != null) {
            middle.left = left;
            left.parent = middle;
        }

        if (mid < hi) {
            Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                               it, str, defaultVal);
            middle.right = right;
            right.parent = middle;
        }

        return middle;
    }

三、Hashtableスレッドの同期、性能がよくないため、あまり使わない.SortedMapはMapの継承であり、秩序あるソートです.
メモ:transientは、データがハードディスクに格納されず、メモリにのみ格納されることを示します.