基于源码(jdk1.7)对HashMap的get()和put()的小结

迷南。 2022-06-01 11:12 152阅读 0赞

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

## HashMap的概述 ##

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

Map m = Collections.synchronizedMap(new HashMap(…));由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

此类是 Java Collections Framework 的成员。

## 源码 ##

##  ##

#### \- HashMap的桶(容量) ####

// 默认的初始桶(容量)是16，每次扩容都是x2
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
     // 最大容量为（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换） 
        static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子为0.75,
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。

下面说下加载因子，如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方.

#### \- HashMap的key和value可以为null ####

##### get()方法 #####

// 获取key对应的value 
     public V get(Object key) {
            if (key == null)
                //如果key为null,调用getForNullKey()
                return getForNullKey();
            //key不为null,调用getEntry(key);
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
    }
     //当key为null时,获取value
        private V getForNullKey() {
            if (size == 0) {
                return null;//链表为空,返回null
            }
        //链表不为空,将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
    
    //key不为null,获取value
    final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
       //判断链表中是否有值
             //链表中没值,也就是没有value
                return null;
            }
           //链表中有值,获取key的hash值 
            int hash = (key == null) ? 0 : hash(key);
            // 在“该hash值对应的链表”上查找“键值等于key”的元素 
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                //判断key是否相同
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;//key相等,返回相应的value
                 }
            return null;//链表中没有相应的key
        }

首先，如果key为null，则直接从哈希表的第一个位置table\[0\]对应的链表上查找。记住，key为null的键值对永远都放在以table\[0\]为头结点的链表中，当然不一定是存放在头结点table\[0\]中。  
如果key不为null，则先求的key的hash值，根据hash值找到在table中的索引，在该索引对应的单链表中查找是否有键值对的key与目标key相等，有就返回对应的value，没有则返回null。

##### put() #####

// 将“key-value”添加到HashMap中 
      public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)// 若“key为null”，则将该键值对添加到table[0]中。 
                return putForNullKey(value); 
          // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。 
            int hash = hash(key);//获取key的hash值
            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))) {
                 // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
       // 若“key”对应的键值对不存在，则将“key-value”添加到table中 
            modCount++;
       //将key-value添加到table[i]处
            addEntry(hash, key, value, i);
            return null;
        }

如果key为null，则将其添加到table\[0\]对应的链表中，putForNullKey的源码如下

// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 
    private V putForNullKey(V value) {
            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;
                }
            }
     // 如果没有存在key为null的键值对，则直接添加到table[0]处! 
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }

如果key不为null，则同样先求出key的hash值，根据hash值得出在table中的索引，而后遍历对应的单链表，如果单链表中存在与目标key相等的键值对，则将新的value覆盖旧的value，比将旧的value返回，如果找不到与目标key相等的键值对，或者该单链表为空，调用addEntry()方法将该键值对插入到改单链表的头结点位置（每次新插入的节点都是放在头结点的位置）.  
如果key为null,调用putForNullKey(),直接去遍历table\[0\]Entry链表，寻找e.key==null的Entry或者没有找到遍历结束.如果找到了e.key==null，就保存null值对应的原值oldValue，然后覆盖原值，并返回oldValue  
如果在putForNullKey()中,在table\[0\]Entry链表中没有找到也会调用addEntry方法添加一个key为null的Entry.  
下面是addEntry的源码：

void addEntry(int hash, K key, V value, int bucketIndex) {
     //先判断大小 
      if ((size >= threshold) && (null != table[bucketIndex])) {
     // 若HashMap的实际大小不小于 “阈值”，则调整HashMap的大小 
                resize(2 * table.length);//扩容,每次增长2倍
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
           createEntry(hash, key, value, bucketIndex);//新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。 
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
          // 保存“bucketIndex”位置的值到“e”中 
            Entry<K,V> e = table[bucketIndex];
        // 设置“bucketIndex”位置的元素为“新Entry”， 
        // 设置“e”为“新Entry的下一个节点” 
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;

注意这里new Entry<>()的构造方法，将key-value键值对赋给table\[bucketIndex\]，并将其next指向元素e，这便将key-value放到了头结点中，并将之前的头结点接在了它的后面。该方法也说明，每次put键值对的时候，总是将新的该键值对放在table\[bucketIndex\]处（即头结点处）。  
同时也要注意,这个方法首先会判断是否要扩容，当现在的HashMap中的Entry数大于等于扩容临界值（capacity\*load factor）并且index对应的地方没有Entry就扩容.HashMap每次扩容的大小为2倍原容量，默认容量为16，hashmap的capacity会一直是2的整数幂。

// 重新调整HashMap的大小，newCapacity是调整后的单位 
    void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
            //旧容量不小于最大容量(一般不会发生,反正我没遇到过)
                threshold = Integer.MAX_VALUE;
                return;
            }
         //一般扩容
        // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中， 
        // 然后，将“新HashMap”赋值给“旧HashMap”。 
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }

很明显，是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。transfer方法的源码如下

// 将HashMap中的全部元素都添加到newTable中 
    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

遍历原表table ，从table\[0\]开始，e=table\[0\]，不为null就创建一个临时Entry next引用e.的下一个Entry，然后把e放到新表中，头插到table\[i\]中，i由indexFor方法决定i(h&newCapacity)，然后让e=next，继续遍历拷贝。  
扩容之后继续插入要插入的Entry，这个时候就要重新hash了，因为旧表已经扩容了,若果key为nul任然是0。  
然后进行真正的插入，调用 createEntry(hash, key, value, bucketIndex)，下面是源码：

void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }
    //进行头插，创建一个新的entry，
     Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }

新的entry复制到table\[bucketIndex\]，并next引用原来的table\[bucketIndex\]，完成。  
……..  
仅仅只是HashMap的普通扩容,就这么麻烦,如果再加上线程安全,而加同步的话,那么效率可想而知.并且,HashMap在高并发场景下调用transfer方法，可能会出现环形链表，导致程序死循环.  
所以,怎么解决HashMap的线程安全问题,同时又能保证效率呢?

[SouthEast]: /images/20220601/322b34e6cfbb4cb18e9be6db8aa5e9b5.png