HashMap源码分析

HashMap源码分析

请注意,本文编写于  1,192  天前,最后修改于  723  天前,其中某些信息可能已经过时。

`HashMap`最早出现在JDK1.2中,底层基于散列算法(Hash)实现。并且`HashMap`允许null键和null值,是线程非安全类,在多线程环境下可能会存在问题,与之对应的是`HashTable`类,`HashTable`是线程安全的`HashMap`,但是在之前由于HashTable方法都是用`synchronized`实现,开销比较大,所以在多线程时反而并不使用`HashTable`,而是使用`CurrentHashMap`。在JDK1.8后,`HashMap`和`CurrentHashMap`的数据结构都有了新变化,即加入了红黑树

JDK1.7及之前版本中的HashMap数据结构

在JDK1.6,1.7中,HashMap都是基于“拉链法”实现,即数组+链表的形式,通过不同的hash值来对键分配不同的桶(bucket)。关于更多1.7版本及之前的HashMap数据结构可以参考我的另一篇博客Java中的容器

JDK1.8版本的HashMap数据结构

在JDK1.8中对HashMap的源码进行了优化,在JDK1.7中,HashMap处理“碰撞”的时候,都是采用链表来存储,当碰撞的节点很多的时候,查询时间复杂度从原来的O(1)变成了O(N)。而JDK1.8中,为了优化这种情况,HashMap处理“碰撞”增加了红黑树这种数据结构,当碰撞节点较少时,采样链表存储,当较大(默认是超过8)时,变成使用红黑树(特点是查询时间是O(logN))存储。

结构

Node是HashMap中的一个静态内部类:

//Node是单向链表,实现了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
 	final int hash; //哈希
 	final K key;  //键值对
   V value;
 	Node<K,V> next;  //下一个节点
    
	 //构造函数
  Node(int hash, K key, V value, Node<K,V> next) {
	 this.hash = hash;
 	 this.key = key;
 	 this.value = value;
 	 this.next = next;
 	}

 	// getter and setter ... toString ...
 	public final K getKey() { return key; }
 	public final V getValue() { return value; }
 	public final String toString() { return key + "=" + value; }

	public final int hashCode() {
 	return Objects.hashCode(key) ^ Objects.hashCode(value);
   }

 public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
 }

 public final boolean equals(Object o) {
 	if (o == this)
 	   return true;
 	if (o instanceof Map.Entry) {
 	   Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 	if (Objects.equals(key, e.getKey()) &&
 	   Objects.equals(value, e.getValue()))
 	   return true;
  }
    return false;
  }
}

TreeNode是红黑树的数据结构:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
 	TreeNode<K,V> parent; // red-black tree links
 	TreeNode<K,V> left;
 	TreeNode<K,V> right;
 	TreeNode<K,V> prev; // needed to unlink next upon deletion
 	boolean red;
 	TreeNode(int hash, K key, V val, Node<K,V> next) {
 	super(hash, key, val, next);
 }

 /**
     * Returns root of tree containing this node.
     */
 final TreeNode<K,V> root() {
 	for (TreeNode<K,V> r = this, p;;) {
 		if ((p = r.parent) == null)
 			return r;
         r = p;
 	}
 }

类定义

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

变量

/**
 * 默认初始容量16(必须是2的幂次方)
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * 最大容量,2的30次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认加载因子,用来计算threshold
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表转成树的阈值,当桶中链表长度大于8时转成树 
   threshold = capacity * loadFactor
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 进行resize操作时,若桶中数量少于6则从树转成链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶中结构转化为红黑树对应的table的最小大小
   当需要将解决 hash 冲突的链表转变为红黑树时,
   需要判断下此时数组容量,
   若是由于数组容量太小(小于 MIN_TREEIFY_CAPACITY )
   导致的 hash 冲突太多,则不进行链表转变为红黑树操作,
   转为利用 resize() 函数对 hashMap 扩容
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 保存Node<K,V>节点的数组
 该表在首次使用时初始化,并根据需要调整大小。 分配时,
 长度始终是2的幂。
 */
transient Node<K,V>[] table;

/**
 * 存放具体元素的集
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 记录 hashMap 当前存储的元素的数量
 */
transient int size;

/**
 * 每次更改map结构的计数器
 */
transient int modCount;

/**
 * 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
 */
int threshold;

/**
 * 负载因子:要调整大小的下一个大小值(容量*加载因子)。
 */
final float loadFactor;

构造方法

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0,否则报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    // 初始容量不能大于最大值,否则为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    //负载因子不能小于或等于0,不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    // 初始化负载因子                                        
    this.loadFactor = loadFactor;
    
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);    
}

public HashMap(int initialCapacity) {
    // 调用HashMap(int, float)型构造函数
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    // 初始化填充因子,此处说明HashMap也是采用延迟加载的方式,首次使用时才会进行加载
    this.loadFactor = DEFAULT_LOAD_FACTOR;
        
public HashMap(Map<? extends K, ? extends V> m) {
    // 初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将m中的所有元素添加至HashMap中
    putMapEntries(m, false);
}
    
//putMapEntries(Map m, boolean evict)函数将m的所有元素存入本HashMap实例中。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
   // 判断table是否已经初始化
   if (table == null) { // pre-size
       // 未初始化,s为m的实际元素个数
       float ft = ((float)s / loadFactor) + 1.0F;
       int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值,则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化,并且m元素个数大于阈值,进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

tableSizeFor方法详解

用位运算找到大于或等于cap的最小2的整次幂的数,比如10,则返回16。

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;
    }
  1. 让cap-1再赋值给n的目的是使得找到的目标值大于或等于原值。例如二进制0100,十进制是4,若不减1而直接操作,答案是0001 0000十进制是16,明显不符合预期。
  2. 对n右移1位:001xx…xxx,再位或:011xx…xxx
  3. 对n右移2位:00011…xxx,再位或:01111…xxx
  4. 对n右移4位…
  5. 对n右移8位…
  6. 对n右移16位,因为int最大就2^32所以移动1、2、4、8、16位并取位或,会将最高位的1后面的位全变为1。
  7. 再让结果n+1,即得到了2的整数次幂的值了。

附带一个实例:

loadFactory负载因子

对于HashMap来说,负载因子是一个很重要的参数,该参数反应了HashMap桶数组的使用情况,通过调节负载因子,可以使HashMap时间和空间复杂度上有不同的表现。

当我们调低负载因子时,HashMap 所能容纳的键值对数量变少。扩容时,重新将键值对存储新的桶数组里,键的键之间产生的碰撞会下降,链表长度变短。此时,HashMap 的增删改查等操作的效率将会变高,这里是典型的拿空间换时间。

相反,如果增加负载因子(负载因子可以大于1),HashMap 所能容纳的键值对数量变多,空间利用率高,但碰撞率也高。这意味着链表长度变长,效率也随之降低,这种情况是拿时间换空间。至于负载因子怎么调节,这个看使用场景了。

一般情况下,我们用默认值就可以了。大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。

查找

public V get(Object key) {
   Node<K,V> e;
   return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// HashMap中的Hash方法
static final int hash(Object key) {
   int h;
 // 拿到key的hash值后与其无符号右移16位取“与”
 // 这种方式能混合原始hash值的高位和低位,并且混合后的低位混杂了高位的特征
 // 主要是考虑数组的table的length比较小的时候也能保证考虑到高低bit都能参与到hash中,并且效率很高
 // 通过这种方式,让高位数据与低位数据进行异或,以此加大低位信息的随机性,变相的让高位数据参与到计算中。
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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) {
 // 判断桶中第一项(数组元素)相等
 if (first.hash == hash && // always check first node
     ((k = first.key) == key || (key != null && key.equals(k))))
 		return first;
 // 桶中不止一个结点
 if ((e = first.next) != null) {
 // 是否是红黑树,是的话调用getTreeNode方法
 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;
}
HashMap:如何有效减少碰撞
  1. 扰动函数:促使元素位置分布均匀,减少碰撞几率
  2. 使用final对象,并采用合适的equals()和hashCode()方法

注意:

  1. HashMap的hash算法(hash()方法)。
  2. (n - 1) &amp; hash等价于对 length 取余。

添加

public V put(K key, V value) {
   // 调用hash(key)方法来计算hash 
   return putVal(hash(key), key, value, false, true);
}

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为空,则调用resize()方法来初始化容器,并且resize()方法可以扩容
   if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
   //确定元素存放在哪个桶中,桶为空,新生成结点放入桶中
   if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
   else {
   Node<K,V> e; K k;
   // 比较桶中第一个元素(数组中的结点)的hash值相等,key相等
   if (p.hash == hash &&  ((k = p.key) == key || (key != null && key.equals(k))))
   //如果键的值以及节点 hash 等于链表中的第一个键值对节点时,则将 e 指向该键值对
       e = p;
   // 如果桶中的引用类型为 TreeNode,则调用红黑树的插入方法
   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);
   // 如果结点数量达到阈值,转化为红黑树
   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
       treeifyBin(tab, hash);
       break;
    }
   // 判断链表中结点的key值与插入的元素的key值是否相等
   if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))
        break;
        p = e;
      }
   }
   //判断要插入的键值对是否存在 HashMap 中
   if (e != null) { // existing mapping for key
       V oldValue = e.value;
   // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
   if (!onlyIfAbsent || oldValue == null)
       e.value = value;
       afterNodeAccess(e);
       return oldValue;
    }
 }
   ++modCount;
   // 键值对数量超过阈值时,则进行扩容
   if (++size > threshold)
     resize();
     afterNodeInsertion(evict);
     return null;
}

事实上,new HashMap();完成后,如果没有put操作,是不会分配存储空间的。

HashMap:put方法的逻辑

  1. 如果HashMap未被初始化过,则初始化
  2. 对key求hash值,然后再计算下标
  3. 如果没有碰撞,直接放入桶中
  4. 如果碰撞了,以链表的方式链接到后面
  5. 如果链表长度超过阈值,就把链表转换成红黑树
  6. 如果链表的长度低于6,就把红黑树转回链表
  7. 如果节点已经存在就替换旧值
  8. 如果桶满了(容量16*负载因子0.75),就需要resize(扩容2倍后重排)

扩容机制

在 HashMap 中,桶数组的长度均是2的幂,阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时,进行扩容。 HashMap 按当前桶数组长度的2倍进行扩容,阈值也变为原来的2倍(如果计算过程中,阈值溢出归零,则按阈值公式重新计算)。扩容之后,要重新计算键值对的位置,并把它们移动到合适的位置上去。

final Node<K,V>[] resize() {
 // 拿到数组桶
 Node<K,V>[] oldTab = table;
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 int oldThr = threshold;
 int newCap, newThr = 0;
 // 如果数组桶的容量大与0
 if (oldCap > 0) {
 // 如果比最大值还大,则赋值为最大值
 if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
 return oldTab;
 }
 // 如果扩容后小于最大值 而且 旧数组桶大于初始容量16, 阈值左移1(扩大2倍)
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
 }
 // 如果数组桶容量<=0 且 旧阈值 >0
 else if (oldThr > 0) // initial capacity was placed in threshold
 // 新容量=旧阈值
        newCap = oldThr;
 // 如果数组桶容量<=0 且 旧阈值 <=0
 else { // zero initial threshold signifies using defaults
 // 新容量=默认容量
        newCap = DEFAULT_INITIAL_CAPACITY;
 // 新阈值= 负载因子*默认容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 // 如果新阈值为0
 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) {
 for (int j = 0; j < oldCap; ++j) {
 Node<K,V> e;
 if ((e = oldTab[j]) != null) {
                oldTab[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;
 }
 else {
 if (hiTail == null)
     hiHead = e;
 else
     hiTail.next = e;
     hiTail = e;
   }
 } while ((e = next) != null);
 // 将分组后的链表映射到新桶中
 if (loTail != null) {
     loTail.next = null;
     newTab[j] = loHead;
 }
 if (hiTail != null) {
     hiTail.next = null;
     newTab[j + oldCap] = hiHead;
 		}
 	   }
 	  }
    }
 }
 	return newTab;
}
说明:进行扩容,会伴随着一次重新hash分配,并且会遍历hash表中所有的元素,是非常耗时的。在编写程序中,要尽量避免resize。

HashMap扩容问题:

  1. 多线程环境下,调整大小会存在条件竞争,容易造成死锁
  2. rehashing是一个比较耗时的过程

整体步骤:

  1. 计算新桶数组的容量 newCap 和新阈值 newThr
  2. 根据计算出的 newCap 创建新的桶数组,桶数组 table 也是在这里进行初始化的
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型,则需要拆分红黑树。如果是普通节点,则节点按原顺序进行分组。

总结起来,一共有三种扩容方式

  1. 使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12
  2. 指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold,接着threshold = 当前的容量(threshold) * DEFAULT_LOAD_FACTOR
  3. HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍。

细心点的人会很好奇,为什么要判断loadFactor为0呢?

loadFactor小数位为 0,整数位可被2整除且大于等于8时,在某次计算中就可能会导致 newThr 溢出归零。

疑问和进阶

1. JDK1.7是基于数组+单链表实现(为什么不用双链表)

首先,用链表是为了解决hash冲突。

单链表能实现为什么要用双链表呢?(双链表需要更大的存储空间)

2. 为什么要用红黑树,而不用平衡二叉树?

插入效率比平衡二叉树高,查询效率比普通二叉树高。所以选择性能相对折中的红黑树。

3. 重写对象的Equals方法时,要重写hashCode方法,为什么?跟HashMap有什么关系?

equals与hashcode间的关系:

  1. 如果两个对象相同(即用equals比较返回true),那么它们的hashCode值一定要相同;
  2. 如果两个对象的hashCode相同,它们并不一定相同(即用equals比较返回false)

因为在 HashMap 的链表结构中遍历判断的时候,特定情况下重写的 equals 方法比较对象是否相等的业务逻辑比较复杂,循环下来更是影响查找效率。所以这里把 hashcode 的判断放在前面,只要 hashcode 不相等就玩儿完,不用再去调用复杂的 equals 了。很多程度地提升 HashMap 的使用效率。

所以重写 hashcode 方法是为了让我们能够正常使用 HashMap 等集合类,因为 HashMap 判断对象是否相等既要比较 hashcode 又要使用 equals 比较。而这样的实现是为了提高 HashMap 的效率。

4. HashMap为什么不直接使用对象的原始hash值呢?

static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们发现,HashMap的哈希值是通过上面的方式获取,而不是通过key.hashCode()方法获取。

原因:

通过移位和异或运算,可以让 hash 变得更复杂,进而影响 hash 的分布性。

5. 既然红黑树那么好,为啥hashmap不直接采用红黑树,而是当大于8个的时候才转换红黑树?

因为红黑树需要进行左旋,右旋操作, 而单链表不需要。

以下都是单链表与红黑树结构对比。

如果元素小于8个,查询成本高,新增成本低。

如果元素大于8个,查询成本低,新增成本高。

至于为什么选数字8,是大佬折中衡量的结果-.-,就像loadFactor默认值0.75一样。

本文由 Sanarous 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可,转载前请务必署名
本文链接:https://bestzuo.cn/posts/hashmap.html
最后更新于:2020-07-03 17:55:57

切换主题 | SCHEME TOOL