Android(安卓)HashMap源码解析

在Android中，HashMap也是经常用到的，这里我根据源码简单分析一下HashMap

首先我们一般从构造方法看起，在看构造方法之前，我们先了解一下HashMapEntry这个类，源码如下：

    static class HashMapEntry<K, V> implements Entry<K, V> {        final K key;        V value;        final int hash;        HashMapEntry<K, V> next;        HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }        public final K getKey() {            return key;        }        public final V getValue() {            return value;        }        public final V setValue(V value) {            V oldValue = this.value;            this.value = value;            return oldValue;        }        @Override public final boolean equals(Object o) {            if (!(o instanceof Entry)) {                return false;            }            Entry<?, ?> e = (Entry<?, ?>) o;            return Objects.equal(e.getKey(), key)                    && Objects.equal(e.getValue(), value);        }        @Override public final int hashCode() {            return (key == null ? 0 : key.hashCode()) ^                    (value == null ? 0 : value.hashCode());        }        @Override public final String toString() {            return key + "=" + value;        }    }

HashMap是以数组加链表的形式存储的，说白了HashMap中存储的就是HashMapEntry，我们看HashMapEntry中的4个变量，key、value这个不必解释，大家也都知道，hash和next是在存储的时候使用，链表的数据结构，hashCode()方法用来判断存储在哪个数组里面的，equals()方法用来判断是否是同一个对象，这个我们在上篇博客中有解释到。

在看HashMap的构造方法之前，我们先看几个HashMap的变量：

    private static final int MINIMUM_CAPACITY = 4; //最小容量    private static final int MAXIMUM_CAPACITY = 1 << 30;  //最大容量，左移30位，相当于1*2^30    private static final Entry[] EMPTY_TABLE = new HashMapEntry[MINIMUM_CAPACITY >>> 1]; //HashMap中有个表table，保存一个HashMapEntry数组    static final float DEFAULT_LOAD_FACTOR = .75F;    transient HashMapEntry<K, V>[] table;    transient HashMapEntry<K, V> entryForNullKey;    transient int size;    transient int modCount; //标记修改次数的值    private transient int threshold; //阀值，表的大小，扩容相关

HashMap构造方法比较多，我在此拿几个看看就好，最简单的这个，前面说过在HashMap中保存有一张表，存储一个HashMapEntry数组：

    public HashMap() {        table = (HashMapEntry<K, V>[]) EMPTY_TABLE;        threshold = -1; // Forces first put invocation to replace EMPTY_TABLE    }

再看另一个构造方法：

    public HashMap(int capacity) {        if (capacity < 0) {            throw new IllegalArgumentException("Capacity: " + capacity);        }        if (capacity == 0) {            @SuppressWarnings("unchecked")            HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;            table = tab;            threshold = -1; // Forces first put() to replace EMPTY_TABLE            return;        }        if (capacity < MINIMUM_CAPACITY) {            capacity = MINIMUM_CAPACITY;        } else if (capacity > MAXIMUM_CAPACITY) {            capacity = MAXIMUM_CAPACITY;        } else {            capacity = roundUpToPowerOfTwo(capacity);        }        makeTable(capacity);    }

前面部分比较简单，先判断这个容量，当然他的值不能小于零，否则会抛出异常，这个部分就不再介绍了，大家都能看懂。这个构造方法里面有两个比较关键的方法，就是roundUpPowerOfTwo(capacity)和makeTable(capacity)，前者是算出一个比capacity大的2的n次方的最小值，后者其实就相当于是初始化table，我们进入方法详细看一下：

    private static int roundUpToPowerOfTwo(int i) {        i--; // If input is a power of two, shift its high-order bit right        // "Smear" the high-order bit all the way to the right        i |= i >>>  1;        i |= i >>>  2;        i |= i >>>  4;        i |= i >>>  8;        i |= i >>> 16;        return i + 1;    }

这个方法刚看是不是很晕，我们在计算时要换算成二进制去计算，其实很简单，说白了就是位移运算和或运算，i |= i >>> 1 就是 i = i | i >>> 1，例如，capacity的值为5，按之前介绍的这个方法的作用，算出大于5的2的n次方的最小值，首先口算一下是8（也就是2的3次方），我们在用这个方法去反向验证一下：

5转换为二进制数是 0000 0101

执行 i-- 0000 0100

执行i >>> 1 0000 0010

执行i = i | i >>>1 0000 0110

执行i >>> 2 0000 0001

执行i = i | i >>>2 0000 0111

... ... // 再继续执行 i |= i >>>4和 i |= i >>>8 和 i |= i >>> 16时已经不再影响结果

执行 i + 1 0000 1000 转换为十进制数是8

这样就应该能明白了吧，不懂的话还可以再多算一算就明白了，至于前面要先执行 i-- 是因为如果capacity传入的值正好是2的n次方时，最后执行i + 1的话就返回结果就是2的n+1次方了，这就出错了。

注意，这个方法的参数类型为int类型，int类型为32位，所以最多执行到 i >>> 16 时，结果就不再受影响。

    private HashMapEntry<K, V>[] makeTable(int newCapacity) {        @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable                = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];        table = newTable;        threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity        return newTable;    }

这个方法就是初始化table，里面存放一个HashMapEntry数组，这个threshold阀值，HashMap判断当前数组对象（HashMapEntry）超过这个值之后就会扩容，这个值大概是newCapacity的3/4，也就是数组长度的75%.

再看一下HashMap中最最常用的两个方法，大家都熟悉的put()和get()方法：

    @Override public V put(K key, V value) {        if (key == null) {            return putValueForNullKey(value);        }        int hash = secondaryHash(key.hashCode());        HashMapEntry<K, V>[] tab = table;        int index = hash & (tab.length - 1);        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {            if (e.hash == hash && key.equals(e.key)) {                preModify(e);                V oldValue = e.value;                e.value = value;                return oldValue;            }        }        // No entry for (non-null) key is present; create one        modCount++;        if (size++ > threshold) {            tab = doubleCapacity();            index = hash & (tab.length - 1);        }        addNewEntry(key, value, hash, index);        return null;    }

首先判断key值是否位空，如果为空则调用putValueForNullKey()方法，这里先跳过这个方法，一会儿回头来看。

然后计算出key的hash值，根据hash值计算出index值找到在数组中的位置，也就是找到相应的链表（前面说过HashMap是数组加链表的形式存储的，数组的每个元素相当于一直链表，自己脑补一下），如果在链表中存在hash值相等并且也key值相等的entry（HashMap中保存的是HashMapEntry），将新的value值替换就的value值，并且返回旧的value值。

// 如果不存在对应key（key不为null）值，则新建一个。

新建时要去判断size是否大于阀值，当size大于阀值时，需要对HashMap进行扩容，调用doubleCapacity方法，若小于阀值，则直接插入，最后调用addNewEntry方法插入一个新的entry。

首先看putValueForNullKey方法：

    private V putValueForNullKey(V value) {        HashMapEntry<K, V> entry = entryForNullKey;        if (entry == null) {            addNewEntryForNullKey(value);            size++;            modCount++;            return null;        } else {            preModify(entry);            V oldValue = entry.value;            entry.value = value;            return oldValue;        }    }

如果entry==null，说明HashMap中不存在key值为null的HashMapEntry，就调用addNewEntryForNullKey方法，如果存在则替换就的value值，下面看addNewEntryForNullKey方法：

    void addNewEntryForNullKey(V value) {        entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);    }

有点乐，哈哈，这个方法就一句话，很简单，都能看懂哦，不解释了！
继续看扩容的方法doubleCapacity方法，这个方法好长好长，我把这个方法割成小块小块来解释：

        HashMapEntry<K, V>[] oldTable = table;        int oldCapacity = oldTable.length;        if (oldCapacity == MAXIMUM_CAPACITY) {            return oldTable;        }        int newCapacity = oldCapacity * 2;        HashMapEntry<K, V>[] newTable = makeTable(newCapacity);        if (size == 0) {            return newTable;        }

首先看需要扩容的hashmap是否达到了最大容量，如果达到了就没法再扩容了哦，直接将原来的hashmap返回，如果没有达到最大容量，则将容量扩大为原来的二倍，创建一个新的table表，还需调用makeTable方法，就会重新按照新的容量去计算出新的阀值（不明白就往前看）。如果原来的表size为0，说明里面没东西嘛，直接将新的表返回。

        for (int j = 0; j < oldCapacity; j++) {            /*             * Rehash the bucket using the minimum number of field writes.             * This is the most subtle and delicate code in the class.             */            HashMapEntry<K, V> e = oldTable[j];            if (e == null) {                continue;            }            int highBit = e.hash & oldCapacity;            HashMapEntry<K, V> broken = null;            newTable[j | highBit] = e;            for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {                int nextHighBit = n.hash & oldCapacity;                if (nextHighBit != highBit) {                    if (broken == null)                        newTable[j | nextHighBit] = n;                    else                        broken.next = n;                    broken = e;                    highBit = nextHighBit;                }            }            if (broken != null)                broken.next = null;        }        return newTable;

继续前面，如果旧的表中有数据（size不为0），则需要将原来表中的数据重新散列到新的表中，这里要通过HashMapEntry的hash值和容量进行与运算，计算出最高位值highBit，然后通过 j | highBit 计算出数组下标，将e存进去（这里的这个设计然而我也并没有看懂，就不写了，有兴趣的可以自己去再深入研究，有了发现记得告诉我哦）。

继续往下看，这里就比较简单了，判断当前元素下面是否还有挂载这的其他元素，如果有就重新排列，两个最高位比较，如果想等就说明这两个元素位于数组的同一个位置，即他俩处于同一个链表中。（这个地方是整个HashMap中的难点和重点，需要多多研究和理解）。

    void addNewEntry(K key, V value, int hash, int index) {        table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);    }

这个方法就是在table的index位置添加新的HashMapEntry，插入操作。

    public V get(Object key) {        if (key == null) {            HashMapEntry<K, V> e = entryForNullKey;            return e == null ? null : e.value;        }        // Doug Lea's supplemental secondaryHash function (inlined)        int hash = key.hashCode();        hash ^= (hash >>> 20) ^ (hash >>> 12);        hash ^= (hash >>> 7) ^ (hash >>> 4);        HashMapEntry<K, V>[] tab = table;        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];                e != null; e = e.next) {            K eKey = e.key;            if (eKey == key || (e.hash == hash && key.equals(eKey))) {                return e.value;            }        }        return null;    }

这个比较简单，如果key为null，则去取出key为null对应的value值，如果不为null，在根据hash值计算出所在数组的下标，取出HashMapEntry，然后去循环比较key值，知道取出key值相等的对应的value值，找不到则返回null。

关于HashMap的介绍就先介绍这么多吧，里面还有一些其他方法，都比较容易理解了，有兴趣可以自己研究一下。

更多相关文章

随机推荐