跳至主要內容

HashMap原理解析

fangzhipeng约 2222 字大约 7 分钟

HashMap的类结构图

HashMap 是 java 集合框架中用于存储双列数据的散列表,应用非常的广泛。HashMap的类结构图如下:

image-20231202113045647
  • HashMap继承了AbstractMap类并实现类Map接口,所以HashMap具有了AbstractMap和Map的功能。

  • HashMap实现了Cloneable接口,表明HashMap支持克隆。

  • HashMap实现了Serializable接口,表明HashMap支持序列,可以将HashMap以流的形式通过ObjectInputStream/ObjectOutputStream来写/读。

HashMap的底层数据结构

HashMap 的的底层数据结构为数组+链表(或者红黑树)结构,如下图所示:

image-20231202112718275

HashMap 通过 Node 类来存储键值对(K 表示键的类型,V 表示值的类型)。每个 Node 对象包含了键、值以及指向下一个 Node 的引用。

在 JDK 8 以后的版本中,如果链表长度超过阈值(默认为8),且 HashMap 的容量达到了一个较大的值(默认为64),则部分链表节点会转换为红黑树。这些红黑树节点被实现为 TreeNode 类,它拓展自 Node 类。

构造函数

HashMap 有两种构造函数:无参构造函数和带初始容量和负载因子的构造函数。无参构造函数创建一个初始容量为16,负载因子为0.75的 HashMap 对象。

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = tableSizeFor(INITIAL_CAPACITY);
}

带参构造函数接收初始容量 initialCapacity 和负载因子 loadFactor 作为参数,创建一个 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);

    this.loadFactor = loadFactor;
    threshold = tableSizeFor(initialCapacity);
}

tableSizeFor(initialCapacity) 方法用于计算大于等于给定容量的最小 2 的幂。

存储元素过程

首先我们先创建一个HashMap对象,然后使用put(key,value)方法,把元素存储在HashMap对象中,代码如下:

  Map<String,String> map=new HashMap<>();
        map.put("james","1");
        map.put("kobe","1");
        map.put("robin","1");
        map.put("sam","1");

要把键值对 (“james”,”1”)存入map中,首先,根据传入的 key 对象计算哈希值 hash,计算hash的源码如下:

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