mapから一(Hashmapをよく勉強)

10136 ワード

mapといえば、このjavaにおけるcollectionファミリーの模範、特にhashmapはよく知られているツール類ですが、詳しく見てみましょう.
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

    /**
     * The number of key-value mappings contained in this map.
     */
   transient int size;
    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     */
    int threshold;
    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;
    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient volatile int modCount;

 
 
これはHashmapのインスタンス変数(jdk 1.6)です.hashmapの本質はtransient Entry[]table配列であり、DEFAULT_のように見えます.INITIAL_CAPACITY(デフォルト容量)、MAXIMUM_CAPACITY最大容量(2^30)、DEFAULT_LOAD_FACTORデフォルトマウントファクタ(0.75)は、これらはすべてstaic finalで、デフォルトの構成と境界を検査するために使用されます.また、設定可能な3つも一般的に伝達されるパラメータです.size(これはmapメモリの数対のデータを記録しています)、threshold、loadFactor、それぞれ境界値、ロードファクタ、関係はthreshold=a*loadFactorです.つまり、tableはaサイズに初期化され、thresholdサイズにコンテンツを追加し続けると、tableは自動的に2倍になります.
 
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

 これは我々がよく使う構造関数であり,基本的には初期容量サイズ,loadFactorの検査,および最も重要なtable=new Entry[capacity];このうちcapacityは私たちがどれだけ制定したのかではなく、彼がどれだけなのか、実際にはinitialCapacityを入力した2よりもちょうど小さい倍数をサイズとして選択しました.
 
 
 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            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;
    }

 これが有名なput関数です.ここではhashmapが同期していないことが明らかになり、空の値をキーとして受け入れることができます.また、良いkeyのhashcode()が必要であることも明らかになります.ゴミのhashcode()関数を設定すると、
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 HashMapのhash関数はどうしようもなく,処理された32ビットhashコードが得られた後もtable[]を得たindexの処理を継続する.
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 簡単な関数で、tableの長さを利用して適切なサイズを切り取り、indexを利用してtableの中でkeyを探し始めました.明らかにこれは空になるまで、または「同じ」keyを見つけてから、addEntryを呼び出さなければ上書きします.
  for (Entry e = table[i]; e != null; e = e.next) {            Object k;            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;
 
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

 ここで明らかに,新しいEntryを追加するたびにsize++が認められ,size>threshold(前の2つを乗算した結果)ではtable長が2倍になる.
 
getは基本的に似ていますが、詳しくは言いません.hashmapで実用的なkeySet()を見てみましょう.
    public Set<K> keySet() {
        Set<K> ks = keySet;
        return (ks != null ? ks : (keySet = new KeySet()));
    }

    private final class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return newKeyIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        public boolean remove(Object o) {
            return HashMap.this.removeEntryForKey(o) != null;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

 明らかにkeyset()は、AbstractSetを実装する内部クラスを返しますが、この内部クラスの実際のset操作は、Haspmapのデータに直接影響します.
 
  この内部クラスではcollectionの隅々まで伴う非常に多くの方法public Iteratoriterator()も見られます
 
 private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;	// next entry to return
        int expectedModCount;	// For fast-fail
        int index;		// current slot
        Entry<K,V> current;	// current entry

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
	    current = e;
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }

    }

 
これは同様にHashmapの内部クラスであり、Iteratorを実現する抽象クラスでもあり、hashmapにはkeyset、value、entryがiteratorを返すための3つの内部クラスがHashIteratorを継承しており、iteratorに対するいかなる変更もHashmapの変化をもたらすことが明らかであり、特にexpectedModCount=modCountであることに注意しなければならない.
               if (modCount != expectedModCount)                throw new ConcurrentModificationException();
ここでは実際にiteratorがHashmapを巡る過程でHashmapの変化(増加と削除はいずれもmodCountの増加をもたらし、前のput関数を見ることができる)が保証されており、iteratorが異常を投げ出すことになるが、put関数をよく見ると、新しく追加するのではなくvalueの交代であればmodCountは変化しないことがわかる.
    Iterator<K> newKeyIterator()   {
        return new KeyIterator();
    }
    Iterator<V> newValueIterator()   {
        return new ValueIterator();
    }
    Iterator<Map.Entry<K,V>> newEntryIterator()   {
        return new EntryIterator();
    }

 
HashIteratorはうまくいったので、自分のiteratorごとに実現するのは簡単です.
    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

 さてHashmapはこれくらいですが、明日はHashmapからもっとmapを広げます