技术学习分享_CKX技术 技术资讯 HashMap源码,看我这篇就够了

HashMap源码,看我这篇就够了

广告位

HashMap源码深度剖析

 * HashMap底层数据结构(为什么引入红黑树、存储数据的过程、哈希碰撞相关问题)  * HashMap成员变量(初始化容量是多少、负载因子、数组长度为什么是2的n次幂)  * HashMap扩容机制(什么时候需要扩容? 怎么进行扩容?)  * JDK7 与 Jdk8比较,JDK8进行了什么优化? 

1 定义

HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

  • JDK1.7 HashMap数据结构:数组 + 链表
  • JDK1.8 HashMap数据结构:数组 + 链表 / 红黑树

思考:为什么1.8之后,HashMap的数据结构要增加红黑树?

2 哈希表

Hash表也称为散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key – value)而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中的一个位置来访问记录,以此来加快查找的速度。在链表、数组等数据结构中,查找某个关键字,通常要遍历整个数据结构,也就是O(N)的时间级,但是对于哈希表来说,只是O(1)的时间级

哈希表,它是通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做**散列表,只需要O(1)**的时间级

HashMap源码,看我这篇就够了

思考:多个 key 通过散列函数会得到相同的值,这时候怎么办?

解决:

​ (1)开放地址法

​ (2)链地址法

HashMap源码,看我这篇就够了 对于开放地址法,可能会遇到二次冲突,三次冲突,所以需要良好的散列函数,分布的越均匀越好。对于链地址法,虽然不会造成二次冲突,但是如果一次冲突很多,那么会造成子数组或者子链表很长,那么我们查找所需遍历的时间也会很长。

3 JDK1.8前HashMap的数据结构

  • JDK 8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。
  • 当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,极端情况HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。

HashMap源码,看我这篇就够了

4 JDK1.8后HashMap的数据结构

  • JDK 8 后 HashMap 的实现是 数组+链表+红黑树
  • 桶中的结构可能是链表,也可能是红黑树,当链表长度大于阈值(或者红黑树的边界值,默认为8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。

HashMap源码,看我这篇就够了

5. 类构造器

public class HashMap<K,V> extends AbstractMap<K,V>     implements Map<K,V>, Cloneable, Serializable { 

HashMap源码,看我这篇就够了  JDK 为我们提供了一个抽象类 AbstractMap ,该抽象类继承 Map 接口,所以如果我们不想实现所有的 Map 接口方法,就可以选择继承抽象类 AbstractMap 。

HashMap 集合实现了 Cloneable 接口以及 Serializable 接口,分别用来进行对象克隆以及将对象进行序列化。

注意:HashMap 类即继承了 AbstractMap 接口,也实现了 Map 接口,这样做难道不是多此一举?

据 java 集合框架的创始人Josh Bloch描述,这样的写法是一个失误。在java集合框架中,类似这样的写法很多,最开始写java集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。 

6 字段属性

	//序列化和反序列化时,通过该字段进行版本一致性验证     private static final long serialVersionUID = 362498820763181265L;     //默认 HashMap 集合初始容量为16(必须是 2 的倍数)     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16     //集合的最大容量,如果通过带参构造指定的最大容量超过此数,默认还是使用此数     static final int MAXIMUM_CAPACITY = 1 << 30;     //默认的填充因子     static final float DEFAULT_LOAD_FACTOR = 0.75f;     //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)     static final int TREEIFY_THRESHOLD = 8;     //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)     static final int UNTREEIFY_THRESHOLD = 6;     /**(JDK1.8新增)      * 当集合中的容量大于这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,      * 而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD      */     static final int MIN_TREEIFY_CAPACITY = 64;  	/**      * 初始化使用,长度总是 2的幂      */     transient Node<K,V>[] table;      /**      * 保存缓存的entrySet()      */     transient Set<Map.Entry<K,V>> entrySet;      /**      * 此映射中包含的键值映射的数量。(集合存储键值对的数量)      */     transient int size;      /**      * 跟前面ArrayList和LinkedList集合中的字段modCount一样,记录集合被修改的次数      * 主要用于迭代器中的快速失败      */     transient int modCount;      /**      * 调整大小的下一个大小值(容量*加载因子)。capacity * load factor      */     int threshold;      /**      * 散列表的加载因子。      */     final float loadFactor; 

 下面我们重点介绍上面几个字段:

  ①、Node<K,V>[] table

  我们说 HashMap 是由数组+链表+红黑树组成,这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 声明数组的长度总是 2的n次方(一定是合数),为什么这里要求是合数,一般我们知道哈希算法为了避免冲突都要求长度是质数,这里要求是合数,下面在介绍 HashMap 的hashCode() 方法(散列函数),我们再进行讲解。

  ②**、size**

  集合中存放key-value 的实时对数。

  ③、loadFactor

  装载因子,是用来衡量 HashMap 满的程度,计算HashMap的实时装载因子的方法为:size/capacity,而不是占用桶的数量去除以capacity。capacity 是桶的数量,也就是 table 的长度length。

  默认的负载因子0.75 是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor 的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子 loadFactor 的值,这个值可以大于1。

  ④、threshold

  计算公式:capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容),扩容后的 HashMap 容量是之前容量的两倍

7 构造函数

①、默认无参构造函数

/**      * 默认构造函数,初始化加载因子loadFactor = 0.75      */     public HashMap() {         this.loadFactor = DEFAULT_LOAD_FACTOR;      } 

②、指定初始容量的构造函数

/**      *      * @param initialCapacity 指定初始化容量      * @param loadFactor 加载因子 0.75      */     public HashMap(int initialCapacity, float loadFactor) {         //初始化容量不能小于 0 ,否则抛出异常         if (initialCapacity < 0)             throw new IllegalArgumentException("Illegal initial capacity: " +                                                initialCapacity);         //如果初始化容量大于2的30次方,则初始化容量都为2的30次方         if (initialCapacity > MAXIMUM_CAPACITY)             initialCapacity = MAXIMUM_CAPACITY;         //如果加载因子小于0,或者加载因子是一个非数值,抛出异常         if (loadFactor <= 0 || Float.isNaN(loadFactor))             throw new IllegalArgumentException("Illegal load factor: " +                                                loadFactor);         this.loadFactor = loadFactor;         this.threshold = tableSizeFor(initialCapacity);     }     // 返回大于等于initialCapacity的最小的二次幂数值。     // >>> 操作符表示无符号右移,高位取0。     // | 按位或运算     static final int tableSizeFor(int cap) {         int n = cap - 1;         n |= n >>> 1;         n |= n >>> 2;         n |= n >>> 4;         n |= n >>> 8;         n |= n >>> 16;         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;     } 

8 确定哈希桶数组索引位置

前面我们讲解哈希表的时候,我们知道是用散列函数来确定索引的位置。散列函数设计的越好,使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合,我们希望在有限个数组位置时,尽量每个位置的元素只有一个,那么当我们用散列函数求得索引位置的时候,我们能马上知道对应位置的元素是不是我们想要的,而不是要进行链表的遍历或者红黑树的遍历,这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法:

static final int hash(Object key) {         int h;         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);     }          i = (table.length - 1) & hash;//这一步是在后面添加元素putVal()方法中进行位置的确定 

主要分为三步:

  ①、取 hashCode 值: key.hashCode()

  ②、高位参与运算:h>>>16

  ③、取模运算:(n-1) & hash

  这里获取 hashCode() 方法的值是变量,但是我们知道,对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

  为了让数组元素分布均匀,我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length),但是计算机都是二进制进行操作,取模运算相对开销还是很大的,那该如何优化呢?

  HashMap 使用的方法很巧妙,它通过 hash & (table.length -1)来得到该对象的保存位,前面说过 HashMap 底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当 length 总是2的n次方时,hash & (length-1)运算等价于对 length 取模,也就是 hash%length,但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

  这也解释了为什么要保证数组的长度总是2的n次方。

  再就是在 JDK1.8 中还有个高位参与运算,hashCode() 得到的是一个32位 int 类型的值,通过hashCode()的高16位 异或 低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

  下面举例说明下,n为table的长度:

HashMap源码,看我这篇就够了

9 添加元素

//hash(key)就是上面讲的hash方法,对其进行了第一步和第二步处理     public V put(K key, V value) {         return putVal(hash(key), key, value, false, true);     }     /**      *      * @param hash 索引的位置      * @param key  键      * @param value  值      * @param onlyIfAbsent true 表示不要更改现有值      * @param evict false表示table处于创建模式      * @return      */     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,             boolean evict) {          Node<K,V>[] tab; Node<K,V> p; int n, i;          //如果table为null或者长度为0,则进行初始化          //resize()方法本来是用于扩容,由于初始化没有实际分配空间,这里用该方法进行空间分配,后面会详细讲解该方法          if ((tab = table) == null || (n = tab.length) == 0)              n = (tab = resize()).length;          //注意:这里用到了前面讲解获得key的hash码的第三步,取模运算,下面的if-else分别是 tab[i] 为null和不为null          if ((p = tab[i = (n - 1) & hash]) == null)              tab[i] = newNode(hash, key, value, null);//tab[i] 为null,直接将新的key-value插入到计算的索引i位置          else {//tab[i] 不为null,表示该位置已经有值了              Node<K,V> e; K k;              if (p.hash == hash &&                  ((k = p.key) == key || (key != null && key.equals(k))))                  e = p;//节点key已经有值了,直接用新值覆盖              //该链是红黑树              else if (p instanceof TreeNode)                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);              //该链是链表              else {                  for (int binCount = 0; ; ++binCount) {                      if ((e = p.next) == null) {                          p.next = newNode(hash, key, value, null);                          //链表长度大于8,转换成红黑树                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                              treeifyBin(tab, hash);                          break;                      }                      //key已经存在直接覆盖value                      if (e.hash == hash &&                          ((k = e.key) == key || (key != null && key.equals(k))))                          break;                      p = e;                  }              }              if (e != null) { // existing mapping for key                  V oldValue = e.value;                  if (!onlyIfAbsent || oldValue == null)                      e.value = value;                  afterNodeAccess(e);                  return oldValue;              }          }          ++modCount;//用作修改和新增快速失败          if (++size > threshold)//超过最大容量,进行扩容              resize();          afterNodeInsertion(evict);          return null;     } 

①、判断键值对数组 table 是否为空或为null,否则执行resize()进行扩容;

②、根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③、判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④、判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤、遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥、插入成功后,判断实际存在的键值对数量size是否超过了最大容量threshold,如果超过,进行扩容。

⑦、如果新插入的key不存在,则返回null,如果新插入的key存在,则返回原key对应的value值(注意新插入的value会覆盖原value值)

注意1:其中代码:

if (++size > threshold)//超过最大容量,进行扩容     resize(); 

这里有个考点,我们知道 HashMap 是由数组+链表+红黑树(JDK1.8)组成,如果在添加元素时,发生冲突,会将冲突的数放在链表上,当链表长度超过8时,会自动转换成红黑树。

  那么有如下问题:数组上有5个元素,而某个链表上有3个元素,问此HashMap的 size 是多大?

  我们分析代码,很容易知道,只要是调用put() 方法添加元素,那么就会调用 ++size(这里有个例外是插入重复key的键值对,不会调用,但是重复key元素不会影响size),所以,上面的答案是 7。

10 扩容机制

扩容(resize),我们知道集合是由数组+链表+红黑树构成,向 HashMap 中插入元素时,如果HashMap 集合的元素已经大于了最大承载容量threshold(capacity * loadFactor),这里的threshold不是数组的最大长度。那么必须扩大数组的长度,Java中数组是无法自动扩容的,我们采用的方法是用一个更大的数组代替这个小的数组,就好比以前是用小桶装水,现在小桶装不下了,我们使用一个更大的桶。

JDK1.8融入了红黑树的机制,比较复杂,这里我们先介绍 JDK1.7的扩容源码,便于理解,然后在介绍JDK1.8的源码。

//参数 newCapacity 为新数组的大小     void resize(int newCapacity) {         Entry[] oldTable = table;//引用扩容前的 Entry 数组         int oldCapacity = oldTable.length;         if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了             threshold = Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1),这样以后就不会扩容了             return;         }          Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组         transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面         table = newTable;         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值     }     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;//访问下一个 Entry 链上的元素             }         }     } 

通过方法我们可以看到,JDK1.7中首先是创建一个新的大容量数组,然后依次重新计算原集合所有元素的索引,然后重新赋值。如果数组某个位置发生了hash冲突,使用的是单链表的头插入方法,同一位置的新元素总是放在链表的头部,这样与原集合链表对比,扩容之后的可能就是倒序的链表了。

下面我们在看看JDK1.8的。

final Node<K,V>[] resize() {         Node<K,V>[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组如果为null,则长度赋值0         int oldThr = threshold;         int newCap, newThr = 0;         if (oldCap > 0) {//如果原数组长度大于0             if (oldCap >= MAXIMUM_CAPACITY) {//数组大小如果已经大于等于最大值(2^30)                 threshold = Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1),这样以后就不会扩容了                 return oldTab;             }             //原数组长度大于等于初始化长度16,并且原数组长度扩大1倍也小于2^30次方             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                 newThr = oldThr << 1; // 阀值扩大1倍         }         else if (oldThr > 0) //旧阀值大于0,则将新容量直接等于就阀值             newCap = oldThr;         else {//阀值等于0,oldCap也等于0(集合未进行初始化)             newCap = DEFAULT_INITIAL_CAPACITY;//数组长度初始化为16             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阀值等于16*0.75=12         }         //计算新的阀值上限         if (newThr == 0) {             float ft = (float)newCap * loadFactor;             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                       (int)ft : Integer.MAX_VALUE);         }         threshold = newThr;         @SuppressWarnings({"rawtypes","unchecked"})             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];         table = newTab;         if (oldTab != null) {             //把每个bucket都移动到新的buckets中             for (int j = 0; j < oldCap; ++j) {                 Node<K,V> e;                 if ((e = oldTab[j]) != null) {                     oldTab[j] = null;//元数据j位置置为null,便于垃圾回收                     if (e.next == null)//数组没有下一个引用(不是链表)                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)//红黑树                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                     else { // preserve order                         Node<K,V> loHead = null, loTail = null;                         Node<K,V> hiHead = null, hiTail = null;                         Node<K,V> next;                         do {                             next = e.next;                             //原索引                             if ((e.hash & oldCap) == 0) {                                 if (loTail == null)                                     loHead = e;                                 else                                     loTail.next = e;                                 loTail = e;                             }                             //原索引+oldCap                             else {                                 if (hiTail == null)                                     hiHead = e;                                 else                                     hiTail.next = e;                                 hiTail = e;                             }                         } while ((e = next) != null);                         //原索引放到bucket里                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;                         }                         //原索引+oldCap放到bucket里                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         return newTab;     } 

该方法分为两部分,首先是计算新桶数组的容量 newCap 和新阈值 newThr,然后将原集合的元素重新映射到新集合中。

HashMap源码,看我这篇就够了 相比于JDK1.7,1.8使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

11 删除元素

HashMap 删除元素首先是要找到 桶的位置,然后如果是链表,则进行链表遍历,找到需要删除的元素后,进行删除;如果是红黑树,也是进行树的遍历,找到元素删除后,进行平衡调节,注意,当红黑树的节点数小于 6 时,会转化成链表。

public V get(Object key) {         Node<K,V> e;         return (e = getNode(hash(key), key)) == null ? null : e.value;     }      final Node<K,V> getNode(int hash, Object key) {         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;         if ((tab = table) != null && (n = tab.length) > 0 &&             (first = tab[(n - 1) & hash]) != null) {             //根据key计算的索引检查第一个索引             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 return first;             //不是第一个节点             if ((e = first.next) != null) {                 if (first instanceof TreeNode)//遍历树查找元素                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);                 do {                     //遍历链表查找元素                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);             }         }         return null;     } 

12 查找元素

①、通过 key 查找 value

首先通过 key 找到计算索引,找到桶位置,先检查第一个节点,如果是则返回,如果不是,则遍历其后面的链表或者红黑树。其余情况全部返回 null。

public V get(Object key) {         Node<K,V> e;         return (e = getNode(hash(key), key)) == null ? null : e.value;     }      final Node<K,V> getNode(int hash, Object key) {         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;         if ((tab = table) != null && (n = tab.length) > 0 &&             (first = tab[(n - 1) & hash]) != null) {             //根据key计算的索引检查第一个索引             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 return first;             //不是第一个节点             if ((e = first.next) != null) {                 if (first instanceof TreeNode)//遍历树查找元素                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);                 do {                     //遍历链表查找元素                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);             }         }         return null;     } 

总结

  ①、基于JDK1.8的HashMap是由数组+链表+红黑树组成,当链表长度超过 8 时会自动转换成红黑树,当红黑树节点个数小于 6 时,又会转化成链表。相对于早期版本的 JDK HashMap 实现,新增了红黑树作为底层数据结构,在数据量较大且哈希碰撞较多时,能够极大的增加检索的效率。

  ②、允许 key 和 value 都为 null。key 重复会被覆盖,value 允许重复。

  ③、非线程安全

  ④、无序(遍历HashMap得到元素的顺序不是按照插入的顺序)

本文由传智教育博学谷教研团队发布。

如果本文对您有帮助,欢迎关注点赞;如果您有任何建议也可留言评论私信,您的支持是我坚持创作的动力。

转载请注明出处!

本文来自网络,不代表技术学习分享_CKX技术立场,转载请注明出处。

作者: CKX技术

上一篇
下一篇
广告位

发表回复

返回顶部