HashMap是我们日常使用的较多的集合类之一,要了解清楚HashMap才能更好的使用它。那么,了解一个集合工具的最好的方法就是从它的源码开始研读啦。废话少说,我们就一步一步了解HashMap源码。

1.HashMap是什么

  在看HashMap源码之前,我们必须要先对HashMap是什么,有个宏观的了解。其实,HashMap的本质就是哈希表,它的数据结构是通过组合数组及链表方式实现的。它的数据结构类似下图所示:
pic1.png

2.HashMap的存取

2.1HashMap的put(K key, V value)

我们先看看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    //通过hashCode来算出Hash值
    int hash = hash(key.hashCode());
    //通过Hash值和table的长度的-1的与,获得对应的table的下标
    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为null值的,当我们插入一个Key,Value的时候,HashMap会首先根据Key的HashCode方法计算Hash值(故从此处我们可以了解到,如果重写了HashCode,使用HashMap的时候,要多加小心),当计算完Hash值之后,就会计算在对应table的位置。indexFor方法如下:

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

  这段代码很简单,就是返回刚才计算的Hash值和数组长度-1的与。为什么这里要这么做呢?
  其实,一般情况下,我们很容易想到的是通过哈希取模的方式来获得对应的index的,但是由于h和length取模涉及到除法,所以HashMap使用了h & (length-1)的方式,既提高了效率,又使得对象能够均匀的分布在数组里。
  然而,为何这里要用length-1和h与,而不是直接用length呢?
  要了解这个,我们得先了解HashMap的长度的容量,我们先看看HashMap的默认容量的代码:

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

  HashMap的默认容量是16,但注释里有个关键的一句:MUST be a power of two(必须为2的次方数。)。为何要为2的次方数呢?
  我们再结合上面的h & (length-1)看看,其实这里之所以这么要求,其根本目的就是为了能让数组的空间能被充分的利用。当length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的二进制最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的二进制最后一位是0,这样h&(length-1)的二进制最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。
  了解这个之后,我们再看下addEntry方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //添加到链表里
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

  这个方法涉及到一个重要的概念,Hash的扩容。要了解HashMap的扩容,我们先看看threshold这个变量:

1
2
3
4
5
6
7
8
9
10
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子
 
/**
 * The next size value at which to resize (capacity * load factor).
 * @serial
 */
int threshold;//判断何时扩容的值

  其实,threshold这个变量就是判断何时进行扩容的,它是当前容量和加载因子的乘积。而默认的加载因子是0.75。例如:假设HashMap的容量是16,那么threshold为16*0.75=12,当插入的size大于或等于12时,hashMap就会调用resize方法进行扩容。那么,我们重点看下resize方法及其关联的transfer方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 *
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 *
 * @param newCapacity the new capacity, MUST be a power of two;
 *        must be greater than current capacity unless current
 *        capacity is MAXIMUM_CAPACITY (in which case value
 *        is irrelevant).
 */
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];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    //判断是否需要重新计算Hash值
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
 
/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            //重新计算key的hash值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

  从上面代码我们可以了解到,每一次的扩容操作,其实就是申请一个新的空间,然后将原油的数组复制到新的数组里,而且,有时还需要重新计算元素的Hash值。这个操作是非常消耗性能的。所以,由此我们也可以得出一个结论:HashMap是不适合频繁的存操作的。

2.2HashMap的get(Object key)

  有了对上面Hash算法及put方法的了解后,我们再看get方法相对就会变得简单的多,get方法源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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();
    Entry<K,V> entry = getEntry(key);
 
    return null == entry ? null : entry.getValue();
}
 
/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    //计算key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //计算数组下标并定位链表,遍历链表获取对象
    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;
}

  从上面的代码里,我们可以看到,get方法本质就是先计算key的hash值,然后通过定位下标获取链表,从而获取对应的元素。

3.总结

  HashMap是我们工作中经常用到的集合工具类之一,它所包含的部分特点除上述提到的,还有如下:1.HashMap不是线程安全的,线程安全的建议使用ConcurrentHashMap;2.由于HashMap在扩容的时候,需要进行rehash的,所以,不保证其内部元素的顺序,而且随着时间的推移,同一元素的位置也可能改变(resize的情况)。

转载自:http://www.alienhsu.com/index.php/archives/68/

作者:星辰 时间:2016-09-09 浏览 1018评论 0 赞 0砸 0 标签: 面试题 笔试题 Java基础知识
评论
还可以再输入500个字

请您注意

·自觉遵守:爱国、守法、自律、真实、文明的原则
·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规
·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品
·承担一切因您的行为而直接或间接导致的民事或刑事法律责任
·您在NoteShare上发表的作品,NoteShare有权在网站内保留、转载、引用或者删除
·参与本评论即表明您已经阅读并接受上述条款