Java容器HashMap源代码解析

Bertha 。 2022-06-15 04:08 245阅读 0赞

## **写在前面的话** ##

本文针对的是Java1.6进行的源码分析，与其他版本可能存在差异。

## **哈希表** ##

HashMap是基于哈希表来实现的，在介绍HashMap前，我们先了解一下哈希表。哈希表查找效率非常高，只需要O(1)的时间，相比之下，在一个大小为n的数组中查找数据，则需要O(n)时间。哈希表是基于数组来实现的，它的设计思路是把关键字key通过hash函数映射到数组的不同位置上。这样，当进行查找操作时，可以根据key直接得到数据在数组中的下标，只用常数时间就可以完成查找工作。

hash函数有多种实现方法：除法散列法、乘法散列法、全域散列法等。最常用的就是除法散列法，HashMap也是用改方法实现的hash函数。除法散列法就是通过取key除以数组大小m的余数，来将关键字k映射到m个槽的某一个中去。

在哈希表中，数组下标是通过hash函数计算出来的，这样不可避免的会发生多个关键字key映射到同一个数组下标的位置，这种情况我们称之为“碰撞”。主要有两种方法来解决碰撞，一种是链表法，一种是开放寻址法。开放寻址法是在发生碰撞后，根据一定的探查算法，继续探查，直到找到空槽为止。链表法是把散列到同一个槽中的所有元素都放在一个链表中。HashMap就是采用链表法来解决碰撞的。

## **HashMap源代码解析** ##

**1.HashMap的底层数据结构**

上面说到HashMap是用哈希表来实现的，采用的是链表法来解决碰撞，所以哈希表的底层数据结构就是数组和链表。HashMap定义了一个Entry类型的数组table用来存放数据，我们就先从HashMap的内部类Entry看起。源代码如下：

//实现了map.Entry接口
        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            //存放链表的下一个值，用于解决碰撞
            Entry<K,V> next;
            final int hash;
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    
            public final K getKey() {
                return key;
            }
    
            public final V getValue() {
                return value;
            }
    
            public final V setValue(V newValue) {
            V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            //实现equal方法，如果key和value都相等，则返回true
            public final boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry e = (Map.Entry)o;
                Object k1 = getKey();
                Object k2 = e.getKey();
                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                    Object v1 = getValue();
                    Object v2 = e.getValue();
                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
                        return true;
                }
                return false;
            }
    
            //实现hashCode方法
            public final int hashCode() {
                return (key==null   ? 0 : key.hashCode()) ^
                       (value==null ? 0 : value.hashCode());
            }
    
            public final String toString() {
                return getKey() + "=" + getValue();
            }
    
            //在添加元素时，会调用此方法，在这不进行任何操作
            //在LinkedHashMap中会重写该方法
            void recordAccess(HashMap<K,V> m) {
            }
    
            //在删除元素时，会调用此方法，在这不进行任何操作
            //在LinkedHashMap中会重写该方法
            void recordRemoval(HashMap<K,V> m) {
            }
        }

Entry实现了map.Entry接口，包含了键和值，next也是一个Entry对象，用于形成一个链表来解决碰撞。

**2.HashMap属性**

知道了HashMap的底层数据结构后，先来看HashMap中定义的一些重要属性：

/**
         * Entry类型数组，用于存放数据，可以根据需要扩容
         */
        transient Entry[] table;
    
        /**
         * HashMap的大小
         */
        transient int size;
    
        /**
         * 临界值，当HashMap大小大于临界值时，会进行扩容，threshold=capacity * load factor
         */
        int threshold;
    
        /**
         * 加载因子
         */
        final float loadFactor;
    
        /**
         * 修改次数，同其他容器一样
         */
        transient volatile int modCount;

这里，详细说一下加载因子。加载因子其实就是HashMap中存储数据的饱和度，当HashMap中存储存储数据的个数size大于它的容量和加载因子的乘积后，HashMap就会自动扩容。所以，如果加载因子取值过大，虽然容器利用率高了，但是也加大了碰撞的可能性，导致查询效率低下；如果加载因子取值过小，虽然减少了碰撞的概率，但是容器利用率会很低，可能容器中还没存储多少数据，就要扩容了，造成很大的浪费。加载因子的取值需要折中考虑，HashMap给定了加载因子的默认值0.75，我们一般用给定的默认值即可。顺便再看一下HashMap给定的几个默认值：

/**
         * 默认容量大小，容量大小必须是2的幂次方
         */
        static final int DEFAULT_INITIAL_CAPACITY = 16;
    
        /**
         * 最大容量
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 默认加载因子
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

对于容量大小，注释特别提到必须是2的幂次方。那么，为什么会有这个要求呢？我们可以从HashMap的indexFor()方法找到答案。该方法代码如下：

/**
         *返回hashCode的索引值
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }

这个方法的作用是计算出hashCode对应数组table中的索引值。上面已经说了HashMap是通过取余来进行散列，但是取余要用到除法，计算效率比较低。当length大小为2的幂次方时，h&(length-1)与h%length是等效的，但是运算速度提升很大。所以，HashMap要求容量必须是2的整次幂。

**3.构造方法**

HashMap提供了四种构造方法，如下：

/**
         * 给定容量和加载因子的构造方法
         */
        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);
    
            //找到大于initialCapacity的最小的2的幂次方，保证容量一直都是2的幂次方
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
    
            this.loadFactor = loadFactor;
            //计算临界值
            threshold = (int)(capacity * loadFactor);
            //初始化数组
            table = new Entry[capacity];
            //初始化方法，在HashMap中并没有做任何操作，在LinkedHashMap中会重写
            init();
        }
    
        /**
         * 只给了初始容量的构造方法，加载因子会直接用默认值
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * 默认构造函数，加载因子和容量都用默认值
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            table = new Entry[DEFAULT_INITIAL_CAPACITY];
            init();
        }
    
        /**
         * 带有map参数的构造函数
         */
        public HashMap(Map<? extends K, ? extends V> m) {
            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                          DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
            //调用putAllForCreate方法
            putAllForCreate(m);
        }

前三个构造函数都比较好理解，我们可以看看最后一个构造函数的putAllForCreate方法是如何实现的。代码如下：

private void putAllForCreate(Map<? extends K, ? extends V> m) {
            for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                //遍历Iterator，把每个键值对放到table中
                putForCreate(e.getKey(), e.getValue());
            }
        }
    
        private void putForCreate(K key, V value) {
            //hashMap是允许键为null的，如果键为null，则hashCode值就为0
            int hash = (key == null) ? 0 : hash(key.hashCode());
            //计算hashCode在table数组中的索引，上面已经介绍过这个方法
            int i = indexFor(hash, table.length);
    
            //计算出位置i后，遍历table[i]的next链表，判断是否是重复的key，如果是重复的
            //则直接替换原先的value值
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    e.value = value;
                    return;
                }
            }
            //如果不是重复的key，则调用createEntry方法，新建Entry
            createEntry(hash, key, value, i);
        }
    
        //计算hash值
        static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    
        //创建Entry，并存入到table中
        void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            //新建Entry，并把它放在链表的头部
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            //大小加1
            size++;
        }

**4.获取数据**

public V get(Object key) {
            //HashMap允许key为null，如果key为null，单独处理
            if (key == null)
                return getForNullKey();
            //计算hash值，并得到索引，然后遍历所引处的链表，查找value
            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为null的方法
        private V getForNullKey() {
            //HashMap会把key为null的Entry直接放在table[0]位置上，直接在该位置遍历链表就可以了
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }

HashMap的put和get方法基本上是最常用的了，get方法的实现是先判断key值是否为null，这是因为HashMap是允许key值为null的，如果是null，则调用getForNullKey()方法单独处理；如果不为null，则计算key的哈希值，然后计算出在table中的索引，遍历索引处的链表，判断是否有与key值相等的，如果有，则返回对应的value，没有就返回null。注意，在HashMap里如果查找的键不存在，会返回null；而如果在python的字典中查找不存在的键，则就会报异常。

**5.存储数据**

public V put(K key, V value) {
            //HashMap允许key为null，如果key为null，单独处理
            if (key == null)
                return putForNullKey(value);
            //计算hash值，得到索引
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            //遍历索引处链表，如果key值已经存在，则替换原先的value
            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;
                    //此方法在HashMap中没有任何操作，在LinkedHashMap中会重写
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            //修改数加1
            modCount++;
            //如果key值不存在，在调用此方法添加Entry
            addEntry(hash, key, value, i);
            return null;
        }
    
        //单独处理key为null的方法
        private V putForNullKey(V value) {
            //key为null的entry存放在table[0]处，所以先在table[0]处查找是否有key为null
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            //如果不存在key为null的entry，则在table[0]处添加entry
            addEntry(0, null, value, 0);
            return null;
        }
    
        //添加entry方法
        void addEntry(int hash, K key, V value, int bucketIndex) {
            //添加entry
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            //如果HashMap的大小已经到达了临界值，则需要对table扩容
            //为了保证容量一直是2的幂次方，每次直接扩容到原先的2倍
            if (size++ >= threshold)
                resize(2 * table.length);
        }
    
        //扩容方法
        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];
            //把原来的数据都存放到新的table中
            transfer(newTable);
            table = newTable;
            //重新计算临界值
            threshold = (int)(newCapacity * loadFactor);
        }
    
        //转换方法
        void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            //遍历原先的table
            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;
                        //计算在新table中的索引值
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }
        }

HashMap的put方法稍微复杂些，与get方法类似，它也会先判断key值是否为null，如果为null，则调用putForNullKey()方法处理；如果不为null，则找到索引值，遍历索引处的链表，判断key是否已存在，如果存在，则直接替换value，不存在的话，就调用addEntry()方法。我们再来看addEntry()这个方法，它与上文已经介绍过的createEntry()方法相似，不同之处在于多了扩容的步骤。这是因为createEntry()方法只在构造函数用到，这种情形下，table的容量已经提前计算出来，肯定够用，不必再考虑扩容的情形。而addEntry()是在table中新增数据，是有可能使得size达到临界值的，所以必须要考虑扩容。为了保证容量一直都是2的幂次方，所以每次扩容都是扩到原先的2倍。

下面我们再来看下HashMap是如何去扩容的。它会先判断是否已经达到最大容量了，如果已经达到最大容量了，则不再扩容。然后会通过调用transfer()方法，把原先的table中的所有值存入到新的table中，最后再重新计算临界值。

除了put方法，HashMap还提供了putAll()方法，如下：

public void putAll(Map<? extends K, ? extends V> m) {
            int numKeysToBeAdded = m.size();
            //如果m没有要添加的key，不做任何除了
            if (numKeysToBeAdded == 0)
                return;
    
            //如果要添加的key的数量已经超过了临界值，则计算新的容量并扩容
            if (numKeysToBeAdded > threshold) {
                int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
                if (targetCapacity > MAXIMUM_CAPACITY)
                    targetCapacity = MAXIMUM_CAPACITY;
                int newCapacity = table.length;
                while (newCapacity < targetCapacity)
                    newCapacity <<= 1;
                if (newCapacity > table.length)
                    resize(newCapacity);
            }
            //遍历m，把m的键值对依次put到table中
            for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                put(e.getKey(), e.getValue());
            }
        }

**6.判断数据是否存在**

HashMap提供了containsKey()和containsValue()方法，分别用来判断是否存在某个key和某个value值。先来看containsKey()方法：

public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        final Entry<K,V> getEntry(Object key) {
            //计算hash值，得到索引
            int hash = (key == null) ? 0 : hash(key.hashCode());
            //遍历索引处链表，如果Key存在，就返回相对应的entry，如果不存在，则返回null
            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()方法中去查找value的代码类似，不再详述。下面再看containsValue()方法。

public boolean containsValue(Object value) {
            //HashMap允许value为null，null不能用equals方法直接比较，所以单独处理
            if (value == null)
                return containsNullValue();
    
            Entry[] tab = table;
            //查找value，无法得到索引，只能遍历table
            for (int i = 0; i < tab.length ; i++)
                for (Entry e = tab[i] ; e != null ; e = e.next)
                    if (value.equals(e.value))
                        return true;
            return false;
        }
    
        //单独处理value为null的情形
        private boolean containsNullValue() {
            Entry[] tab = table;
            for (int i = 0; i < tab.length ; i++)
                for (Entry e = tab[i] ; e != null ; e = e.next)
                    if (e.value == null)
                        return true;
            return false;
        }

**7.删除数据**

public V remove(Object key) {
            Entry<K,V> e = removeEntryForKey(key);
            //如果key存在，则返回对应的value；key不存在，则返回null
            return (e == null ? null : e.value);
        }
    
        //删除entry方法
        final Entry<K,V> removeEntryForKey(Object key) {
             //计算hash值，得到索引
            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;
    
            //遍历链表，找到对应的entry，如果是链表的头结点，则直接table[i] = next;
            //如果是中间结点，则让entry的上一个结点的next指向entry的下一个结点
            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--;
                    //如果是链表头结点，直接将下一个结点赋值给table[i]
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    //此方法在HashMap中没有任何操作，在LinkedHashMap中会重写
                    e.recordRemoval(this);
                    return e;
                }
                prev = e;
                e = next;
            }
            return e;
        }

remove()方法的逻辑是先计算出索引值，然后遍历索引处的链表，找到与给定key相等的entry。如果entry是链表的头结点，则直接将entry的下一个结点赋值给table\[i\]；如果是链表的中间结点，则将entry的上一个结点的next指向entry的下一个结点。如果key存在，则删除后返回对应的entry，如果不存在，则返回null。所以，即使去删除HashMap中不存在的Key，也不会出现异常的。

**8.其它方法**

clear()方法：把数组的所有值置为null，size置为0，如下：

public void clear() {
            modCount++;
            Entry[] tab = table;
            //把table的所有值置为null
            for (int i = 0; i < tab.length; i++)
                tab[i] = null;
            size = 0;
        }

isEmpty()方法：判断是否为空

public boolean isEmpty() {
            return size == 0;
        }

size()方法：返回大小

public int size() {
            return size;
        }

**9.遍历哈希表**

关于哈希表的遍历用法和代码解析请参考[Java HashMap遍历方法和源代码解析][Java HashMap]

[Java HashMap]: http://blog.csdn.net/kevin_zhai/article/details/72539916