hashMap源码解析

冷不防 2022-03-25 06:58 540阅读 0赞

源码来自jdk：1.8，和其他jdk版本可能有少许差异。

一.hashMap的实现原理

  1. hashMap底层是一个有Node组成的数组，每个Node都有一个key，一个value，一个通过对key的hashcode得到的hash值，和一个next指针。可以简单理解为一个数组，数组里每个元素存的是链表，链表过长就转化为红黑树。
  3. /**
  4.  *可以看到这个数组是被transient修饰，禁止被序列化，因为table数组是随时变化，
  5.  *所以没必要序列化，序列化只会浪费存储空间，可以看到hashMap源码中很多属性都加了transient。
  6.  */
  7. transient Node<K,V>[] table;
  9. static class Node<K,V> implements Map.Entry<K,V> {
  10.         final int hash; //通过key的hashcode进行hash运算得到的hash值
  11.         final K key; //键
  12.         V value; //值
  13.         Node<K,V> next; //指向下一个Node的指针
  15.         Node(int hash, K key, V value, Node<K,V> next) { //构造函数
  16.             this.hash = hash;
  17.             this.key = key;
  18.             this.value = value;
  19.             this.next = next;
  20.         }
  21. }

1.当向hashMap中存储元素时，首先通过key的hashcode值计算出该元素的hash值，通过hash值来决定该元素存储在底层数组的哪个位置，当出现多个hash值时即hash冲突时，hashMap的解决方案是拉链法，在当前数组中元素的位置形成一个链表，新加入元素的放在链头，最先加入元素的放在链尾。

  1. /**
  2.      * Implements Map.put and related methods
  3.      *
  4.      * @param hash hash for key
  5.      * @param key the key
  6.      * @param value the value to put
  7.      * @param onlyIfAbsent if true, don't change existing value
  8.      * @param evict if false, the table is in creation mode.
  9.      * @return previous value, or null if none
  10.      */
  11.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  12.                    boolean evict) {
  13.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  14.         if ((tab = table) == null || (n = tab.length) == 0)
  15.             n = (tab = resize()).length;
  16.         if ((p = tab[i = (n - 1) & hash]) == null)
  17.             tab[i] = newNode(hash, key, value, null);
  18.         else {
  19.             Node<K,V> e; K k;
  20.             if (p.hash == hash &&
  21.                 ((k = p.key) == key || (key != null && key.equals(k))))
  22.                 e = p;
  23.             else if (p instanceof TreeNode)
  24.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  25.             else {
  26.                 for (int binCount = 0; ; ++binCount) {
  27.                     if ((e = p.next) == null) {
  28.                         p.next = newNode(hash, key, value, null);
  29.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  30.                             treeifyBin(tab, hash);
  31.                         break;
  32.                     }
  33.                     if (e.hash == hash &&
  34.                         ((k = e.key) == key || (key != null && key.equals(k))))
  35.                         break;
  36.                     p = e;
  37.                 }
  38.             }
  39.             if (e != null) { // existing mapping for key
  40.                 V oldValue = e.value;
  41.                 if (!onlyIfAbsent || oldValue == null)
  42.                     e.value = value;
  43.                 afterNodeAccess(e);
  44.                 return oldValue;
  45.             }
  46.         }
  47.         ++modCount;
  48.         if (++size > threshold)
  49.             resize();
  50.         afterNodeInsertion(evict);
  51.         return null;
  52.     }

2.当从hashMap中取元素时，首先通过key的hashcode计算该元素的hash值，通过hash值找到该元素在数组的位置，如果该位置有多个元素，即形成了链表，则遍历链表，通过equals()方法诸个比较，找出元素。

  1. public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6. /**
  7.      * Implements Map.get and related methods
  8.      *
  9.      * @param hash hash for key
  10.      * @param key the key
  11.      * @return the node, or null if none
  12.      */
  13.     final Node<K,V> getNode(int hash, Object key) {
  14.         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  15.         if ((tab = table) != null && (n = tab.length) > 0 &&
  16.             (first = tab[(n - 1) & hash]) != null) {
  17.             if (first.hash == hash && // always check first node
  18.                 ((k = first.key) == key || (key != null && key.equals(k))))
  19.                 return first;
  20.             if ((e = first.next) != null) {
  21.                 if (first instanceof TreeNode)
  22.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  23.                 do {
  24.                     if (e.hash == hash &&
  25.                         ((k = e.key) == key || (key != null && key.equals(k))))
  26.                         return e;
  27.                 } while ((e = e.next) != null);
  28.             }
  29.         }
  30.         return null;
  31.     }

3.

  1. public V remove(Object key) {
  2.         Node<K,V> e;
  3.         return (e = removeNode(hash(key), key, null, false, true)) == null ?
  4.             null : e.value;
  5.     }
  7.   /**
  8.      * Implements Map.remove and related methods
  9.      *
  10.      * @param hash hash for key
  11.      * @param key the key
  12.      * @param value the value to match if matchValue, else ignored
  13.      * @param matchValue if true only remove if value is equal
  14.      * @param movable if false do not move other nodes while removing
  15.      * @return the node, or null if none
  16.      */
  17.     final Node<K,V> removeNode(int hash, Object key, Object value,
  18.                                boolean matchValue, boolean movable) {
  19.         Node<K,V>[] tab; Node<K,V> p; int n, index;
  20.         if ((tab = table) != null && (n = tab.length) > 0 &&
  21.             (p = tab[index = (n - 1) & hash]) != null) {
  22.             Node<K,V> node = null, e; K k; V v;
  23.             if (p.hash == hash &&
  24.                 ((k = p.key) == key || (key != null && key.equals(k))))
  25.                 node = p;
  26.             else if ((e = p.next) != null) {
  27.                 if (p instanceof TreeNode)
  28.                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  29.                 else {
  30.                     do {
  31.                         if (e.hash == hash &&
  32.                             ((k = e.key) == key ||
  33.                              (key != null && key.equals(k)))) {
  34.                             node = e;
  35.                             break;
  36.                         }
  37.                         p = e;
  38.                     } while ((e = e.next) != null);
  39.                 }
  40.             }
  41.             if (node != null && (!matchValue || (v = node.value) == value ||
  42.                                  (value != null && value.equals(v)))) {
  43.                 if (node instanceof TreeNode)
  44.                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  45.                 else if (node == p)
  46.                     tab[index] = node.next;
  47.                 else
  48.                     p.next = node.next;
  49.                 ++modCount;
  50.                 --size;
  51.                 afterNodeRemoval(node);
  52.                 return node;
  53.             }
  54.         }
  55.         return null;
  56.     }

4.当hash冲突很多，链表过长时，查询操作效率很低，这时候链表会转化成红黑树。

5.jdk1.8引入的红黑树，当链表长度为8时转化为红黑树，当红黑树长度为6时，转化为链表。

5-1.为什么：在平均查找的时间效率上，红黑树是log(n)，所以有8个元素时为log(8)=3；链表是n/2，长度为8时，平均时间为8/2=4；小于6链表平均时间少，大于8红黑树平均时间少，至于为什么会间隔一个7呢，那是因为链表和红黑树之间的转化也需要一定的时间成本，频繁转化会浪费很多时间，所以预留了一个7。

  1. static final int TREEIFY_THRESHOLD = 8;
  3.     static final int UNTREEIFY_THRESHOLD = 6;

附：hash冲突的四种解决方法：https://blog.csdn.net/qq_27093465/article/details/52269862

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xjZ29pbmc_size_16_color_FFFFFF_t_70

一些重要属性：

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  4.     static final int MAXIMUM_CAPACITY = 1 << 30;
  7.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  10.     static final int TREEIFY_THRESHOLD = 8;
  13.     static final int UNTREEIFY_THRESHOLD = 6;
  15.     static final int MIN_TREEIFY_CAPACITY = 64;

预留。。。

二.什么是红黑树

平衡二叉搜索树(AVL树):一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

https://www.cnblogs.com/zhangbaochong/p/5164994.html

红黑树：红黑树是自平衡二叉查找树的一种，包含以下特性。

  1. 1. 节点是红色或黑色。
  3. 2. 根节点是黑色。
  5. 3.每个叶节点（NIL节点，空节点）是黑色的。
  7. 4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xjZ29pbmc_size_16_color_FFFFFF_t_70 1

图：https://www.cnblogs.com/skywang12345/p/3245399.html

hashMap中的红黑树：

  1. /**
  2.      * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
  3.      * extends Node) so can be used as extension of either regular or
  4.      * linked node.
  5.      */
  6.     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  7.         TreeNode<K,V> parent;  // 红黑树的父节点
  8.         TreeNode<K,V> left;
  9.         TreeNode<K,V> right;
  10.         TreeNode<K,V> prev;    // 删除需要取消的节点
  11.         boolean red;
  12.         TreeNode(int hash, K key, V val, Node<K,V> next) {
  13.             super(hash, key, val, next);
  14.         }
  16.         /**
  17.          * Returns root of tree containing this node.
  18.          */
  19.         final TreeNode<K,V> root() {
  20.             for (TreeNode<K,V> r = this, p;;) {
  21.                 if ((p = r.parent) == null)
  22.                     return r;
  23.                 r = p;
  24.             }
  25.         }

它是继承于LinkedHashMap.Entry的，从这里也可以看到LinkedHashMap底层是一个链表

  1. /**
  2.      * HashMap.Node subclass for normal LinkedHashMap entries.
  3.      */
  4.     static class Entry<K,V> extends HashMap.Node<K,V> {
  5.         Entry<K,V> before, after;
  6.         Entry(int hash, K key, V value, Node<K,V> next) {
  7.             super(hash, key, value, next);
  8.         }
  9.     }

hashMap是一种牺牲空间换取查找等操作时间的设计，所以空间转化率特别低，在面向对象的思想中不要滥用。

发表评论

表情：
评论列表 （有 0 条评论，540人围观）

还没有评论，来说两句吧...

相关阅读

    相关 HashMap源码解析

    一.HashMap概述 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作， 并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它

    落日映苍穹つ落日映苍穹つ/ 0 赞/ 431 阅读

    相关 HashMap源码解析

    来不及整理电子版，先献丑把笔记本拍几张，随后整理。 有人问，什么年代了，还手写笔记，哈哈，如果不亲自手写一遍，我是真心记不住。很多API不用知道工作原理 一样可以使用，所以

    本是古典 何须时尚本是古典 何须时尚/ 0 赞/ 485 阅读

    相关 HashMap源码解析

    埋坑 这个必须写 1，hash方法 问：为何扩容是翻倍（乘以2） 2，get方法 3，put方法 问：为什么hash值冲突后，list变为红黑树的节点是8

    快来打我*快来打我*/ 0 赞/ 411 阅读

    相关 HashMap源码解析

    源码博客相关博客写了那么多，突然想起来都没有写一篇我们日常开发中最常见的HashMap,今天简单补一下！ HashMap简介： `HashMap` 是应用更加广泛的哈希

    左手的ㄟ右手左手的ㄟ右手/ 0 赞/ 485 阅读

    相关 hashMap源码解析

    源码来自jdk：1.8，和其他jdk版本可能有少许差异。 一.hashMap的实现原理     hashMap底层是一个有Node组成的数组，每个Node都有一个key

    冷不防冷不防/ 0 赞/ 541 阅读

    相关 HashMap源码解析

    本文的所有图片以及源码解析内容都来自于微信公众号<java知音>，原文作者:阿进的写字台。此处仅是对该公众号分享的内容进行一下消化吸收，不作传播。想要阅读原文，可以关注这个公众

    Love The Way You LieLove The Way You Lie/ 0 赞/ 536 阅读