HashMap类详细分析

在继续详细讨论该类之前，让我们先关注与哈希表相关的基本概念。本文不会讨论使用哈希映射的方法。只对插入、查找、删除操作进行清晰详细的讨论。我认为从同一个 Schildt 那里读到HashMap可用方法的描述并不困难。也许将来我会写另一篇文章专门讨论这些方法，但目前这是有问题的。与 Java 7 相比，Java 8 中的 HashMap 类发生了重大变化（+1000 行代码）。您可以在这里阅读有关 Java 7 中的实现（但不再相关）：habr 哈希表是一种实现关联数组接口（抽象键值模型或条目）的数据结构，它提供非常快速的插入和搜索：无论元素数量的插入和搜索（有时是删除）的执行时间接近常数 - O(1)。本质上，这是一个常规数组，其中元素的位置取决于元素本身的值。元素的值与其在哈希表中的位置之间的关系由哈希函数指定。 哈希函数接受一个输入数据（我们称之为键），并生成一个称为哈希值（或哈希码）的整数作为输出。然后，哈希值将我们的密钥绑定到特定的哈希表索引。对于基本操作：插入、查找和删除，我们使用相同的哈希函数，因此这些操作执行得相当快。因此，哈希函数的行为必须一致，并且对于相同的输入数据输出相同的索引，这一点很重要。值得注意的是，生成的哈希码可能是一个巨大的数值，而原始数组有条件地设计为仅包含 16 个元素。为什么不创建一个包含 10 亿个元素的数组来仅添加 10 个元素呢？因此，我们必须以某种方式将这个哈希码转换为0到15之间的值（如果数组大小为16）。为此，使用了额外的转换。因此我们生成一个索引来最小化数组的大小。例如，在 Java 8 之前的 HashMap 中，使用此附加方法来查找所需的单元格：

static int indexFor(int h, int length) {
        return h & (length-1);
}

作为输入，它采用工作结果获得的哈希码hashCode()和内部数组的长度（单元数）。它返回结果“哈希码”->按位“AND”->（数组长度 - 1）。该类HashMap继承自类AbstractMap并实现以下接口：Map、Cloneable、Serializable。.method 负责 Java 中的哈希函数hashCode()。默认实现返回一个称为身份哈希码的hashCode()值。即使类重写了，您也始终可以通过调用 来获取对象的 ID 哈希值。有时人们认为，OpenJDK 中的默认实现与内存地址无关。更多详细信息请参见：habr 在 HashMap 中，哈希表是基于单链表数组（或者更准确地说，动态的，因为表可以扩展）实现的。本质上，我们通过方法获得键的哈希码，然后对其进行修改（我们稍后将考虑），并在内部使用附加方法将结果值分发到所需的单元格。数组元素（单元）也称为存储桶，用于存储各个节点。每个桶都是一个集合（列表或树）。节点是嵌套类（或树结构中）的对象。事实上，数组单元内部只有一个单链表或红黑树，它是另一个类 - 的实现的基础。 hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap 红黑树的选项并不经常出现（如何、什么和在哪里 - 下面），并且这种结构很难理解，因此重点将放在 Node 类型的节点上。 Node是一个嵌套类，其中HashMap包含以下字段：

• final int hash— 当前元素的哈希值，这是我们通过哈希键获得的结果；
• final K key— 当前元素的键。这是您指定为方法中第一个对象的写入位置put()；
• V value— 当前元素的值。你在方法中指定的第二个对象写在这里put()；
• Node < K, V> next— 链接到同一篮子内的下一个节点。该列表是连接的，因此它需要一个不指向下一个节点的链接（如果有）。

现在让我们看看HashMap类本身的字段：

• transient Node < K, V> [] table– 哈希表本身，基于数组实现，用于以节点的形式存储键值对。这是我们的节点存储的地方；
• transient int size— 键值对的数量；
• int threshold— 元素的最大数量，达​​到该数量后哈希表的大小将加倍。使用公式计算（容量*负载系数）；
• final float loadFactor— 该参数决定当前哈希表需要多大程度的负载才能创建新的哈希表，即 一旦哈希表已满 75%，就会创建一个新的哈希表，并将当前元素移入其中（这是一个成本高昂的操作，因为所有元素都必须重新哈希）；
• transient Set< Map.Entry< K,V>> entrySet- 包含一个缓存entrySet()，我们可以用它进行迭代HashMap。

和常数：

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— 默认哈希表容量（16）；
• static final int MAXIMUM_CAPACITY = 1 << 30— 哈希表的最大可能容量（大约 10 亿）；
• static final float DEFAULT_LOAD_FACTOR = 0.75f——默认负载系数；
• static final int TREEIFY_THRESHOLD = 8是一个桶中元素数量的“阈值”，达到该阈值后，内部链表将转换为树结构（红黑树）。
• static final int UNTREEIFY_THRESHOLD = 6— 如果一个篮子中的元素数量减少到 6，那么就会发生从树到链表的反向转换；
• static final int MIN_TREEIFY_CAPACITY = 64— 可以转换为树结构的哈希表的最小容量（桶数）。那些。如果哈希表中至少有 64 个桶，并且一个桶中有 8 个或更多元素，那么就会发生向树结构的转变。

类构造函数：

1. public HashMap()— 默认创建哈希显示：体积(capacity) = 16和负载因子(load factor) = 0.75；
2. public HashMap(Map< ? extends K, ? extends V> m)— 创建一个由另一个给定映射的元素初始化的哈希映射，其初始容量足以容纳另一个映射的元素；
3. public HashMap(int initialCapacity)— 创建具有给定初始容量的哈希图。为了HashMap能够正确正确地工作，内部数组的大小必须是2的幂（即16、64、128等）；
4. public HashMap(int initialCapacity, float loadFactor)— 使用指定参数创建哈希映射：初始容量和负载因子。

类实现接口Map并扩展类，AbstractMap而不添加自己的方法。哈希映射不保证其元素的顺序。因此，元素进入哈希映射的顺序不一定是迭代器检索它们的顺序。 添加对象 添加键值对是使用put(). 让我们看一下添加对象时涉及的步骤：

1. 计算输入对象的键的哈希值。密钥哈希是通过static final int hash(Object key)已经访问hashCode()我们已知的密钥方法的方法计算的。为此，hashCode()可以使用重写方法或其默认实现。该方法中的附加转换hash()：

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

   Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash

   где n – длина массива.

3. Создается an object Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Теперь к очень подробному примеру.

   1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

   2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

   3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

   4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

   5. 同时，我们计算将放置对象的桶的索引，并检查其中是否已经有元素。我们计算：

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4

      查看：

      
      if ((p = tab[i = (n - 1) & hash]) == null)

   6. 由于检查结果为 true（桶中没有元素），因此将生成具有以下字段的 Node 对象：

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      我们生成的 Node 对象将被添加到索引 [4] 下的存储桶中：

      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()是一个仅返回 Node 类对象的方法。

   7. 添加后，将检查当前元素数量是否超过参数threshold：

      if (++size > threshold)
          resize();

      如果超过，则会调用一个方法resize()来增加哈希表的大小。

      此时，该方法putVal()（分别为 和put()）将完成其工作。

      结果可以用图形表示如下：

      一般来说，如果所需的存储桶为空，这就是向哈希表添加节点（键值对）的情况。现在让我们尝试添加一个会导致碰撞的元素（当一个桶中有多个元素时）。

关于冲突的一些知识 不同的键最终出现在同一个存储桶中（即使具有不同的哈希值）的情况称为冲突或碰撞。即使哈希表比数据集大并且选择了好的哈希函数，也不能保证不会发生冲突。并且哈希值仅限于int值的范围（约40亿）。生成的新值还需要写入某处，为此您需要确定它将写入的确切位置。这称为冲突解决。有两种方法：

• 外部链接或链接方法（在 HashMap 中实现） - 即 单元格实际上包含一个列表（链）。并且列表可能已经包含多个值（不一定具有相同的哈希码）。
• 线性探测或开放寻址方法（在 IdentityHashMap 中实现）- 包括搜索哈希函数指向的空单元之后的第一个空单元；

您可以在此处阅读有关碰撞的信息：单击

1. 使用该方法，put()我们将另一个键值对添加到哈希映射中：

   map.put("BLAKE", 10);

2. 我们计算“初步哈希” - 63281361。我们修改它，结果我们得到最终的哈希码 - 63281940。

3. 由于第一次检查“空”现在将返回 false（无需创建表），因此我们立即计算将放置对象的存储桶的索引：

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4

4. 检查指定索引处的存储桶中是否存在元素，由于if ((p = tab[i = (n - 1) & hash]) == null)在这种情况下不满足条件（存储桶中已经有一个元素），因此我们转到块else。

5. 首先，我们将添加的元素与桶内链表的第一个元素进行比较：

   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:

   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }

   В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };

   Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

   Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))

   Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

   После добавления второго element наш an object HashMap графически выглядит так:

   В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

   • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
   • если ключи одинаковы, заменить текущее meaning новым.
   • иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

   for (int binCount = 0; ; ++binCount)

   До тех пор, пока их количество не станет равно or больше 7:

   binCount >= TREEIFY_THRESHOLD – 1

   В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

   将调用一个方法来resize()增加哈希表的大小，重新分配元素，而不是进入树结构。treeify()反过来，链表转换TreeNode成红黑树。该方法resize()迭代当前存储的所有元素，重新计算它们的索引（考虑到新的大小）并将元素重新分配到新数组中。

   简而言之，在不深入红黑树结构细节的情况下，会发生以下情况：

   1. 列表的第一个元素被写为整个树的根（黑色）：

      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }

   2. 对于其他元素：

      根据哈希值将它们分布到左侧或右侧：

      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;

      所有左子节点必须小于（或等于）其根节点，而所有右子节点必须大于其根节点。

   3. 如果两个元素具有相同的哈希值并且无法以任何其他方式进行比较（它们没有实现接口Comparable），我们会中断树的构造并调用该方法tieBreakOrder()，该方法又使用本机方法System.identityHashCode()来计算全局唯一的哈希码。

      更多详细信息请参见：文章链接

   4. 我们检查树元素（对象TreeNode），直到找到子（左或右）零元素。

      if ((p = (dir <= 0) ? p.left : p.right) == null)

   5. 添加一个子节点（左或右取决于目录）：

      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;

   6. 由于添加新元素可能会破坏树的平衡，因此我们将方法称为重新平衡：

      root = balanceInsertion(root, x);

      您可以在这里阅读有关平衡 CCH 的信息：habr

   7. 平衡后，根元素可能会发生变化。我们通过调用一个方法来修复这个问题，该方法保证传递给它的根将是第一个节点：

      moveRootToFront(tab, root)

      在这里可以清楚地看到红黑树是如何构建和自平衡的：可视化

原则上这就是全部，并使用一个示例，假设我们要添加以下名称作为键：KING、MARY、JOSE、ANNA、FRED、TONY、ALEX、PEPE。假设哈希表中至少有 64 个桶，所有这些元素都累积在一个桶中。从结构上讲，这个存储桶将如下所示（元素按哈希码排序）： CCHD 类型： 查看桶内情况： 检索元素（通过键检索值） 关于添加操作，非常简单。算法（当桶中有链表时）可以这样写：

1. 计算密钥的哈希码。
2. 计算桶索引。
3. 遍历索引并将第一个元素的键与现有值进行比较。如果它们相等，则返回该值，否则检查下一个元素（如果存在）。
4. 如果下一个 Node 对象为 null，则返回 null。
5. 如果下一个Node对象不为null，则转到它并重复前三个步骤，直到找到该元素或者下一个Node对象为null。

使用该方法，get()我们获取“KING”键的值：

map.get("KING");

在内部，调用该方法getNode(int hash, Object key)，将密钥本身（“KING”）及其哈希值（2306996）传递给该方法，该哈希值以与操作期间相同的方式预先计算put()。

1. 我们检查：

   1. 哈希表是否存在：(tab = table) != null

      让我提醒您，创建 HashMap 时，不会在构造函数中创建表的数组；这会在稍后的方法中创建resize()，该方法在将第一个元素添加到哈希表时总是被调用。因此，如果HashMap中还没有添加任何元素，那么根本就没有内部数组来存储这些元素。

   2. 如果前面的表达式返回 true，则需要确保内部数组的长度大于 0：(n = tab.length) > 0;

   3. 如果前面的表达式也返回 true，则转到之前计算的索引（在我们的例子中为 4）处的存储桶，并检查它是否存在元素：

      (first = tab[(n - 1) & hash]) != null)

   4. 我们将要查找的键与存储桶内列表中第一个元素的键进行比较，因为在大多数存储桶中（并非在所有发生冲突的地方）只有一个元素（我们的情况）。与方法 的情况一样put()，会比较哈希值，如果它们匹配，则通过引用比较键，然后才通过 进行比较equals()。

      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))

      因为在我们的例子中，键“KING”将在键“BLAKE”之前（在链表中，新元素被添加到末尾，KING首先被添加），我们将在此时停止并返回第一个对象在 get() 方法中输入 Node，该方法会从他那里“抢走”一个值为 (100) 的字段：

      return (e = getNode(hash(key), key)) == null ? null : e.value;

2. 如果桶内有多个元素，则：

   1. 如果桶是一个链表，我们会循环遍历列表中的每个元素，do – while直到找到匹配项：

      do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      } while ((e = e.next) != null);

   2. 如果桶是树结构，则另外调用该方法getTreeNode()，进而使用该方法来查找所需的键find()。我们进行树搜索 - 比较哈希值并确定要搜索的左根节点或右根节点。如果键相等（通过引用或通过equals），则返回此节点。如果左或右子节点为空，我们还使用compareTo比较键（如果键实现接口Comparable），否则我们在树（右子树或左子树）中执行递归搜索，直到找到匹配项。

从 HashMap 中删除对象 由于本文篇幅有限，我将简要描述如何通过键进行删除。该算法非常相似：

• 转到所需的存储桶（同样，它是预先计算的）；

• 如果桶中只有一个对象（我们检查其空指针），我们会比较哈希值、链接和equals（如果突然哈希值不相等）。找到匹配的了吗？太棒了，这是我们的键 - 删除它（=null）并返回该键的值。

• 如果桶中有多个元素，我们会循环检查每个元素，直到找到该元素或到达列表末尾。

• 如果没有找到该元素，我们返回 null。

在树的情况下，有一个相当棘手的实现，最好不要知道它并睡个好觉（该方法的描述甚至说该实现比红黑中的常规删除操作更复杂）树）。而且，当删除时，一个桶中的节点数可以恢复到6个，然后树将被重建回链表。如果您不是具有多年经验的开发人员，则完全没有必要了解和理解这一点（而且根本没有必要）。