乐趣区

关于java:详解HashMap源码解析上

jdk 版本:1.8

数据结构:

HashMap的底层次要基于 数组 + 链表 / 红黑树 实现,数组长处就是 查问块 HashMap 通过计算 hash 码 获取到数组的下标来查问数据。同样也能够通过 hash 码 失去数组下标,存放数据。

哈希表为了解决抵触,HashMap采纳了 链表法, 增加的数据寄存在链表中,如果发送抵触,将数据放入链表尾部。

上图左侧局部是一个哈希表,也称为哈希数组(hash table):

// table 数组
transient Node<K,V>[] table;

table数组的援用类型是 Node 节点,数组中的每个元素都是 单链表 的头结点,链表次要为了解决下面说的hash 抵触,Node 节点蕴含:

  • hash hash 值
  • key
  • value
  • next next 指针

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;
    }
    // 省略 get/set 等办法
}

次要属性

// 贮存元素数组
Node<K,V>[] table;

// 元素个数
int size;

// 数组扩容临界值,计算为:元素容量 * 装载因子
int threshold

// 装载因子,默认 0.75
float loadFactor;

// 链表长度为 8 的时候会转为红黑树
int TREEIFY_THRESHOLD = 8;

// 长度为 6 的时候会从红黑树转为链表
int UNTREEIFY_THRESHOLD = 6;
  • size 记录元素个数
  • threshold 扩容的临界值,等于元素容量 * 装载因子
  • TREEIFY_THRESHOLD 8 链表个数减少到 8 会转成红黑树
  • UNTREEIFY_THRESHOLD 6 链表个数缩小到 6 会进化成链表
  • loadFactor 装载因子,默认为0.75

loadFactor 装载因子等于扩容阈值 / 数组长度,示意元素被填满的程序,越高示意空间 利用率越高 ,然而hash 抵触 的概率减少,链表越长,查问的效率升高。越低 hash 抵触 缩小了,数据查问效率更高。然而示 空间利用率越低 ,很多空间没用又持续扩容。为了平衡 查问工夫 应用空间,零碎默认装载因子为0.75

获取哈希数组下标

增加、删除和查找办法,都须要先获取哈希数组的下标地位,首先通过 hash 算法 算出 hash 值,而后再进行长度取模,就能够获取到元素的数组下标了。

首先是调用 hash 办法, 计算出hash 值

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

先获取 hashCode 值,而后进行高位运算, 高位运算后的数据,再进行取模运算的速度更快。

算出 hash 值之后,再进行取模运算:

(n - 1) & hash

下面的 n 是长度,计算的后果就是数组的下标了。

构造方法

HashMap()

     /**
     * default initial capacity (16)
     *  the default load factor (0.75). 
     */
    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}

设置默认装载因子0.75,默认容量16

HashMap(int initialCapacity)

// 指定初始值大小
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定初始值和默认装载因子 0.75
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);
}

HashMap(int initialCapacity) 指定初始容量,调用 HashMap(int initialCapacity, float loadFactor) 其中loadFactor 为默认的0.75

首先做容量的校验,小于零报错,大于最大容量赋值最大值容量。而后做装载因子的校验,小于零或者是非数字就报错。

tableSizeFor应用右移和或运算,保障容量是 2 的幂次方,传入 2 的幂次方,返回传入的数据。传入不是 2 的幂次方数据,返回大于传入数据并靠近 2 的幂次方数。比方:

  • 传入 10 返回16
  • 传入 21 返回32

# HashMap(Map<? extends K, ? extends V> m)

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

将汇合 m 的数据增加到 HashMap 汇合中,先设置默认装载因子,而后调用 putMapEntries 增加汇合元素到 HashMap 中,putMapEntries是遍历数组,增加数据。

总结

本文基于 jdk1.8 解析 HashMap 源码,次要介绍了:

  • HashMap 是基于 数组 + 链表 / 红黑树 构造实现。采纳 链表法 解决 hash 抵触。
  • Node 节点记录了数据的 keyhashvalue 以及 next 指针。
  • HashMap次要属性:

    • size 元素个数
    • table[] 哈希数组
    • threshold 扩容的阈值
    • loadFactor 装载因子
    • TREEIFY_THRESHOLD 8,链表个数为 8 转成红黑树。
    • UNTREEIFY_THRESHOLD 6,链表个数为 6 红黑树转为链表。
  • 增加、删除以及查找元素,首先要先获取数组下标,HashMap先调用 hasCode 办法,hashCode()的高 16 位异或低 16 位,大大的减少了运算速度。而后再对数组长度进行取模运算。实质就是 取 key 的 hashCode 值、高位运算、取模运算
  • HashMap几个构造方法:

    • HashMap()设置默认装载因子 0.75 和默认容量16
    • HashMap(int initialCapacity)设置初始容量,默认装载因子0.75,容量是肯定要是 2 的幂次方,如果不是 2 的幂次方,减少到靠近 2 的幂次方数。
    • HashMap(Map<? extends K, ? extends V> m)次要是遍历增加的汇合,增加数据。

参考

深入浅出 HashMap 的设计与优化

Java 8 系列之重新认识 HashMap

感觉不错的话,就点个赞吧!

退出移动版