当前位置： 首页 > news >正文

HashMap 源码分析

news 2024/11/5 9:36:10

HashMap 源码分析

1. 前置知识

1.1 什么是 Map

在实际需求中，我们常常会遇到这样的问题：在诸多数据中，通过其编号来寻找某些信息，从而进行查看或修改，例如通过学号查询学生信息。今天我们所介绍的 Map 集合就可以很好地帮助我们实现这种需求。

1.1.1 概述

Map 是一种存储元素对的集合（元素对分别称作键和值，也称键值对），它将键映射到值的对象。一个映射不能包含重复的键，并且每个键最多只能映射到一个值。

  • 键 (key)：就是存的值的编号
  • 值 (value)：就是要存放的数据

可以将键理解为下标，值依据键而存储。每个键都有其对应值。这两者是一一对应的，但在 Map 中，键可以是任意类型的对象。

1.1.2 Map 集合和 Collection 集合的区别
  • Map 集合存储元素是成对出现的，键是唯一的，值是可重复的。
  • Collection 集合存储元素是单独出现的，Set 是唯一的，List 是可重复的。
  • Map 集合的数据结构值针对键有效，跟值无关；Collection 集合的数据结构是针对元素有效。

1.2 什么是散列表

散列表，也叫 hash 表，是根据关键码值而进行直接访问的数据结构。它通过将关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射叫散列函数，存放记录的数组叫散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名到首字母的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。—— 维基百科

1.2.1 分析一下为什么要用散列表

哈希表本质上是一种数组扩展，因为其使用数组按下标随机访问数据的特点。假设创建一个数组，每个存储空间看作一个箱子，存储一些 key-value 的数据，如：

  • 【张三，20】
  • 【李四，30】
  • 【王五，40】
  • 【赵六，50】
  • 【孙七，60】

如果使用顺序表查找方式，需要从开始依次比对查询，数据量越多，查找耗费的时间就越长。

1.2.2 散列表工作原理

假设使用 5 个箱子（桶）空间的数组来存储数据。存储第一个数据【张三，20】时，散列表使用哈希函数计算出“张三”的哈希值，例如返回一个 5372。将其做取余处理，除数为数组的长度，即：5372 mod 5 = 2，因此将其放在下标（index）为 2 的位置。

当存储第三个数据【王五，40】时，经过哈希函数计算，得出的结果为 5277，5277 mod 5 = 2，此时位置 2 已经有数据【张三，20】存在了，这种存储位置重复的情况称为冲突。

1.2.3 如何解决 Hash 冲突

1.2.3.1 JDK 1.7

在 JDK 1.8 之前，HashMap 的底层是数组和链表。当出现哈希冲突时，使用拉链法解决冲突。拉链法是将数组的每一个格子看作一个链表，例如下标为 1 的格子，若仍有数据哈希值 mod 后等于 1，则直接在该链表中追加数据。

1.2.3.2 JDK 1.8

JDK 8 进行了较大调整，当数组中每个格子里的链表长度大于阈值（默认为 8）时，将链表转化为红黑树，从而减少搜索时间。并且如果散列表快满时，系统会进行再散列。

1.3 什么是红黑树

红黑树是一种复杂的树形结构，主要目的是保持平衡，防止二叉树变成一条线状或左右不均衡。

对于理解，还可以参考掘金上的一篇文章（掘金-漫画：什么是红黑树？@程序员小灰）非常不错！

2. 源码分析

2.1 类成员

// 序列化自动生成的一个码，用来在正反序列化中验证版本一致性。
private static final long serialVersionUID = 362498820763181265L;   // 默认的初始容量 1 * 2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量 1 * 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 桶的树化阈值，当桶(bucket)上的结点数大于这个值时会转成红黑树，
// 也就是上面提到的长度大于阈值（默认为8）时，将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;// 桶的链表还原阈值，当桶(bucket)上的结点数小于这个值时树转链表
// 一个道理
static final int UNTREEIFY_THRESHOLD = 6;// 最小树形化容量阈值，当哈希表中的容量 > 该值时，才允许树形化链表 
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容和树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table; // 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;// 存放元素的个数（不是数组的长度）
transient int size;// 扩容和修改的计数变量
transient int modCount;   // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;// 加载因子
final float loadFactor;

需要强调的内容有：

  • threshold：临界值，数组扩容的一个临界值。当数组实际大小（容量 × 填充因子）超过该值时，进行扩容。
  • loadFactor：加载因子，表示哈希表中元素填满的程度。当表中元素超过该值时，哈希表自动扩容，通常是 1 倍。经过实验，加载因子设置为 0.75f 是较为合理的平衡。

2.2 两个节点

由于一定条件下会转换成红黑树，因此有两个节点类型：

  • Node 节点
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;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }// 重写了 hashCode， ^ 是位异或运算符public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}// 重写 equals() 方法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;// 左节点TreeNode<K,V> left;// 右节点TreeNode<K,V> right;TreeNode<K,V> prev;// 判断颜色，默认红色boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}// 返回根节点final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}

2.3 构造方法

// 指定了具体容量大小和加载因子的构造函数
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;this.threshold = tableSizeFor(initialCapacity);
}// 指定了具体容量大小的构造函数
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}// 默认无参构造函数
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; 
}// 指定了 map 的构造函数
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}
  • tableSizeFor：计算合适的数组大小。
/*** 返回一个大于输入参数，且最接近的，2的整数次幂的数* 只是一个初始化内容，创建哈希表时，会再重新赋值*/
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;
}
  • putMapEntries：用于将 Map 的所有条目添加到 HashMap。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {// 拿到给定 Map 的长度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);// 若大于临界值，则初始化阈值if (t > threshold)threshold = tableSizeFor(t);}// table 已初始化，并且给定 Map 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 方法会在介绍添加相关方法时介绍putVal(hash(key), key, value, false, evict);}}
}

2.4 添加方法

2.4.1 put()

HashMap 提供的公共添加方法只有 put(K key, V value) 一个，其他的 put 方法是供内部调用的。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
2.4.2 putVal()

流程如下：

  • 定位到具体的数组位置 A。
  • 若 A 处没有元素，直接插入。
  • 若 A 处有元素，则与待插入的 key 比较：
    • 若 key 相同，直接覆盖。
    • 若 key 不同，判断 p 是否为树节点：
      • 若是，调用 putTreeVal 方法添加元素。
      • 若不是，遍历链表插入（尾插法）。
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;// 若桶为空，即无发生碰撞// (n - 1) & hash 用来确定元素存放在哪个位置，即哪个桶中if ((p = tab[i = (n - 1) & hash]) == null)// 新生成结点放入桶中(数组中)tab[i] = newNode(hash, key, value, null);// 若桶中已经存在元素else {Node<K,V> e; K k;// 若节点 key 存在，就和要插入的key比较if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 如果key相同就直接覆盖 valuee = p;// hash值不相等，即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);// 结点数量达到阈值，转化为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循环break;}// 遍历的过程中，遇到相同 key 则覆盖 valueif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循环break;// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表p = e;}}// 在桶中找到key值、hash值与插入元素相等的结点if (e != null) { // 记录e的valueV oldValue = e.value;// onlyIfAbsent 为 false 或者旧值为 nullif (!onlyIfAbsent || oldValue == null)// 用新值替换旧值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改++modCount;// 超过最大容量，扩容if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;
}

2.5 获取方法

2.5.1 get()

同样，get 方法中也用到了 hash 方法计算 key 的哈希值。

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}
2.5.2 getNode

用于根据 key 获取对应节点。

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) {// 在树中 getif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 在链表中getdo {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

2.6 移除方法

2.6.1 remove()

同样，remove 方法中也用到了 hash 方法计算 key 的哈希值。

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}
2.6.2 removeNode()

用于根据 key 移除对应节点。

final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;// 桶不为空，映射的哈希值也存在if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 如果在桶的首位就找到对应元素，记录下来if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 若不在首位，就去红黑树或者链表中查询了else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 找到了要删除的节点和值，就分三种情况去删除，链表，红黑树，桶的首位if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

2.7 扩容方法

2.7.1 resize()

resize 在程序中是非常耗时的，因此需要尽量避免调用它。其过程中会重新分配 hash，然后遍历哈希表中所有元素。

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 超过最大值，不再扩容，没办法了if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 没超过最大值，就扩充为原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in threshold// 初始化时，threshold 暂时保存 initialCapacity 参数的值newCap = oldThr;else { // signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的resize上限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 { // 拆链表，拆成两个子链表并保持原有顺序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;elseloTail.next = e;loTail = e;}// 原索引 + oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到新的哈希桶中if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引 +oldCap 放到新的哈希桶中if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

3. 重点分析

3.1 HashMap 的添加元素过程

1. HashMap 的基本结构

在 HashMap 中，主要使用一个数组（table）来存储键值对。根据负载因子和初始容量的设置，HashMap 可能会动态调整大小，以保持操作的高效性。具体如下：

  • 数组 table：存储链表或红黑树的节点。
  • DEFAULT_INITIAL_CAPACITY：默认数组大小，通常为16。
  • DEFAULT_LOAD_FACTOR：默认负载因子，通常为0.75，用于决定何时扩容。
2. 数据结构

在 HashMap 中，每个节点可以分为两种类型：链表节点和红黑树节点。

2.1 链表节点

每个链表节点的结构如下：

static class Node<K, V> {int hash;         // 键的哈希值final K key;     // 键V value;         // 值Node<K, V> next; // 下一个节点的地址
}
2.2 红黑树节点

红黑树节点的结构如下：

static class TreeNode<K, V> extends Node<K, V> {TreeNode<K, V> parent; // 父节点TreeNode<K, V> left;   // 左子节点TreeNode<K, V> right;  // 右子节点boolean red;           // 节点颜色
}
3. 添加元素的过程

我们来看看如何向 HashMap 中添加元素，并讨论不同的情况：

HashMap<String,Integer> hm = new HashMap<>();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);

在添加元素时，主要考虑以下三种情况：

  • 数组位置为 null：创建新的键值对对象，直接放入数组。
  • 数组位置不为 null，键不重复：将新节点挂在已有节点下面，形成链表或红黑树。
  • 数组位置不为 null，键重复：覆盖已有键的值。

下面逐步讲解 put 方法的逻辑和过程：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
3.1 计算哈希值

首先，使用 hash 方法计算出键的哈希值：

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

这个哈希值会在后续操作中决定元素在数组中的位置。

3.2 putVal 方法

putVal 方法是核心，处理键值对的插入：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab;Node<K,V> p;int n, i;tab = table;

  1. 初始化：

    • 获取当前数组 tab，并声明一些局部变量。

  2. 扩容检查：

    if (tab == null || (n = tab.length) == 0) {tab = resize();n = tab.length;
}
    • 如果数组为空，说明这是第一次插入元素。此时，调用 resize() 方法初始化数组，并设置其大小。

  3. 计算索引：

    i = (n - 1) & hash; // 计算索引
p = tab[i];        // 获取数组中对应的节点
3.3 插入元素的不同情况

接下来，根据数组位置的情况进行不同的处理：

3.3.1 数组位置为 null
if (p == null) {tab[i] = newNode(hash, key, value, null);
}
  • 如果当前位置 p 为 null，直接在数组中创建一个新节点。
3.3.2 数组位置不为 null，键不重复
  • 如果当前位置不为空（p != null），需要检查键是否重复。
Node<K,V> e;
K k;
boolean b1 = p.hash == hash;if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))) {e = p;
} 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)treeifyBin(tab, hash);break;}if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {break;}p = e;}
}

  • 判断键是否相同：

    • 使用 hash 和 key 的 equals 方法判断。
    • 如果存在相同键的节点，记下该节点 e。

  • 处理红黑树：

    • 如果当前位置是红黑树的节点，调用 putTreeVal 方法按照红黑树的插入规则添加。

  • 处理链表：

    • 如果链表未满，依次遍历链表找到最后一个节点，添加新的节点。
    • 判断链表长度，如果超过8个元素，调用 treeifyBin 方法将其转换为红黑树。
    final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 检查哈希表是否需要扩容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize(); // 扩容以保证足够的空间else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null; // 创建链表头尾节点do {// 将链表节点转换为红黑树节点TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p; // 如果是第一个节点，则将头节点设为 pelse {p.prev = tl; // 设置前驱节点tl.next = p; // 设置后继节点}tl = p; // 更新尾节点} while ((e = e.next) != null); // 遍历整个链表// 将头节点放回哈希表，并调用 treeify 方法将链表转换为红黑树if ((tab[index] = hd) != null)hd.treeify(tab);}
}
3.3.3 数组位置不为 null，键重复，元素覆盖
if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null) {e.value = value; // 更新值}afterNodeAccess(e); // 访问后操作return oldValue;     // 返回旧值
}
  • 如果 e 不为 null，表示键重复，执行值的覆盖。
  • 根据 onlyIfAbsent 的值决定是否覆盖旧值，并返回旧值。
4. 扩容判断

最后，在插入完毕后，检查是否需要扩容：

if (++size > threshold) {resize();
}
  • 如果当前 size 超过阈值（threshold），则调用 resize() 方法进行扩容。

3.2 hash() 中的扰动函数如何解决 Hash 冲突

在 Java 的 HashMap 中，哈希冲突是一个不可避免的问题。HashMap 的 hash() 方法通过引入一个扰动函数来减少哈希冲突的发生，确保哈希表中的元素均匀分布。

1. HashMap 的 put 方法

HashMap 的 put 方法用于将键值对添加到哈希表中。具体流程如下：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

在此方法中，首先调用 hash(key) 来计算键的哈希值。

2. hash() 方法的实现

HashMap 中的 hash() 方法的实现如下：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2.1 扰动函数分析

  • 判断 null：如果 key 为 null，返回 0。这意味着 null 键的哈希值是 0，不会占用其他位置。

  • 计算 hashCode：对于非 null 键，调用 key.hashCode() 方法。比如，对于 Integer 类型，hashCode 返回值就是这个整数本身。

  • 扰动函数：

    • 这里的扰动函数 h ^ (h >>> 16) 在哈希计算中发挥着重要作用。通过将哈希值的高位与低位混合，它有助于减少哈希冲突的概率。具体来说：
      • key.hashCode()：这是一个由 Object 类定义的方法，通常在子类中被重写。对于 Integer 类型，它返回的是这个整数本身。因此，hashCode 在这种情况下是唯一的。
      • h >>> 16：这是一个无符号右移操作，将哈希值的高16位移到低16位，确保高位信息被引入到最终哈希值中。
      • ^ (位异或运算)：通过异或运算，高位与低位混合后，新的哈希值就变得更加随机，有助于更均匀地分布在哈希表中。
2.2 扰动函数的必要性

这一过程的核心在于通过扰动函数使得哈希值更加随机。举个例子，假设我们有两个不同的 hashCode 值，经过与操作（&）后，如果它们的低位相同，可能会导致冲突。我们来看看这段分析：

HashMap初始长度为16，length - 1 = 15；
其二进制表示为：00000000 00000000 00000000 00001111

假设 hashCode 值为：

  • hash1 = 1234567890（二进制为 01001001100101101011111001000110）
  • hash2 = 987654321（二进制为 0011101011011010111111100001110001）

经过与运算，我们得到：

index1 = hash1 & 15;
index2 = hash2 & 15;

如果这两个值经过与操作后都得到了相同的结果（比如都是 12），就会发生哈希冲突。这是因为高位信息在与操作中被忽略，导致不同的哈希值映射到同一个位置。

3. 扰动函数如何解决冲突

引入扰动函数后，我们能够更好地解决冲突问题。通过混合高低位信息，扰动函数确保了高位的一些特征也能够影响最终的哈希值：

数据一：hash1 = key.hashCode() = 1234567890
数据二：hash2 = key.hashCode() = 987654321计算扰动后的哈希值：
hash1' = hash1 ^ (hash1 >>> 16);
hash2' = hash2 ^ (hash2 >>> 16);

这样，在扰动函数的作用下，即使 hash1 和 hash2 的低位可能相同，它们经过扰动函数的处理后，最终得到的值可能会完全不同。例如：

  • hash1' = 1234567890 ^ (1234567890 >>> 16) = ...（计算后得到的新哈希值）
  • hash2' = 987654321 ^ (987654321 >>> 16) = ...（计算后得到的新哈希值）

通过这种方式，扰动函数使得每个键的哈希值更具随机性，降低了哈希冲突的概率。

4. 位运算的效率

在实现过程中，使用位运算（&）比取模运算（%）更高效，因为位运算直接对内存数据进行操作，而取模运算需要进行转换。因此，使用位运算不仅提高了效率，也降低了哈希冲突的风险。
= 1234567890（二进制为 01001001100101101011111001000110`）

  • hash2 = 987654321（二进制为 0011101011011010111111100001110001）

经过与运算，我们得到：

index1 = hash1 & 15;
index2 = hash2 & 15;

如果这两个值经过与操作后都得到了相同的结果（比如都是 12），就会发生哈希冲突。这是因为高位信息在与操作中被忽略，导致不同的哈希值映射到同一个位置。

3. 扰动函数如何解决冲突

引入扰动函数后，我们能够更好地解决冲突问题。通过混合高低位信息，扰动函数确保了高位的一些特征也能够影响最终的哈希值：

数据一：hash1 = key.hashCode() = 1234567890
数据二：hash2 = key.hashCode() = 987654321计算扰动后的哈希值：
hash1' = hash1 ^ (hash1 >>> 16);
hash2' = hash2 ^ (hash2 >>> 16);

这样，在扰动函数的作用下，即使 hash1 和 hash2 的低位可能相同，它们经过扰动函数的处理后，最终得到的值可能会完全不同。例如：

  • hash1' = 1234567890 ^ (1234567890 >>> 16) = ...（计算后得到的新哈希值）
  • hash2' = 987654321 ^ (987654321 >>> 16) = ...（计算后得到的新哈希值）

通过这种方式，扰动函数使得每个键的哈希值更具随机性，降低了哈希冲突的概率。

4. 位运算的效率

在实现过程中，使用位运算（&）比取模运算（%）更高效，因为位运算直接对内存数据进行操作，而取模运算需要进行转换。因此，使用位运算不仅提高了效率，也降低了哈希冲突的风险。


http://www.mrgr.cn/news/65876.html

相关文章：

  • Docker篇（容器的备份与迁移）
  • [vulnhub]DC: 1
  • Android 各版本 TLS 协议支持及启用方式
  • 15分钟学 Go 第 35 天：Go的性能调优 （7000字详细教程）
  • C++ --- 指针的使用（如何理解指针？指针的细节你又了解多少？）
  • 《深度学习入门》笔记
  • git上传大文件的解决方案
  • 文件系统上云的挑战
  • 详解：枚举类
  • 关于Linux系统调试和性能优化技巧有哪些？
  • 计算机启动过程中各个步骤
  • 全面解析：物联网技术及其应用
  • ACTF新生赛2020：NTFS数据流
  • C++——用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个团数，整数和n在主函数中输人,最后在主函数中输出。
  • 十四届蓝桥杯STEMA考试Python真题试卷第二套第四题
  • 一文了解Android SELinux
  • Golang | Leetcode Golang题解之第538题把二叉搜索树转换为累加树
  • Python | Leetcode Python题解之第538题把二叉搜索树转换为累加树
  • DDD学习笔记
  • 麻省理工学院的研究人员最近开发了一种新的机器人训练方法
  • 阿里云服务器 篇十：自动定时备份CSDN博客内容
  • 十四届蓝桥杯STEMA考试Python真题试卷第二套第五题
  • 【Java知识】java进阶-一个好用的java应用分析工具arthas
  • markdown/Latex希腊字母αβγ...λ...π等怎么编辑
  • sqlserver
  • 【C++ 曼哈顿距离 数学】1131. 绝对值表达式的最大值|2059