今天要分享的 Java 集合是 Map, 主要是针对它的常见实现类 HashMap 进行讲解(jdk1.8)
什么是 Map 核心方法源码剖析 1. 文档注释 2. 成员变量 3. 构造方法 4.put()5.get()
什么是 Map
Map 是非线性数据结构的主要实现, 用来存放一组键 - 值型数据, 我们称之为散列表. 在其他语言中, 也被称为字典.
HashMap 是一个非常重要的数据结构, 在我们的项目中有大量的运用, 或充当参数, 或用于缓存. 而在面试中, HashMap 也几乎成为了一个 "必考项", 所以今天我们就从源码的角度, 对这种数据结构进行剖析.
首先我们先就使用上, 给出几个先入为主的概念. 有了概念, 再去看源码就会容易很多.
HashMap 的查询速度是 O(1), 它为什么会这么快呢? 因为散列表利用的是数组支持按下标随机访问的特性, 所以散列表其实是对数组的一种扩充, 是由数组演化而来的.
我们来举一个例子, A 班一共有 64 个学生, 学号是唯一的 9 位数. 在一场期末考试中, 如果我们想知道一个学生的成绩, 那么就可以通过学号来定位学生, 然后获取所有的考试信息. 为了便于存储和查询, 我们将学生的学号, 通过编码映射到下标从 1-63 的数组中.
将例子和 HashMap 中的概念对应起来: 学号就是键(key), 也叫做关键字, 学生的信息就是值, 将学号转换成数组下标的映射方法就叫做散列函数(散列函数是散列表的核心), 散列函数计算得到的值就叫作散列值, 也叫做 Hash 值或哈希值.
如果这个班扩充到了 100 个人, 存储成绩的方法不变, 那么一定会有至少 2 个同学的成绩经过散列函数计算出的值相同. 这种现象叫做散列冲突. 为了解决散列冲突, 不出现数据相互覆盖的情况, 散列表会将这两个学生的信息组成一个链表, 存储在数组中, 从而保存多个同学的考试信息, 这种解决散列冲突方法叫做链表法.(解决散列冲突的方法不止这一种, 还有其他的方法, 比如线性探测法).
对这些只要有一个大致的印象就可以, 接下来我们会通过剖析源码的方式, 对散列表的工作原理进行深入的分析.
核心方法源码剖析
这一部分, 选取了 HashMap 的一些核心内容进行讲解. 分别是: 文档注释, 成员变量, 构造方法, put(),hash(),get(),remove().
1. 文档注释
permits null values and the null key
允许存储 null 值和 null 键
The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.
HashMap 近似于 Hashtable, 除了它不同步并且允许 null 值
This class makes no guarantees as to the order of the map
这个类存储数据是无序的
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor
一个散列表有两个影响其性能的参数: 初始值和负载因子
so that the hash table has approximately twice the number of buckets
每次扩容 2 倍
2. 成员变量
- // 默认容量
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- // 最大容量
- static final int MAXIMUM_CAPACITY = 1 << 30;
- // 负载因子: 已用空间 / 总空间, 负载因子平衡了时间和空间成本, 如果负载因子过高, 导致空间成本减少, 查找成本增加, 反之亦然.
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- // 一个哈系桶存储的元素超过 8, 就会将链表转换成红黑二叉树
- static final int TREEIFY_THRESHOLD = 8;
- // 一个哈希桶存储的元素小于 6, 并且是红黑二叉树存储, 那么此时就会将红黑二叉树重新转换成链表
- static final int UNTREEIFY_THRESHOLD = 6;
- // 数据量阈值, 数据量只有大于这一个值, 才会发生树化
- static final int MIN_TREEIFY_CAPACITY = 64;
3. 构造方法
HashMap 的构造方法有 4 种, 我们一般不会修改它的负载因子, 常用的构造方法只有无参构造和传入初始值的构造方法.
- HashMap()
- HashMap(int initialCapacity)
- HashMap(int initialCapacity, float loadFactor)
- HashMap(Map<? extends K,? extends V> m)
- 4.put()
put 中有一个核心的方法, hash(), 即散列方法
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
从 hash 方法中可以看出, 如果传入的 key 是 null, 就会固定的返回 0 位置. 如果传入的 key 不是 null, 那么就会取 key 的 hashCode 方法的返回值, 记做 h, 返回 h 与 h 高 16 位的异或值.
hash()方法的这段代码, 又被称为扰动函数, 我们可以思考一下, h 的值是一个 int, 它的范围是[-2147483648, 2147483647], 大概包含了 40 亿的映射空间. 如果直接存到内存中, 肯定是存不下的, 而且 HashMap 的初始值只有 16, 那么我们就需要将 h 映射到这 16 个哈希桶中, 可以直接取模, 但是这样的效率不是很高, 所以这里 jdk 使用了位与的方法, 代码抽象如下:
- private int getIndex(int length, int h){
- return h & (length - 1);
- }
这里可以解释一下, 为什么 HashMap 要求初始值是 2 的整次幂?, 这样 length - 1 正好相当于一个低位掩码, 只截取了低位的值.
但是这里有一个问题, 即使我们的散列函数设计的再松散, 那么当屏蔽掉高位, 只看低位的时候, 还是会容易发生散列冲突. 此时扰动函数的价值就体现出来了, 它将自身的高半区 (32bit) 和低半区 (32bit) 做异或, 这样既增加了随机性, 又将高位的信息变相的参杂了进来.
这里的 getIndex 函数除了位运算性能高, 还有一个好处, 这里扩容前后, h 的值是不变的, 只跟 key 有关. 那么 length - 1 的值, 只会增加一个高位 1, 所以经过 getIndex 计算的值, 有一定几率保持不变(增加的高位, 对应 h 的位是 0), 扩容时, 就会少进行一些数据的搬运, 即扩容时数据是黏性的.
讲完了 hash(),put()方法的核心思想就差不多讲完了, 接下来我们将屏蔽一些实现细节, 来讲一下剩下的 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;
- // 当散列表为 null 的时候, 调用 resize()进行初始化
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 如果没有发生哈希碰撞, 直接将元素存进哈希桶
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // 如果发生了哈希碰撞
- Node<K,V> e; K k;
- if (p.hash == hash &&
- ((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);
- break;
- }
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- if (e != null) { // 覆盖元素
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- if (++size > threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
这里的扩容方法是 resize(), 每次扩容 2 倍, 采用的也是数据搬运的方式, 所以我们要尽可能的去避免 HashMap 的扩容.
- 5.get()
- public V get(Object key) {
- Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
- 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) {
- // 根据节点类型, 在红黑二叉树或者链表中查询数据
- if (first instanceof TreeNode)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- do {
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
get()的思想和 put()类似, 根据不同的 Node 类型, 进行查找
最后, 期待您的订阅和点赞, 专栏每周都会更新, 希望可以和您一起进步, 同时也期待您的批评与指正!
来源: http://www.bubuko.com/infodetail-3445968.html