8/26/2010

HashMap

简介

packagejava.util;

importjava.io.*;

HashMap属于包java.util,实现中使用到了包java.io中的某些类。

它继承自AbstractMap,实现了Map接口,Cloneable接口,Serializable接口

默认值

staticfinal int DEFAULT_INITIAL_CAPACITY = 16;

默认容量大小为16

staticfinal int MAXIMUM_CAPACITY = 1 << 30;

最大值为2的30次方

staticfinal float DEFAULT_LOAD_FACTOR = 0.75f;

默认装载因子为0.75

transientEntry[] table;

Entry的数组,即实际存储key和value对的容器。

staticclass Entry<K,V> implements Map.Entry<K,V>{}

Entry实现了Map里的Entry接口。

四种构建方法

publicHashMap(int initialCapacity, float loadFactor)

publicHashMap(int initialCapacity)

publicHashMap()

publicHashMap(Map<? extends K, ? extends V> m)

hash的实现:

 static int hash(int h) {

        // This function ensures that hashCodesthat differ only by

        // constant multiples at each bitposition have a bounded

        // number of collisions (approximately8 at default load factor).

        h ^= (h >>> 20) ^ (h>>> 12);

        return h ^ (h >>> 7) ^ (h>>> 4);

    }

只是二进制数本身的移位与异或运算。

索引的实现:

    static int indexFor(int h, int length) {

        return h & (length-1);

    }

注意这里,就决定了length最好是2的n次方。

获取key对应的value

publicV get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e =table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash && ((k =e.key) == key || key.equals(k)))

                return e.value;

        }

        return null;

    }

-----------end---------------

if(key == null)    return getForNullKey();

这一句单独用于处理key为null的情况.这也是HashMap允许任何形式null值的原因所在.

如果key不为null,则获取key的hashCode,根据静态方法hash(int h)

h^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^(h >>> 4);

求得对应的hash值,然后用求得的hash值去table里找到该hash值对应的索引.

table是一个Entry数组,对应的table[i]即是一个Entry对象(实现了Map.Entry),里边有K,V,hash值,和next.

如果没有预先put进去,会是一个null值,即返回null; 如果有,则判断该处的hash值与key值是否与get(key)里的key一致,如果不一致则e= e.next();直到找到一致的或者e == null;

null值的处理

get:

    private V getForNullKey() {

        for (Entry<K,V> e = table[0]; e!= null; e = e.next) {

            if (e.key == null)

                return e.value;

        }

        return null;

}

get时,当key为null执行此方法.即是索引的0位置.

put:

    private V putForNullKey(V value) {

        for (Entry<K,V> e = table[0]; e!= null; e = e.next) {

            if (e.key == null) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(0, null, value, 0);

        return null;

    }

由for循环中的循环体可知,如果table[0]位置不为null则直接将V替换掉原来Entry中的V;

否则,则在table[0]直接增加一个Entry;

put的实现 & hash值冲突的处理

   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;

}

如果key为null,则直接调用null值的put方法;

否则,计算hash值 => 找hash值在table中对应的索引=> 判断该索引是否为null =>

为null,直接添加;

不为null,判断hash值和key值是否相同(即使不同的hash值得到的索引i也可能相同),相同直接更新V,不相同则继续e = e.next();直到找到具有完全相同hash值和key值的e(Entry), 或e == null;

如果最终e == null; 而且未找到完全相同的Entry,则运行addEntry(hash, key,value, i);

   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);    //增长方式: *2;

    }

利用一个单链的方式处理hash冲突.

假如本来table[i]为A,且A.next() == null;

这时候put方法获取了一个hash值与A的相同,但key值与A的不同的参数,则利用获得的两个参数key和value以及hash值与索引i值组合生成一个Entry B, 则将B放入table[i],将B.next 指向A;

同理,put了一个C,则将C放入table[i],C.next指向B;

containsKey

   public boolean containsKey(Object key) {

       return getEntry(key) != null;

}

很猥琐吧,还是少用点;

containsValue

   public boolean containsValue(Object value) {

         if(value == null)

           return containsNullValue();

         Entry[]tab = table;

       for (int i = 0; i < tab.length ; i++)

           for (Entry e = tab[i] ; e != null ; e = e.next)

                if (value.equals(e.value))

                    return true;

         returnfalse;

}

    private boolean containsNullValue() {

         Entry[] tab = table;

        for (int i = 0; i < tab.length ;i++)

            for (Entry e = tab[i] ; e != null ;e = e.next)

                if (e.value == null)

                    return true;

         return false;

    }

更猥琐.

默认值与增长方式:

默认值为16,且即使指定初值,大小也只能是第一个比指定值大的2^n!

增长方式, 只有addEntry和putAll中直接会调用

   void resize(int newCapacity) {

       Entry[] oldTable = table;

       int oldCapacity = oldTable.length;

       if (oldCapacity == MAXIMUM_CAPACITY) {

           threshold = Integer.MAX_VALUE;

           return;

       }

       Entry[] newTable = new Entry[newCapacity];

       transfer(newTable);

       table = newTable;

       threshold = (int)(newCapacity * loadFactor);

    }

   /**

    * Transfers all entries from current table to newTable.

    */

   void transfer(Entry[] newTable) {

       Entry[] src = table;

       int newCapacity = newTable.length;

       for (int j = 0; j < src.length; j++) {

           Entry<K,V> e = src[j];

           if (e != null) {

                src[j] = null;

                do {

                    Entry<K,V> next =e.next;

                    int i = indexFor(e.hash,newCapacity);

                    e.next = newTable[i];

                    newTable[i] = e;

                    e = next;

                } while (e != null);

           }

       }

}

当扩容的时候要去遍历所有的Entry,所以事先指定容量是能节约很多时间的。

遍历方式:

详见:HashMap遍历的三种方法

遍历Entry,Set<Map.Entry<K,V>>;

  publicSet<Map.Entry<K,V>> entrySet();

遍历value,Collection<V>;

  publicCollection<V> values();

遍历key, Set<K>;  //与Hashtable不同

  publicSet<K> keySet();

其他的方法基本上都是基于这些方法的.

OK~