Java集合之HashMap源码实现分析

　　1.简介

　　通过上面的一篇随笔我们知道了HashSet的底层是采用Map实现的，那么Map是什么？它的底层又是如何实现的呢？这下我们来分析下源码，看看具体的结构与实现。Map 集合类用于存储元素对（称作“键”和“值”），其中每个键映射到一个值。Map.Entry是其的内部类，描述Map中的按键/数值对。需要指出的是Map,允许null的键也允许null的值。它的实现主要有HashMap和sortedMap,其中SortedMap扩展了Map使按键保持升序排列，下面我们简要分析下HashMap的具体实现。首先给出一个应用举例：

package com.test.collections;

import java.util.Collection;

import java.util.HashMap;

import java.util.Map;

import java.util.Set;

public class HashMapTest {

	/**

	 * @param args

	 */

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Map<String,String> map = new HashMap<String,String>();

		map.put("A", "A");

		map.put("D", "D");

		map.put("S", "S");

		map.put("C", "C");

		map.put("B", "B");

		map.put("W", "W");

		System.out.println(map.size());

		System.out.println(map.isEmpty());

		System.out.println(map.containsKey("A"));//boolean

		System.out.println(map.containsValue("A"));;//boolean

		System.out.println(map.get("A"));

		System.out.println(map.remove("A"));

		map.putAll(map);

		Set<String> keySet = map.keySet();

		Collection<String>  values = map.values();

		Set<Map.Entry<String, String>> entry = map.entrySet();

		map.clear();

	}

}

　　2.继承结构

　　HashMap直接继承了AbstractMap类，实现了Map<K,V>, Cloneable, Serializable接口，除了这些继承和实现外，它还有一些重要的属性值。简单看一下：

　　　　DEFAULT_INITIAL_CAPACITY：默认的初始化容量（16）；

　　　　MAXIMUM_CAPACITY：能够允许的最大容量（1 << 30）；

　　　　DEFAULT_LOAD_FACTOR：缺省的加载因子（0.75）；

　　　　Entry[] table：存储具体的值。

　　　　transient int size：记录Map的大小。

　　　　final float loadFactor：加载因子。

上面的属性中除了一个Entry类型，这个是什么意思呢。原来这里面就是维护Map键值的类，用来存储Map的具体值的，让我们来看下它的具体实现结构：

 static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;

        Entry<K,V> next;

        final int hash;

        /**

         * Creates new entry.

         */

        Entry(int h, K k, V v, Entry<K,V> n) {

            value = v;

            next = n;

            key = k;

            hash = h;

        }

        public final K getKey() {

            return key;

        }

        public final V getValue() {

            return value;

        }

        public final V setValue(V newValue) {

	    V oldValue = value;

            value = newValue;

            return oldValue;

        }

        public final boolean equals(Object o) {

            if (!(o instanceof Map.Entry))

                return false;

            Map.Entry e = (Map.Entry)o;

            Object k1 = getKey();

            Object k2 = e.getKey();

            if (k1 == k2 || (k1 != null && k1.equals(k2))) {

                Object v1 = getValue();

                Object v2 = e.getValue();

                if (v1 == v2 || (v1 != null && v1.equals(v2)))

                    return true;

            }

            return false;

        }

        public final int hashCode() {

            return (key==null   ? 0 : key.hashCode()) ^

                   (value==null ? 0 : value.hashCode());

        }

        public final String toString() {

            return getKey() + "=" + getValue();

        }

        /**

         * This method is invoked whenever the value in an entry is

         * overwritten by an invocation of put(k,v) for a key k that's already

         * in the HashMap.

         */

        void recordAccess(HashMap<K,V> m) {

        }

        /**

         * This method is invoked whenever the entry is

         * removed from the table.

         */

        void recordRemoval(HashMap<K,V> m) {

        }

    }

　　Entry<K,V> 实现了Map接口中的内部接口Map.Entry<K,V>，key,value分别用来存储键值的， Entry<K,V> next还指向了下一个节点的指针，说明Map的存储空间不是连续的可以使分散的。Hash属性说明键的位置是根据Hash值算出来的。需要注意的是这是作为HashMap的内部类出现的。此外还有内部类KeySet，Values、EntrySet、ValueIterator、KeyIterator、EntryIterator不过通过类名称就可以知道他们的具体作用了吧。

3.源码解析

　　a:构造函数

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();

    }

public HashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

   public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        init();

    }

   public HashMap(Map<? extends K, ? extends V> m) {

        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

        putAllForCreate(m);

    }

 void init() {

    }

   private void putAllForCreate(Map<? extends K, ? extends V> m) {

        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {

            Map.Entry<? extends K, ? extends V> e = i.next();

            putForCreate(e.getKey(), e.getValue());

        }

    }

　　构造方法只需要说明第一个的即可，其他的都是传递一些缺省的参数值然后调用第一个构造方法实现具体的操作。重点看下第一个构造方法。它首先判断一下传入的容量是否合法以及加载因子是否合法。如果容量操作最大值是需要将它重置的，但是如果传入的值为负数是要抛出异常的。然后根据容量与加载因子的乘积得出临界值并且赋值给属性threshold，然后通过 table = new Entry[capacity]分配存储空间，完成了构造过程。Init()方法为空，不知道做了什么事情。

2.hash(int h)

 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);

    }

　　根据Hash 值确定键的位置，如果传入的为null,那么返回的hash值就是为0，索引值就是0.

3.size(),isEmpty()

   public int size() {

        return size;

    }

    /**

     * Returns <tt>true</tt> if this map contains no key-value mappings.

     *

     * @return <tt>true</tt> if this map contains no key-value mappings

     */

    public boolean isEmpty() {

        return size == 0;

    }

　　Map大小就是直接返回属性值size的值，判断是否为空就是如果size为0说明为空否则不为空。

4.get(Object)

    public V 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;

    }

　　根据键返回对应的值，首先判断键是否为null，如果为空的话就调用getForNullKey(）返回空键对应的值只会有一个。其实也就是返回Map的第一个值，因为null对应的hash值为0，存储位置就是第一个。然后调用hash（）方法返回唯一对应的hash值，然后再循环遍历这个Map，如果发现Hash值相等就直接返回它的值，如果没有发现对应的值就返回null.

5.containsKey(Object ）

   public boolean containsKey(Object key) {

        return getEntry(key) != null;

    }

    final Entry<K,V> getEntry(Object key) {

        int hash = (key == null) ? 0 : 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 != null && key.equals(k))))

                return e;

        }

        return null;

    }

　　判断是否含有某个值就是首先获取这个值，如果获取的值不为空就说么这个对象是存在的。获取key的方法是根据getKey()方法来实现的。首先获取Hash值，然后遍历循环这个Entry数组，如果遇到键相同就返回否则就返回为null.

6.put(K，V)

    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;

    }

   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);

    }

    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);

    }

　　我们是通过put（K,V）方法来添加对象到Map中的，首先判断传入的Key是否为null，如果为null就直接调用putForNullKey(value)方法将null的键对应上值。如果不为空就首先获取K对应的Hash值,然后遍历循环这个Map，如果值已经存在就更新覆盖value并且返回返回老的value，否则的话就调用addEntry(hash, key, value, i);插入新值。插入及很简单了，New一个Entry对象然后确定数组位置指定值即可。

4.其他

　　HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量是哈希表中数据的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的数目。

巴特西