数据结构——HashMap

客官°小女子只卖身不卖艺 2022-05-23 23:51 128阅读 0赞

HashMap也是比较常用的一个集合，比如ZooKeeper中就用的比较多。而且HashMap也是面试中常被问到，今天就来探讨一下HashMap。

#### HashMap结构 ####

![这里写图片描述][70]

从上图可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。

transient Entry<K, V>[] table;
    
    public HashMap(int paramInt, float paramFloat){
       if (paramInt < 0) {
          throw new IllegalArgumentException("Illegal initial capacity: " + paramInt);
       }
        if (paramInt > 1073741824)
         paramInt = 1073741824;
        if ((paramFloat <= 0.0F) || (Float.isNaN(paramFloat))) {
         throw new IllegalArgumentException("Illegal load factor: " + paramFloat);
       }
    
        int i = 1;
        while (i < paramInt) {
           i <<= 1;
        }
        this.loadFactor = paramFloat;
        this.threshold = ((int)Math.min(i * paramFloat, 1.073742E+009F));
        this.table = new Entry[i];  //初始化数组
        this.useAltHashing = ((VM.isBooted()) && (i >= Holder.ALTERNATIVE_HASHING_THRESHOLD));
    
        init();
      }
    
    static class Entry<K, V> implements Map.Entry<K, V>{ 
        final K key;
        V value;
        Entry<K, V> next;
        int hash;
        ....
     }

从源码中可以看出，当新建一个HashMap的时候，就会初始化一个数组，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。  
**注意：在java8中HashMap稍微有些改变，当链表的长度超过8个时，会将链表转换为红黑树**

#### HashMap的存取 ####

**PUT**

/**
         * 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) {
            //其允许存放null的key和null的value，当其key为null时，调用putForNullKey方法，放入到table[0]的这个位置
            if (key == null)
                return putForNullKey(value);
            //通过调用hash方法对key进行哈希，得到哈希之后的数值。该方法实现可以通过看源码，其目的是为了尽可能的让键值对可以分不到不同的桶中
            int hash = hash(key);
            //根据上一步骤中求出的hash得到在数组中是索引i
            int i = indexFor(hash, table.length);
            //如果i处的Entry不为null，则通过其next指针不断遍历e元素的下一个元素。
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //如果key的hash值相等并且key相同说明已经存在相同的key,将新的value存入并返回旧的value
                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的时候，如果key存在了，那么新的value会代替旧的value，并且如果key存在的情况下，该方法返回的是旧的value，如果key不存在，那么返回null。  
从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标）， **如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾（java8中刚好相反，新加入的放在链尾）。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上**。

/** * 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) {
            // 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
            if ((size >= threshold) && (null != table[bucketIndex])) {
                // 2倍扩容，后面会介绍一下
                resize(2 * table.length);
                // 扩容以后，重新计算 hash 值
                hash = (null != key) ? hash(key) : 0;
                // 重新计算扩容后的新的下标
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
    }
    // 将新值放到链表的表头，然后 size++
    void createEntry(int hash, K key, V value, int bucketIndex) {
            // 获取指定 bucketIndex 索引处的 Entry
            Entry<K,V> e = table[bucketIndex];
            // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entr
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
    }

这个方法的主要逻辑就是先判断是否需要扩容，需要的话先扩容，然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。

**数组扩容**  
前面我们看到，在插入新值的时候，如果当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素，那么就会触发扩容，扩容后，数组大小为原来的 2 倍（为什么2倍后面再细说）

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, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

扩容就是用一个新的大数组替换原来的小数组，并将原来数组中的值迁移到新的数组中。  
由于是双倍扩容，迁移过程中，会将原来 table\[i\] 中的链表的所有节点，分拆到新的数组的 newTable\[i\] 和 newTable\[i + oldLength\] 位置上。如原来数组长度是 16，那么扩容后，原来 table\[0\] 处的链表中的所有元素会被分配到新数组中 newTable\[0\] 和 newTable\[16\] 这两个位置。

**hash值计算**

final int hash(Object k) {
            int h = 0;
            if (useAltHashing) {
                if (k instanceof String) {
                    return sun.misc.Hashing.stringHash32((String) k);
                }
                h = hashSeed;
            }
            //得到k的hashcode值
            h ^= k.hashCode();
            //进行计算
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
    }

hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。我们可以看到在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。  
对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

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

这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方（所以说2倍扩容也是有原因的），这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码：

// Find a power of 2 >= initialCapacity
    int capacity = 1;
        while (capacity < initialCapacity)  
            capacity <<= 1;

这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。

当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。这看上去很简单，其实比较有玄机的，我们举个例子来说明：

假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：  
h & (table.length-1) hash table.length-1  
8 & (15-1)： 0100 & 1110 = 0100  
9 & (15-1)： 0101 & 1110 = 0100  
8 & (16-1)： 0100 & 1111 = 0100  
9 & (16-1)： 0101 & 1111 = 0101

从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1（即1111），这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。  
**GET**

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
    
            return null == entry ? null : entry.getValue();
        }
        final Entry<K,V> getEntry(Object key) {
            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;
        }

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。（如果hashCode不同，equals就不用再比较了）

所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了

**HashMap遍历**  
第一种：常用，操作方便  
foreach遍历

Map< String, String> map = new HashMap<>();
    for(Map.Entry<String, String> entry : map.entrySet()){
    
           String key= "+entry.getKey() String value= "+entry.getValue());
       }

第二种：常用，效率高，推荐这种，特别是容量大的时候

Map< String, String> map = new HashMap<>();
    　　Iterator iter = map.entrySet().iterator();
    　　while (iter.hasNext()) {
    　　Map.Entry entry = (Map.Entry) iter.next();
    　　String key = entry.getKey();
    　　String val = entry.getValue();
    　　}

第三种：效率低，不推荐使用

Map< String, String> map = new HashMap<>();
    　　Iterator iter = map.keySet().iterator();
    　　while (iter.hasNext()) {
    　　String key = iter.next();
    　　String val = map.get(key);
    　　}

**HashMap缺点：**  
HashMap不支持并发操作，所以不适用与多线程环境。在高并发状态下，如果产生同时put操作，并且在put时刚好遇上要扩容，可能会形成链环，如果get的key的hashcode值刚好在链环的位置，而这个key对应的值为 null或不存在，就会进入死循环，耗尽cpu内存。可以用ConcurrentHashMap解决这个问题。

参考博客：[李大辉博客][Link 1]  
[http://www.importnew.com/28263.html][http_www.importnew.com_28263.html]

[70]: /images/20220524/006e5697cbeb40c09d754a170f02dfdb.png
[Link 1]: http://tracylihui.github.io/2015/07/01/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A01%EF%BC%9AHashMap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/
[http_www.importnew.com_28263.html]: http://www.importnew.com/28263.html