您的位置: 首页  >  文章  >  Java基础之HashMap(二)

Java基础之HashMap(二)

分类: 文章 • 2024-01-12 22:46:04

文章目录

1. 导读

经过上期的分享, 相信大家对HashMap已经有了个初步的印象, 今天将围绕下面几个问题展开:
.1 HashMap的数据结构在java中是如何设计的;
.2 HashMap序列化的问题;

2. hash槽长度的确定

我们将围绕下面HashMap的数据结构和关键代码来看HashMap的设计:
Java基础之HashMap(二)

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;

DEFAULT_INITIAL_CAPACITY定义了上图中hash槽的默认大小; 而MAXIMUM_CAPACITY则定义了hash槽的最大值;那么hash槽的长度是[2^4, 2^30], 设计者是采用了何种机制来实现这个的呢?

     static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap::tableSizeFor是确定hash槽长度的核心方法, 我们来看下这个方法干了什么:
.1 因为hash槽的编码是从0开始的, 所以需要将传入的长度-1;
.2 经过5次扰动以后得到新的hash槽长度;
.3 如果结果小于0, 则返回0; 否则判断是否大于最大值了, 如果大于, 则返回最大值, 这个时候不管冲突如何严重, HashMap不会再次扩容了; 反之则直接返回结果;
我们来看下为什么要经过5次扰动;
在DEFAULT_INITIAL_CAPACITY上面设计者特别强调了HashMap的初始化值一定要是2的倍数(为什么这么设计的原因我们后面说), 但是我们通过HashMap的构造函数指定一个非2的倍数的数字, 这个时候不就违背了这个设计吗?

    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的构造函数, 构造函数还是去调用HashMap::tableSizeFor来计算当前hash槽的所需的长度, 然后赋值给threshold(这个具体作用后面说, 这里理解为当前hash槽的长度即可);
那么经过这5次扰动就一定可以得到2的倍数的长度吗? 我们以27为例( | 的作用是只有都为0时, 结果才为0, 否则都是1):

    0001 1100
    0000 1111 (>>>1)
  |:0001 1111
    0000 0011 (>>>2)
  |:0001 1111  
    0000 0000 (>>>4)
  |:0001 1111 (到这步其实值已经固定了)
    0000 0000 (>>>8)
  |:0001 1111    
    0000 0000 (>>>16)
  |:0001 1111

可以看到在右移四位的时候, 结果就已经固定了, 就是32, 所以经过HashMap::tableSizeFor扰动得到的长度一定是大于等于输入值得(只有在输入2的倍数时才会等于, 否则都会得到一个离输入值最近的大于输入值得2的倍数, 且这个值必定大于等于16);
所以new HashMap(1), 是不会像我们所想的那样指定长度为1的hash槽的, 他的长度是2;

3. 数据节点的设计

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        ...
    }

通过源码, 我们可以看到设计者将HashMap的存储节点设计成了单链表, 每个数据节点存储key(键值), value(存储的值), hash(当前节点的哈希码)和 next(指向下个节点的指针);
但是在JKD8中又引入了红黑树, 我们来看下红黑树的存储结构:

     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
    ...
}

通过HashMap.TreeNode的源码可看到:
.1 维护了parent(父节点), left(左子节点), right(右子节点)的双向链表(继承了LinkedHashMap.Entry是双向链表);
.2 red: 标识该节点的颜色;
.3 prev放到红黑树的删除中讲解;

那么JDK8中是如何判断什么时候链表会升级成红黑树, 红黑树又在什么条件时变为链表呢?

    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;

TREEIFY_THRESHOLD定义的是当链表长度大于8时, 需要升级成红黑树;
UNTREEIFY_THRESHOLD定义的是当红黑树的节点数少于6时, 需要变为链表;
至于为何是8 和 6, 因为log(8)的结果是平均查找长度为3, 而链表的平均查找长度是4, 所以才有了转换的必要; 同理当长度是6的时候, 链表的平均查找长度也是3了, 那么从树转为链表也就能理解了;
至于为什么不是只采用8作为黑红树和链表的转换条件, 那是因为6 和 8之间有个7可以作为缓冲; 如果HashMap某个槽的长度不断地做增删, 就不要频繁的做树与链表的变换了;

4. hash槽的设计

    transient Node<K,V>[] table;
     int threshold;

.1 table是hash槽的底层实现, 可以看到是一个Node(数据节点)数组;
.2 threshold记录的是当前的hash槽的长度;
不知道大家有没有疑问, 我们获取hash槽的长度不就是table.length吗? 为什么还需要设计一个threshold属性来存储呢?
这就需要说到HashMap的设计了:

    public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
        ...
    }

我们关注下Serializable这个关键字, 这表示HashMap是可序列化的;但是我们也要关注到table也有个关键修饰:transient; transient是告诉虚拟机, 不要序列化这个字段, 至于为什么不序列化table这个字段, 我们后面再说; 正因为这么设计, 所以才需要通过threshold在反序列化的时候告诉虚拟机, 这个HashMap的hash槽长度是多少;

5. hashMap的序列化问题

前面我们说到了table(hash槽)是不会被序列化的, 那么HashMap为什么这么设计呢?
这个就需要用到前面的知识了:HashMap::hash, 这个方法是用来确定key的hash值得, 然后再来确定这个key位于哪个hash槽; 但是我们要知道,Object::hashCode是依赖于虚拟机的底层实现的, 所以当一个HashMap在不同虚拟机之间序列化的时候, 同一个key是有可能位于不同的hash槽的,所以HashMap在序列化的使用了HashMap::writeObject来输出必须字段, 然后再使用
HashMap::readObject来读取并重新生成HashMap;

HashMap::writeObject来输出必须字段:
.1 当前table的长度;
.2 每个Node的key, value;

HashMap::readObject:
.1 根据获取到的table的长度重新生成一个对应长度的hash槽;
.2 然后把每个Node插入到新的hash槽中;

本期的分享主要是这些, 如果有不足之处欢迎指正;
如果上面的内容对你有帮助, 烦请点赞转发, 谢谢;

相关推荐