博客

HashMap

  • Post author:
  • Post category:其他


文章目录

HashMap 是一个最通用的利用哈希表存储元素的集合，将元素放入 HashMap 时，将key的哈希值转换为数组的索引下标确定存放位置，查找时，根据key的哈希地址转换成数组的索引下标确定查找位置。

HashMap 底层是用数组 + 链表 + 红黑树这三种数据结构实现，它是非线程安全的集合。


在这里插入图片描述



整体架构

HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。其中当

链表的长度大于等于 8 并且数组的大小大于64时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表

，整体的数据结构如下：

在这里插入图片描述

图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树，比如数组下标索引为 1 的位置就是一个链表，下标索引为 8 的位置对应的就是红黑树。


源码类注释

通过类注释可以获取一下信息：

  • 允许 null 值，不同于 HashTable ，是线程不安全的；
  • load factor（负载因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 > 需要的数组大小 /load factor，可以查看

    散列表

    这种数据结构。
  • 建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
  • HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；
  • 在迭代过程中，如果 HashMap 的结构被修改，会快速失败。


常见的属性
 

/**
 * The default initial capacity - MUST be a power of two.  
 * 初始容量是16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.  
 * 最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.  
 * 负载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  * The bin count threshold for using a tree rather than list for a
  * bin.  Bins are converted to trees when adding an element to a
  * bin with at least this many nodes. The value must be greater
  * than 2 and should be at least 8 to mesh with assumptions in
  * tree removal about conversion back to plain bins upon
  * shrinkage.  
  * 链表长度大于等于8时，链表转化成红黑树
  */
 static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.  
 * 红黑树大小小于等于6时，红黑树转化成链表
 */
    static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.  
 * 数组容量大于 64 时，链表才会转化成红黑树
 */
static final int MIN_TREEIFY_CAPACITY = 64;

 //记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
 transient int modCount;

 //HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
 transient int size;

 //存放数据的数组
 transient Node<K,V>[] table;

 // 扩容的门槛，有两种情况
 // 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
 // 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
 int threshold;

 //链表的节点
 static class Node<K,V> implements Map.Entry<K,V> {
 
 //红黑树的节点
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {


HashMap的主要操作
 

// 初始化方法一(第二个参数负载因子是单精度浮点型)
Map<String, String> kvHashMap = new HashMap<>(16,  0.7f);

//初始化方法二
HashMap<Object, Object> objectObjectHashMap = new HashMap<>();

// 初始化方法三
HashMap<String, String> hashMap1 = new HashMap<>(kvHashMap);

// 初始化方法四
Map<String, Double> hashMap = new HashMap<>(16);
hashMap.put("k1", 0.1);
hashMap.put("k2", 0.2);
hashMap.put("k3", 0.3);
hashMap.put("k4", 0.4);
Double aDouble = hashMap.putIfAbsent("k5", 1.2);
for (String s : hashMap.keySet()) {
    System.out.println(hashMap.get(s));
}



新增


新增 entry 大概的步骤如下：

1：空数组有无初始化，没有的话初始化；

2：如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3；

3：如果 hash 冲突，两种解决方案：链表 or 红黑树；

4：如果是链表，递归循环，把新元素追加到队尾；

5：如果是红黑树，调用红黑树新增的方法；

6：通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖；

7：判断是否需要扩容，需要扩容进行扩容，结束。


代码如下：
 

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key：通过hash算法计算出来的值
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value：false表示即使key值已经存在了，仍然用新值覆盖
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;// n：数组长度，i：数组索引下标，p：i下标位置的node值
    if ((tab = table) == null || (n = tab.length) == 0)// 如果数组为空，使用resize方法初始化
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)// 如果当前索引位置是空的，直接生成新的节点在当前索引上
        tab[i] = newNode(hash, key, value, null);
    else { //如果当前索引位置有值的处理方法，需要解决 hash 冲突
        Node<K,V> e; K k;   // e 当前节点的临时变量，临时存储位置
        if (p.hash == hash &&   // 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量
            ((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) // -1 for 1st
                        treeifyBin(tab, hash);// 当链表的长度大于等于 8 时，链表转红黑树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;// 链表遍历过程中，发现有元素和新增的元素相等，结束循环
                p = e;//更改循环的当前元素，使 p 在遍历过程中，一直往后移动。
            }
        }// 说明新节点的新增位置已经找到了
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)// 当 onlyIfAbsent 为 false 时，才会覆盖值
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//如果 HashMap 的实际大小大于扩容的门槛，开始扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}



链表的新增节点过程

链表的新增比较简单，就是把当前节点追加到链表的尾部，和 LinkedList 的追加实现一样的。当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，

当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树。


为什么当链表长度大于等于 8 时，链表才会转化成红黑树？

链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以需要定义出转化的边界值。



红黑树的新增节点过程


红黑树新增节点的过程大概分为以下几个步骤：

1：判断新增节点是否在红黑是中已经存在，判断手段有两种：

  • 如果节点没有实现 Comparable 接口，使用

    equals

    进行判断；
  • 如果节点自己实现了 Comparable 接口，使用

    compareTo

    进行判断。

2：如果新增节点已经在红黑树中，直接返回，不在的话判断新增节点是在当前节点的左边还是右边，左边小右边大。

3：自旋递归 1 和 2 步，

直到当前节点的左边或者右边的节点为空时

，停止自旋，

当前节点即为我们新增节点的父节点

；

4：

把新增节点放到当前节点的左边或右边为空的地方

，并于当前节点建立父子节点关系；

5：进行

着色和旋转

，结束。


源代码如下：
 

/**
 * Tree version of putVal.  红黑树的新增节点过程
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}



查找


HashMap 的查找主要分为以下三步：

1：根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话往下。

2：判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。

4：分别走链表和红黑树不同类型的查找方法。


主要代码如下：
 

// 采用自旋方式从链表中查找 key，e 初始为为链表的头节点
do {
    // 如果当前节点 hash 等于 key 的 hash，并且 equals 相等，当前节点就是我们要找的节点
    // 当 hash 冲突时，同一个 hash 值上是一个链表的时候，我们是通过 equals 方法来比较 key 是否相等的
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
    // 否则，把当前节点的下一个节点拿出来继续寻找
} while ((e = e.next) != null);


版权声明：本文为weixin_43894879原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
Tags: