`
410063005
  • 浏览: 177590 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

Java学习之HashMap: 源码学习

    博客分类:
  • java
 
阅读更多

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 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

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

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

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

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

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

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

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

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

 

  • 大小: 9.4 KB
  • 大小: 24.2 KB
  • 大小: 5.4 KB
  • 大小: 6.3 KB
分享到:
评论
1 楼 stuhack0303 2013-05-03  
分析的很好~

相关推荐

Global site tag (gtag.js) - Google Analytics