HashMap原理、源码解析

一、前言

 

HashMap是Map实现中最常使用的，具有快速存取的优点，所以很有必要深入到源码去了解其实现原理。

本文的内容包括：分析HashMap的数据结构和HashMap的常用方法的源码分析。

 

二、HashMap的数据结构

 

HashMap 可以理解为由数组和链表组成的存储结构，如图

 

 

在X轴方向上是一个数组，Y方向是链表。一个节点的信息包括hash、key、value和next。

 

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
        
        ……
}

 

 

 

三、常用方法源码分析

 

1、HashMap的主要相关变量和构造函数

 

 static final int DEFAULT_INITIAL_CAPACITY = 16; 

 static final int MAXIMUM_CAPACITY = 1 << 30; 

 static final float DEFAULT_LOAD_FACTOR = 0.75f;  

 transient Entry[] table;  

 transient int size;     

 int threshold;     

 final float loadFactor;   

   DEFAULT_INITAL_CAPACITY：默认初始化容量，16

    MAXIMUM_CAPACITY ：最大容量，即2的30次方

   DEFAULT_LOAD_FACTOR ：默认负载系数

    Entry[] table：Entry类型的一维数组，长度必须是2的幂，也就是上图的table数组

    int size： 当前HashMap的元素个数

    int threshold： 扩容的临界值，即capacity*loadFactor

    final float loadFactor：hash表的负载系数

 

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

 }

 

 HashMap的初始化主要是initialCapacity和loadFactor这两个参数。前者表示上图中X轴方向table的长度，即不同hash的key的长度，后者是负载系数，扩充的临界值threshold=capacity*loadFactor，当达到扩充临界值时，HashMap会自动扩容。比如默认情况是16*0.75=12，当填充到12时，HashMap会自动将X轴方向的table

的长度扩充到32。HashMap里面的capacity，长度是2的幂，即使你初始化时不是2的幂，它也会帮你转为2

的幂。从上面的代码可以看出来。

 

2、添加元素

 

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

 }

  

基本思路：通过key拿到hash，然后通过hash找到table的索引值，找到之后比较该索引值所在列（Y轴方向

）有没有相同的key，有的话就替换掉原来的vaule，返回旧的value；如果没有相同的key，则把当前元素加进该列的前面，即链表的表头。当容量大于等于扩容的临界值时则扩充为原来table长度的2倍。

注意：HashMap允许key的值为null

 

那它是怎么根据hash值返回该hash在table里面的索引呢？你可能会说，很简单啊，取模就可以了，没错，但取模效率是比较低的，来看看HashMap里面是怎么实现的。

 

static int indexFor(int h, int length) {
    return h & (length-1);
}

 

length，table的长度，也就是HashMap里面的capacity，长度是2的幂，&是与运算，例如length为16，则length-1的二进制为01111，当h为17，即10001，01111&10001=00001，通过与运算取代了取模运算，效率大大提高，这也是为什么table的长度为2的幂。

 

 

3、获取元素

 

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;

 }

  

基本思路：根据传过来的key获取其hash，快速定位到table的索引，再遍历该索引链表，用equals方法找出

该元素的value。

 

注意：一般table里的同个的索引值的元素不会太多，这关系到查找性能的问题，当达到扩容的临界值时会自动扩容，然后rehash，即重新分配所有的元素来尽可能达到哈希均匀。但rehash是很耗性能的，所以如果确定HashMap的容量，最好一开始就初始化好。

 

 

4、删除元素

 

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
}

  

其实删除不难，定义三个指针，一个指向当前元素，另外两个分别指向当前元素的前一个和后一个元素，这主要是链表的操作。

 

 

5、扩容的实现

 

当达到的临界值时，系统会调用resize函数来实现扩容。

 

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

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

 

基本思路：新建一个更大的数组，然后遍历旧数组，修改指针，把一个个的元素放到新数组上，每次插入都是插到链表的表头，并把旧数组设为null。不算太难，但算法精致，值得慢慢品味

 

 

四、小结

 

1、HashMap采用数组和链表组成的存储结构，用数组方式存储hash、key、value和next指针构成的Entry对象，对于冲突采用链表的方式解决；

 

2、HashMap插入时是插入到链表的表头，可能要扩大数组的容量，扩容时需要重新计算hash，并复制对象到新数组中，即rehash；

 

3、HashMap是非线程安全的。

 

 

ps：如写得不好或存在严重错误，欢迎批评指正。

 

 

 

 

评论

1 楼 sprite311 2014-04-24