Java学习之HashMap: 源码学习

HashMap继承AbstractMap并实现Map接口。类图如下

1.AbstractMap

不妨先从AbstractMap源码看起。AbstractMap的实现较为简单明了， 总结如下：

 

1. 这个类提供了Map接口的实现的一个基本骨架，通过继承这个类来实现自己的Map，仅需要完成极少量的工作：实现AbstractMap中抽象的entrySet()方法，并提供一个Map.Entry的实现即可
2. 这个类没有为性能做优化，几个基本的方法如下

          remove()--线性时间

          get()-------线性时间

          put()-------不支持

          entrySet()-未实现

          putAll()----调用put()完成

          clear()------在entrySet()返回的Set上执行clear()

 

          它的remove()和get()方法使用最直观的办法，说白了就是遍历entrySet()返回的Set， 发现目标则执行相应的remove或get操作。(remove(), get(), clear()全都依赖于entrySet()； 又规定Map接口的entrySet()返回当前映射表的视图而不是副本--即对视图的修改会影响原来的映射表， remove(), get(), clear()只需要对目前一个并未实现的视图进行操作即可。真会偷懒，没干多少活，目标就实现了！ )

 

还需要注意的是， AbstractMap的实现并没有涉及到hash相关的东西，这也是它的名字中看不到Hash的原因。 

 

2.HashMap

2.1. entrySet()方法及"视图"

既然HashMap继承自AbstractMap，它首先必须实现的是抽象的entrySet()方法。以下是源码

 

    public Set<Map.Entry<K,V>> entrySet() {
	return entrySet0();
    }

    private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }

    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;
            Entry<K,V> candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

 entrySet()的实现相当简单，仅仅是返回一个HashMap.EntrySet (下文简称为EntrySet)的实例。

 

2.1.1. EntrySet实现

EntrySet的类图如下

EntrySet继承自AbstractSet。AbstractSet的子类仅需要实现size()和iterator()方法即可。EntrySet各方法具体实现如下

  size()------直接返回外部HashMap实例的size(The number of key-value mappings)即可

  clear()-----直接在调用外部HashMap实例中的clear()方法即可

  contains()-通过参数obj(一个Map.Entry)的key找到对应的Entry , 假定名为candidate, 比较candidate和obj是否"相等"

  iterator()--返回一个EntryIterator实例

  remove()--调用外部HashMap实例的removeMapping()方法。

 

 

EntryIterator是如何工作的呢。 它的源码如下

 

    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

 原来是继承自HashIterator, 而且仅仅是覆盖了HashIterator的next()方法

 

 

HashIterator部分实现了Iterator接口， 未实现next()方法，所以仍然是一个抽象类。 我们问题的是entrySet()到底是怎样实现HashMap的视图而非副本的， 所以只看关键的源码 

 

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

可以看到，HashIterator(也即EntryIterator)内部维护了到HashMap的table(一个Entry数组，存储HashMap的键值对， 下文有介绍)中Entry的引用。所以在EntryIterator的迭代器上调用remove，最终会影响到HashMap保存的键值对。

 

 

综合起来，1) EntrySet的remove()调用外部HashMap实例的removeMapping()方法； 2)EntryIterator内部维护到HashMap的table中Entry的引用， 这是实现 "视图" 效果的关键。

 

2.1.2 EntrySet"视图"效果的验证

调用EntrySet的remove()方法。 结果表明会影响HashMap

 

	map.put("map_key", "map_value");
	map.put("map_key2", "map_value2");
	System.out.println("remove之前的map " + map);
	Set<Entry<String, String>> entrySet = map.entrySet();
	System.out.println("remove之前的entrySet " + entrySet);
	System.out.println(entrySet);

	// 1. 通过remove删除一个entry??
	// 1.1 可是我们没法直接生成一个完全一样的entry, 通过下面的方法获取一个
	Entry<String, String> entry = entrySet.toArray(new Entry[2])[0];
	System.out.println(entry);

	// 1.2 删除
	entrySet.remove(entry);

	// entrySet变了吗?
	System.out.println("remove之后的entrySet " + entrySet);
	// map变了吗?
	System.out.println("remove之后的map " + map);

 

调用EntrySet的add()方法。  结果表明add方法未被HashMap.EntrySet实现 , 所以抛出异常(实际当中确实也不应当像以下代码这么使用HashMap)

 

	map.put("map_key", "map_value");
	map.put("map_key2", "map_value2");
	System.out.println("add之前的map " + map);
	System.out.println("add之前的entrySet " + map.entrySet());

	map2.put("map2_key", "map2_value");

	entrySet = map.entrySet();
	// 通过add增加一个entry
	// 可是我们直接生成一个entry太麻烦, 通过下面的方法获取一个
	// entrySet.add(map2.entrySet().toArray(new Entry[2])[0]);

	// entrySet变了吗?
	System.out.println("add之后的entrySet " + entrySet);
	// map变了吗?
	System.out.println("add之后的map " + map);

 

调用EntrySet的iterator的remove()方法。 结果表明会影响HashMap

 

		map.put("map_key", "map_value");
		map.put("map_key2", "map_value2");
		System.out.println("remove之前的map " + map);
		System.out.println("remove之前的entrySet " + map.entrySet());

		entrySet = map.entrySet();
		Iterator<Entry<String, String>> it = entrySet.iterator();
		if (it.hasNext()) {
			it.next();
			it.remove();
		}
		// entrySet变了吗?
		System.out.println("remove之后的entrySet " + entrySet);
		// map变了吗?
		System.out.println("remove之后的map " + map);

 

2.2. 构造方法

 

    /**
     * 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;

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

table---HashMap的槽位(slot)或桶位(bucket)。 这个一个数组，java中存储一组元素最快的数据结构是数组，所以使用它来表示键的信息是合理的。但是这里有一个问题，数组大小固定，而HashMap中保存键值对的数量却不固定。答案是：数组并不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，即散列码(hashCode)。为解决数组容量被固定的问题，不同的键可以产生相同的下标，也即可能会有冲突。因此数组多大就不重要了，任何键总能在数组中找到它的位置。 

 

 

loadFactor--负载因子。 由于table大小有限，而HashMap中保存键值对的数量不固定，所以不存在完美的散列函数(不同对象的hashCode()方法返回的值有可能相同)。所以table只能存储外部链表之类的数组结构来解决冲突问题。在链表中只能使用equals()方法进行线性查询，这部分的查询相对会比较慢， 主要影响因素有: 1) 散列函数的质量，质量越高冲突越少，则table中的分布均匀，每个链表将越短； 2) 负载因子，负载因子越大查询性能越低，负载因子越小内存浪费越多。 随着HashMap中键值对越来越多， 冲突越来越多，键值对数量达到一定时候，HashMap有必要根据负载因子调整table大小。

 

2.3. get()方法 

 

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, 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;
    }

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    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);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 get()方法的处理过程即在下图中查找某个(椭圆形)元素的过程。

即先通过某种hashCode得到该元素所在链表在table中的索引位置，再由这个索引位置取得对应链表，最后在链表中进行线性查询。

这里要注意一下另外两个方法

  hash(int h)-----对hashCode()返回的hash码进行再hash， 主要是防止出现低位(lower bits)相同的(糟糕的)hash码， 减少冲突

  index()---------对上述方法得到的hash码进行再调整，保证得到一个合法的索引值(< table.length)。 

2.4. put()方法

put()方法源码如下

 

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

 对比get()方法，put()方法不难理解。 但要注意两点：1)put()方法可能会从结构上修改HashMap，所以会操作modCount以便"快速失败"检查；2) 如果之前不存在相同的键，则会向HashMap中增加一个新的键值对，即addEntry()。当size超过threshold时，将调整tabler大小为原来的2倍。addEntry()源码如下

 

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

 

3. 总结

以上分析了HashMap几个基本且关键的方法。 水平有限， 可能疏漏。 最后摘抄一段HashMap的文档进行总结：

 

HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假定哈希函数将元素正确分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代集合视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）的和成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

注意，此实现不是同步的。如果多个线程同时访问此映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：

 Map m = Collections.synchronizedMap(new HashMap(...));
 

由所有此类的“集合视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间任意发生不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

 

评论

2 楼 springmvc-freemarker 2015-05-31  

java hashmap学习，地址：
http://www.zuidaima.com/share/khashmap-p1-s1.htm

1 楼 stuhack0303 2013-05-03  

分析的很好~