HashMap以及ConcurrentHashMap(volatile)

2,511 阅读5分钟

1.HashMap怎么实现hashcode和equals

HashMap的数据结构是链表+数组,HashMap的数据结构类似于:

元素0->[hashCode=0,key.value=x1的数据]
元素1->[hashCode=1,key.value=y1的数据]
...
元素n->[hashCode=n,key.value=n1的数据]

hashMap的put和get方法都会调用hashCode方法,如果两个hashCode有冲突,再调用equals方法:

put():会调用对象的hashCode()方法来计算hashcode,然后找到buchet(桶)位置来储存对象,当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。hashMap通过链表来解决冲突问题,如果发生碰撞,对象就会储存在链表的下一节点。

get():buchet(桶)里的第一个节点,直接命中;如果有冲突,则通过key.equals(k)去找对应的可以。

为什么要重写hashCode()和equals():

首先先来看一下equals:

public boolean equals(Object obj){
    return (this==obj);
}

是通过==来比较两个对象的引用地址,Object的equals只是简单的判断是不是同一个实例,但如果我们需要比较逻辑上的相等,就需要重写equals()方法,而涉及到HashMap的时候,重写了equals()就需要重写hashCode()方法。

2.concurrentHashMap怎么实现

采用了“分段锁”的方式来确保线性安全,相比于HashTable,不会存在锁竞争,可以有效的提高并发效率。

concurrentHashMap的主干是Segment数组

final Segment<K,V>[] segment;

Segment继承了ReentrantLock,所以它就是一种“可重入锁”。在concurrentHashMap中一个Segment就相当于一个子哈希表,Segment里维护了一个HashEntry数组,在并发情况下,不需要考虑锁的竞争。

#Segment:
transient volatile HashEntry<K,V>[] table;

一个ConcurrentHashMap维护一个Segment,一个Segment维护一个HashEntry,对于同一个Segment才考虑线程同步,不同Segment不需要考虑。

jdk7中:

put():1.定位segment并确保定位的Segment已初始化 2.调用Segment的put方法

get():get无需加锁,由于其涉及的共享变量都使用volatile修饰,volatile可以保证内存可见性,所以不会读取过期数据。

jdk8中:

put():沿用了hashMap中的put,根据hash值计算这个新插入的点在table中的位置i,如果i位置是空的,直接放进去,否则进行判断,如果i位置是树节点,按照树的方式插入新的节点,否则把i插入到链表的末尾,但是不允许key或value为null。

调用的是putVal方法

public V put(K key, V value) {    return putVal(key, value, false);}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());// 计算key的hash值
    int binCount = 0;// 表示table中索引下标代表的链表或红黑树中的节点数量
    // 采用自旋方式,等待table第一次put初始化完成,或等待锁或等待扩容成功然后再插入
    for (Node<K,V>[] tab = table;;) {
        // f节点标识table中的索引节点,可能是链表的head,也可能是红黑树的head
        // n:table的长度,i:插入元素在table的索引下标,fh : head节点的hash值
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)// 第一次插入元素,先执行初始化
            tab = initTable();
        // 定位到的索引下标节点(head)为null,表示第一次在此索引插入,
        // 不加锁直接插入在head之后,在casTabAt中采用Unsafe的CAS操作,保证线程安全
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // head节点为ForwadingNode类型节点,表示table正在扩容,链表或红黑树也加入到帮助扩容操作中
        else if ((fh = f.hash) == MOVED) 
            tab = helpTransfer(tab, f);
        else {// 索引下标存在元素,且为普通Node节点,给head加锁后执行插入或更新
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {// 为普通链表节点,还记得之前定义的几种常量Hash值吗?
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // 插入新元素,每次插在单向链表的末尾,这点与Java7中不同(插在首部)
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {// head为树节点,按树的方式插入节点
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 链表节点树超过阈值8,将链表转换为红黑树结构
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 如果是插入新元素,则将链表或红黑树最新的节点数量加入到CounterCells中
    addCount(1L, binCount);
    return null;
}

get():

1、计算key的hash值,并定位table索引
2、若table索引下元素(head节点)为普通链表,则按链表的形式迭代遍历。
3、若table索引下元素为红黑树TreeBin节点,则按红黑树的方式查找(find方法)。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {// 普通链表
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // hash值小于-1,即为红黑树,还记得之前定义的TreeBin节点的hash值吗
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {// 匹配下一个链表元素
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

3.volatile

volatile实现的是可见性,即一个线程的修改对另一个线程是可见的。也就是一个线程修改结果,另一个线程马上能看到。

当把变量声明为volatile类型后,编译器与运行时都会注意到这个变量是共享的,因此不会将该变量上的操作与其他内存操作一起重排序,在访问volatile变量时不会执行加锁操作,因此也就不会使执行线程阻塞,因此volatile变量是一种比sychronized关键字更轻量级的同步机制。