您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Java8 HashMap关键源码阅读,以及Java7头插法与Java8尾插法理解。

一,HashMap的底层数据结构

Java8 中HashMap的底层数据结构是数组+链表,当数组长度达到64或者链表长度达到8时,将会把链表转化为红黑树

1.HashMap的存取原理

put方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 当前哈希表为空,则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // 直接调用resize方法,返回长度,默认16
            n = (tab = resize()).length;
        // index的计算方法 (n - 1) & hash n是tab的Leagth
        // 没有hash碰撞,则直接挂在tab[index]下
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 哈希值相等,key也equals相等,覆盖value
            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);
                        // 链表节点数量 >= 8 转化为红黑树
                        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;
                }
            }
            // e不是空,有需要覆盖的节点
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 空函数 Callbacks to allow LinkedHashMap post-actions
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 插入新节点完毕,修改modCount
        ++modCount;
        
        // 更新size 判断是否需要扩容
        if (++size > threshold)
            resize();
        // 空函数 Callbacks to allow LinkedHashMap post-actions
        afterNodeInsertion(evict);
        return null;
    }

get方法 

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 // 传入扰动后的哈希值 和 key
 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);
            }
        }

2.resize,扩容,以及重新hash(rehash)

什么时候resize?

HashMap的默认负载因子是0.75f,所以当HashMap数组的长度大于容量*0.75的时候,会对HashMap进行resize处理。

扩容分为两步,

首先,创建一个新的Entry空数组,长度是原来数组的两倍。

然后,进行ReHash操作,遍历原Entry数组,把所有的Entry重新Hash到新数组。

resize后是一定需要进行rehash的,因为index的计算与数组的长度相关,长度扩大之后,hash计算出来的值自然就发生了变化,这个会在下面hash计算展开详细描述。

对应HashMap源码位于resize()方法707行,往新的数组放元素进行了rehash。

3.Java7的头插法与Java8的尾插法

为什么Java7采用头插法,而Java8却改成了尾插法?

头插法插入会改变链表的顺序,导致并发情况下可能出现环形链表的情况,而改为尾插法之后,由于新插入元素之后维持原来链表的顺序不变,不会有环形链表的情况出现,但是在并发的情况下,会出现值覆盖的情况。

二,HashMap的主要参数都有哪些?

/**
 * The default initial capacity - MUST be a power of two.
 * 初始化容量必须是2的次方
 */
// 默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 树形化最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

1.初始化容量为什么是16,为什么都要是2的次方?

为了实现数据的均匀分布

首先了解index(HashMap底层是数组和链表)的计算规则,index = HashCode(Key) & (Length- 1) ,key的hash值与当前Node数组的长度做位运算。

奇数为什么不行?

由index的计算方法得知,Length为奇数,Length- 1为偶数,偶数二进制结尾都是0,经过&运算后,index的末尾也都会时0,这样就会增加hash冲突。

2的倍数为什么不行?

2的幂数经过Length-1之后,二进制时二进制位全为1,这样计算的index等同于HashCode的后几位的值。

因为当Length为2的幂时,会满足(Length - 1) & hash = hash % Length,位运算的结果与取模的结果一直,index的计算效率更加高效。

2.默认负载因子为什是0.75?

负载因子:是哈希表在其容量自动扩容之前可以达到多满的一种度量。

首先看源码关于0.75有以下这样一段描述

关键内容是,分布良好的hash,树结构是很少用到的,理想情况下,节点服从泊松分布(Poisson distribution),调整大小的参数平均是0.5,0.75与0.5差异很大,以为考虑调整粒度以及忽略方差。

总结来说,0.75作为默认的加载因子,是时间和空间成本上寻求的一种折衷选择

0.5的话,虽然可以减少查询时间成本,但是空间的利用率过低,也就意味着会提高rehash操作的次数。

3.链表转红黑树的阈值为什么是8?

首先链表转红黑树是很消耗性能的,也就是说我们要尽可能减低树化的可能性。

还是上面的那张图,可以看到一个链表中达到8个元素的概率为 0.00000006,几乎是不可能事件,所以8应该是统计概率之后的最优选择。

三,HashMap中Hash的计算规则

1.HashMap是怎么处理hash碰撞的?

Hash碰撞或者Hash冲突,指的是计算hash之后所得的Index一致,即发生了hash碰撞,可以看下上面提到的头插法与尾插法,其实就是发生hash碰撞后如何添加数据的。

Java7中的解决办法是链表,Java8变成了链表+红黑树。

2.为什么重写equals方法时需要重写hashCode方法?

首先需要了解Object的hashCode和equals方法

通过源码我们可以很明显看出,hashCode方法返回的是一个整数,

而equals判断的是参数与当前对象thiis是否相等,这里的对象相等时比较对象的内存地址是否相同,如果内存地址相同,这两个对象相同。

所以,对象相等时,hashCode也一定相等,但是hashCode不同时,对象一定不相等,先比较hashCode可以减少equals比较次数,提高效率。

我们还知道,index的计算是index = HashCode(Key) & (Length- 1),是与HashCode相关的,如果计算得出的index一致,那么就需要使用equals方法去确定同一个index位置的对象哪一个才是我们需要的那个对象。

总结来说,重写equals方法一定要重写hashCode方法是为了,保证不同的对象有不同的hashCode,相同的对象有同一个hashCode。

四,HashMap是否是线程安全

1.为啥会线程不安全?

Java7头插法并发情况下出现环形链表,transfer方法

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

 

而Java8还是之前提到的putVal()方法,由于没有锁,当线程A和线程B同时执行put,

Thread A 下图625行判断了tab[index] 为null,可以插入,但是还没有插入时,没有时间片而暂时挂起,

此时线程B也同样进行插入操作,而且同一个tab[index]位置正常插入元素,

之后,Thread A 再次执行626行put操作,就会把Thread B插入的元素覆盖。

2.有什么线程安全的类可以替代?

a.Hashtable,对所有方法加锁(synchronized),所有线程锁的都是当前对象,锁的粒度太大。

b.ConcurrentHashMap,get时没有锁,put时有锁,锁的粒度比较小。

c.Collection.SynchronizedMap,锁的是同一个对象,每次锁的都是当前整张表,锁的粒度太大。

五,HashMap的红黑树操作

还没整理,先送上一篇文章连接,https://zhuanlan.zhihu.com/p/80587365

 

 

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进