JDK1.7HashMap源码详细解读

JDK1.7HashMap源码详细解读

（本文的源码解析都存在与代码块的注释里面，请耐心观看）

开始之前 我们先简单了解以下HashMap。HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）

简单理解一下上面的图，假设我目前有一个数组，我想在数组中放入一个k-v结构的数据比如（“xmc”，“hansome”）它会根据数据的key也就是xmc，计算出一个hash码，根据hash码放入数组之中，这样的话，即使我以后存了成百上千的数据，只要我输入xmc，他就根据我的xmc计算出hash码从而快速定位到数组下标拿到我的“hansome”。但是hash码可能会形成冲突，比如“aaa”的hash码和我“xmc”的hash码一样，这时便可以在我数组的对应位置上加上一个结点解决冲突。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等 *** 作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加 *** 作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找 *** 作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

HashMap类如下

    static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        } 

一些重要的参数，看代码前必读。

transient int size;


int threshold;


final float loadFactor;


transient int modCount;

 public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);//带参构造方法
    }


    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
//调用默认构造方法，其中DEFAULT_INITIAL_CAPACITY=64，DEFAULT_LOAD_FACTOR=0.75
    }

下面看一下HashMap的构造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)//容量大小小于0抛异常
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)//大于0就设为1<<30
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
    //负载因子小于0或不是float型抛异常
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;//threshole等于初始容量
        init();//空的方法
    }

我们可以查看以下最常用的put方法源码，值得注意的是HashMap是在第一次放入数据的时候生成的table数组！！

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {//如果table为空，源码见下
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);//hashmap允许key为空的情况，会放入key为空的位置
        int hash = hash(key);//计算hash值，可以不用在乎
        int i = indexFor(hash, table.length);//找到放的位置，源码见下 重点！
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            //在entry数组中查找hash码相同并且key相同的位置，放入
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;//注意！ put方法是会返回原来的value值的（如果已经有的话）
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

首先我们查看table为空的情况（以下两块代码段为重点，也解释了为什么HashMap在java中的长度必须是2的n次方，因为Entry数组的长度是要和key的hash码做与运算的）

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
            //roundUpToPowerOf2方法为把一个数字向上转化为一个2的n次幂的数字，比如我传入7，给我转成8，传入10，转为16

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];//初始化Entry数组 大小为上面的得到的capacity；
        initHashSeedAsNeeded(capacity);
    }

 static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);//这就是我们的数据存放的位置 也就是h和length-1做与运算，可以看到length必须是2的整数次幂，在上面的entry数组初始化源码中我们已经知道了是如何 *** 作的，
    }

下面查看一下addEntry(hash, key, value, i);方法

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {//如果以及存在的数字大于了负债因子，扩容 数组长度乘2（保证一定是2的n次幂）
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);//头插法在新建结点
    }

当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的 *** 作。举个例子，假设现在entry数组长度为4，负载因子为2，此时entry头两个位置以及有了a,b两个数据，该addEntry方法会扩充entry长度至4，但是我想新放入的数据还是可能会在前两个ab的下面加入一个新节点。

可以查看下resize方法

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }//如果原来的capacity已经是最大的，则直接返回

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//源码见下 关键点
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

//transfer
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {//遍历原来的entry数组，把原数组的内容放入新数组
            while(null != e) {
                Entry next = e.next;
                if (rehash) {//重新计算hash，放入新的数组之中
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];//这部分就是1.7令人诟病的地方，如果是多线程，很容易成环
                newTable[i] = e;
                e = next;
            }
        }
    }

  public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }




final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry 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;
    }

下面看看HashMap的get方法，由于比较简单 所以不做分析了

  public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }




final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry 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;
    }