一、HashMap

以JDK7为例

1.1 介绍

  1. HashMap 是一种存取高效但不保证有序的常用容器。它的数据结构为“数组+链表”,是解决哈希冲突的产物,也就是我们常说的链地址法。它实现了Map 接口采用K-V 键值对存储数据,并实现了浅拷贝和序列化。
  2. HashMap 的默认初始大小为16,初始化大小必须为2的幂,最大大小为2的30次方。
  3. 数组中存储的链表节点Entry 类实现于Map.Entry 接口,它实现了对节点的通用操作。
  4. HashMap 的阈值默认为“容量*0.75f”,当存储节点数量超过该值,则对map 进行扩容处理。
  5. 在第一次添加操作中,HashMap 会先判断存储数组有没有初始化,如果没有就先进行初始化操作,初始化过程中会取比用户指定的容量大的最近的2 的幂次方数作为数组的初始容量,并更新扩容的阈值。

1.2 添加操作

//put方法
    public V put(K key, V value) {
		//1.先判断有没有初始化数组
        if (table == EMPTY_TABLE) {
			//如果没有,会取比用户指定的容量大的最近的2 的幂次方数作为数组的初始容量,并更新扩容的阈值。
            inflateTable(threshold);
        }
		
		//2.再判断传入的key 是否为空,
        if (key == null)
			//为空保存在table[o] 位置
            return putForNullKey(value);
			
		//3.若key不为空,则对key 进hash
        int hash = hash(key);
		
		//4.hash 的结果再& 数组的长度就得到存储的位置
        int i = indexFor(hash, table.length);	
		
		//5.遍历非空链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
			// 如果key已经存在
            if (e.	 == hash && ((k = e.key) == key || key.equals(k))) {
				// 则覆盖旧value,并返回旧value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
		
		//6.如果key不存在,构建节点添加到链表头(比起加到链表尾效率更高)
        modCount++;
        addEntry(hash, key, value, i);
		
        return null;
    }
//put操作时添加节点
void addEntry(int hash, K key, V value, int bucketIndex) {
		//7.添加还要先判断存储的节点数量是否达到阈值,到达阈值且数组对应位置不为空则进行扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
			//8.扩容扩2倍
            resize(2 * table.length);
			//9.扩容结束后新插入的元素也得再hash 一遍才能插入。
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
		//多线程下产生hash碰撞,调用createEntry会产生更新丢失的情况
        createEntry(hash, key, value, bucketIndex);
    }
//扩容2倍
void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
		//8.1 是新建数组所以要先转移节点
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
	//遍历并转移节点,头插法,多线程下可能会出现循环链表导致死循环
    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;
				//8.2 转移时可能会重新hash,但默认情况下基本不会重新hash
                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;
            }
        }
    }

1.3 问题及解决

问题
  1. HashMap 是一个并发不安全的容器,在迭代操作是采用的是fast-fail 机制,在并发添加操作中会出现丢失更新的问题;
  2. 因为采用头插法在并发扩容时会产生环形链表的问题,导致CPU 到达100%,甚至宕机。
解决
  1. Java 类库提供的Collections 工具包下的Collections.synchronizedMap()方法,返回一个线程安全的Map
  2. 或者使用并发包下的 ConcurrentHashMap,ConcurrentHashMap采用分段锁机制实现线程安全
  3. 使用HashTable (不推荐)

1.4 与JDK8的区别

  1. Hash1.7 和1.8 最大的不同在于1.8 采用了“数组+链表+红黑树”的数据结构,在链表长度超过8 时,把链表转化成红黑树来解决HashMap 因链表变长而查询变慢的问题
  2. 在hash 取下标时将1.7 的9次扰动(5次按位与和4次位运算)改为2次(一次按位与和一次位运算)
  3. 1.7的底层节点为Entry,1.8 为node ,但是本质一样,都是Map.Entry 的实现
  4. 1.8在存取数据时添加了关于树结构的遍历更新与添加操作,并采用了尾插法来避免环形链表的产生,但是并发丢失更新的问题依然存在。

1.5 容量为2的幂

  1. 2的n次幂转化为二进制为1后面n个0,在计算下标的时候是hash&(n-1),n-1的二进制位都是1。
    当(n - 1) 和 hash 做与运算时,会保留hash中 后 x 位的 1,例如 00001111 & 10000011 = 00000011
  2. &运算速度快,至少比%取模运算块
  3. 能保证 索引值 肯定在 capacity 中,不会超出数组长度

1.6 负载因子0.75

空间与时间的均衡

  1. 如果负载因子小,意味着阈值变小。比如容量为10 的HashMap,负载因子为0.5f,那么存储5个就会扩容到20,出现哈希冲突的可能性变小,但是空间利用率不高。适用于有足够内存并要求查询效率的场景。
  2. 相反如果阈值为1 ,那么容量为10,就必须存储10个元素才进行扩容,出现冲突的概率变大,极端情况下可能会从O(1)退化到O(n)。适用于内存敏感但不要求要求查询效率的场景

1.7 hash()的意义

hash 算法的好坏直接影响hash 结构的效率,坏的hash 算法极端情况下可能会使hash 结构的存取效率从O(1)退化到O(n)。1.8 之所以把9 次扰动降到2 次,是出于计算效率的考虑。

二、ConcurrentHashMap

ConcurrentHashmap(1.8)这个并发集合框架是线程安全的,但源码中的get操作全程是没有加任何锁的
image.png

2.1 简介

  1. 在jdk1.7中ConcurrentHashmap是采用Segment + HashEntry + ReentrantLock的方式进行实现的,而1.8中放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现。
  2. JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
  3. JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
  4. JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档

2.2 get操作

//会发现源码中没有一处加了锁
public V get(Object key) {
    Node<K,V>[] tab; 
	Node<K,V> e, p; 
	int n, eh; 
	K ek;
    int h = spread(key.hashCode()); //计算hash
    if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
        if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来
        //eh=-1,说明该节点是一个ForwardingNode,正在迁移,此时调用ForwardingNode的find方法去nextTable里找。
		//eh=-2,说明该节点是一个TreeBin,此时调用TreeBin的find方法遍历红黑树,由于红黑树有可能正在旋转变色,所以find里会有读写锁。
        //eh>=0,说明该节点下挂的是一个链表,直接遍历该链表即可。
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历
            if (e.hash == h &&
             ((ek = e.key) == key || (ek != null && key.equals(ek))))
                 return e.val;
        }
    }
    return null;
}

get没有加锁的话,ConcurrentHashMap是如何保证读到的数据不是脏数据的呢?

2.3 volatile

  1. 对于可见性,Java提供了volatile关键字来保证可见性、有序性。但不保证原子性。
  2. 普通的共享变量不能保证可见性,因为普通共享变量在线程本地被修改之后,什么时候被写入主存是不确定的,当其他线程去读取主存时,此时内存中可能还是原来的旧值,因此无法保证可见性。
  3. volatile关键字对于基本类型的修改可以在随后对多个线程的读保持一致,但是对于引用类型如数组,实体bean,仅仅保证引用的可见性,但并不保证引用内容的可见性。
  4. 禁止进行指令重排序。
用volatile修饰的Node

get操作可以无锁是由于Node的元素val和指针next是用volatile修饰的,在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey() { return key; }
    public final V getValue() { return val; }
    public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
          (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
          (v = e.getValue()) != null &&
          (k == key || k.equals(key)) &&
          (v == (u = val) || v.equals(u))); 
    }

    /**
    * Virtualized support for map.get(); overridden in subclasses.
    */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                 ((ek = e.key) == k || (ek != null && k.equals(ek))))
                   return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

既然volatile修饰数组对get操作没有效果,那加在数组上的volatile的目的是什么呢?
其实就是为了使得Node数组在扩容的时候对其他线程具有可见性而加的volatile

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议