JDK 1.7中

HashMap

以数组+链表（单向链表）的形式存储，以Entry对象存储

image-20220104070932257

HashMap中的Entry对象数组：

Entry对象数组

Entry对象中的next指针：

image-20220104070553553

构造方法

构造方法传入初始容量和加载因子，对HashMap中的属性加载因子和阈值进行赋值。调用空参则进行则会赋默认值。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
    //判断初始容量是否小于0
    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;
    //初始容量赋值给阈值
    threshold = initialCapacity;
    //空方法，在LinkedHashMap中有用到
    init();
}

put方法

modCount

public static void main(String[] args) {
        Map<String,String> hashMap = new HashMap();
        hashMap.put("1","1");
        hashMap.put("2","2");

        for (String key : hashMap.keySet()) {
            if(key.equals("2")){
                hashMap.remove(key);
            }
        }

    }

表示HashMap的修改次数，在执行如上的代码时会抛出异常ConcurrentModifycationException。

这是一种快是失败（Fast-Fail）机制，容错机制。是针对如两个线程操作hashmap，一个遍历一个删除的情况，这个情况下hashmap会有安全问题，于是就直接抛出异常，停止执行代码。

public V put(K key, V value) {
    //判断Entry数组是否为空
    if (table == EMPTY_TABLE) {
        //初始化数组
        inflateTable(threshold);
    }
    //判断key是否为null，为null则放入数组第0个位置
    if (key == null)
        return putForNullKey(value);
    //通过hash算法获取key的hash值
    int hash = hash(key);
    //通过hash值和数组长度计算在数组中的位置
    int i = indexFor(hash, table.length);
    //遍历数组下标i上的链表，如果有重复key，则替换并返回旧值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

  	//修改次数
    modCount++;
    //没有重复则添加元素到链表中，采用头插法
    addEntry(hash, key, value, i);
    return null;
}

inflateTable方法

初始化Table的方法。

  1. 首先将传入的阈值（也就是初始容量，构造方法中赋值给阈值）进行inflateTable方法计算，获得大于等于toSize的2的幂次方的数，即为table的容量。
  2. 计算阈值为 加载因子 * 容量
  3. new一个容量为capacity的Entry数组
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
roundUpToPowerOf2方法

获得大于等于number的2的幂次方的数。

为什么初始化数组一定要是2的幂次方数？

在indexFor方法中，会通过hash值和数组的长度来计算数组的下标。通过与操作h & (length-1)时，则需要保证数组的长度为2的幂次方数，才能保证(length-1)得到一个二进制的低位全部为1的数。

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
initHashSeedAsNeeded方法

初始化hash种子

当容量大于配置的值后，就会生成一个hash种子。

hash种子的目的是让生成的hash更加散列。

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
      			//只有满足以下条件时才会初始化hash种子
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

Holder类中关于ALTERNATIVE_HASHING_THRESHOLD的赋值

用户配置了启动参数-Djdk.map.althashing.threshold后，才会有值；否则默认是Integer.MAX_VALUE

static final int static final int ALTERNATIVE_HASHING_THRESHOLD;

static {
  	//3. altThreshold是用户在启动参数中增加的-Djdk.map.althashing.threshold
    String altThreshold = java.security.AccessController.doPrivileged(
        new sun.security.action.GetPropertyAction(
            "jdk.map.althashing.threshold"));

    int threshold;
    try {
      	//2. altThreshold赋值给threshold
        threshold = (null != altThreshold)
                ? Integer.parseInt(altThreshold)
                : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

        // disable alternative hashing if -1
        if (threshold == -1) {
            threshold = Integer.MAX_VALUE;
        }

        if (threshold < 0) {
            throw new IllegalArgumentException("value must be positive integer.");
        }
    } catch(IllegalArgumentException failed) {
        throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
    }
		//1. 将threshold赋值给ALTERNATIVE_HASHING_THRESHOLD
    ALTERNATIVE_HASHING_THRESHOLD = threshold;
}

putForNullKey方法

遍历数组第0个位置上的链表，如果有重复则替换并返回旧值；没有重复则调用addEntry方法将元素添加在第0个位置的链表上。

数组第0个位置上不一定只存了key为NULL的值，其他Key算出来的下标也可能为0

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

hash方法

获取Hash值

  1. 通过hashCode方法获取hash值
  2. 与hash种子进行异或运算
  3. 进行右移与异或运算

为什么要进行右移与异或？而不直接使用hashCode方法返回的值？

在indexFor方法中，使用hash值进行下标的计算时，只保留了hash值的低位，高位全部被舍弃，没有参与到下标的计算中来。如果这里直接使用hashCode方法，hashCode方法时可以被重写的，如果重写的方法散列性很差，那么发生hash碰撞的可能性比较大；而进行右移与异或操作后，影响hash值的改变，则可以让高位也参与到下标的计算中来。增加下标的随机性。

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

indexFor方法

通过hash值获取数组的下标

下标要求：

  1. 取值范围不能超过数组长度
  2. 下标要平均分布在数组中

image-20220106064002892

数组长度为2的幂次方，-1则能得到除最高位为1的一个二进制数，与hash值进行与操作，则保留了hash值地位的所有数。由于只取了地位，所以不会超过数组长度；hash同时也是散列的，所以也满足平均分布的要求。

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

addEntry方法

添加元素到HashMap中来

  1. 判断数组中存放的元素个数是否大于阈值，并且要存放的位置是否不为null，都满足则进行数组的扩容。扩容的容量为旧数组的2倍
  2. 创建元素并使用头插法，将元素插入到链表中
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}
resize方法
  1. 判断旧的容量是否达到最大容量，达到了则不进行扩容
  2. new 一个2倍容量的新数组
  3. transfer方法将数组元素从旧数组中转移
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];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer方法

双重循环移动数组元素，for循环遍历数组，while循环遍历链表。以头插法将元素插入到新的数组中。

转移同样采用了indexFor计算数组的下标，在没有rehash的情况下，新的下标只会出现在原来的下标或者i+oldTable.length的位置

由于采用了头插法移动数组元素，新数组中的链表与原数组中的链表将会呈倒序

![image-20220106211345431](/Users/doubly/Library/Application Support/typora-user-images/image-20220106211345431.png)

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;
        }
    }
}
createEntry方法

使用头插法，将元素插入到数组下标为bucketIndex的链表中

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

多线程下链表成环问题

两个线程同时进行扩容，并且都已经进入了transfer方法，都执行道了图中的代码位置。

image-20220106213412277

  1. 准备执行的旧数组

    image-20220106220126268

  2. 没有卡住的线程执行完代码

    image-20220106220243877

  3. 卡住的线程从next = e.next后开始执行第一次循环

    image-20220106222231788

  4. 执行完第二次循环

image-20220106222356633

  1. 执行第三次循环

image-20220106222602950

  1. 假设有get方法来获取值，那么进行key比较的时候就会进入无限循环

get方法

判断key为空则取数组第0个位置上的entry

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

首先算出key的hash值

根据hash算出下标

在数组对应下标的链表中遍历查找，如果key相等则返回entry，没找到则返回null

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

ConcurrentHashMap

HashMap是线程不安全的，那么解决的方法有

  1. HashTable

HashTable直接在get,put方法上加了synchronized，使得线程安全。

而当不同线程同时存储到数组的不同索引上时，此时他们并不冲突，用HashTable效率就会比较低

  1. ConcurrentHashMap

采用了分段锁的设计，效率高

Concurrent HashMap中，由entry的table变成了segement的数组，然后segement中存储的才是entry的数组

构造函数

//使用默认初始容量 (16)、负载因子 (0.75) 和 concurrencyLevel (16) 创建一个新的空映射。
public ConcurrentHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        //利用循环得到大于等于并发级别的2的幂次方的数
  			while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift;
        this.segmentMask = ssize - 1;
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
  			//生成一个segment对象放在segment[0]的位置上，当调用put方法时，如果计算出的下标上segment对象为null，则会以第0个位置上的segment对象为模板创建一个新的对象
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  			//UNSAFE操作
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

concurrencyLevel

并发级别，默认是16，其实指的就是segement的个数。

Segement 下的entry数组的长度是计算出来的，为concurrencyLevel/initialCapacity，然后取大于该值的最小2的幂次方，就是entry的数组大小

注意：DEFAULT_INITIAL_CAPACITY的容量指的还是entry的个数，不是segement的个数

UNSAFE操作

public class UnsafeTest {

    private static sun.misc.Unsafe UNSAFE;
    private static long I_OFFSET;

    static {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            UNSAFE = (Unsafe) field.get(null);

            I_OFFSET = UNSAFE.objectFieldOffset(Person.class.getDeclaredField("i"));
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        final Person person = new Person();
        new Thread(new Runnable(){
            @Override
            public void run() {
                while (true) {
                    //UNSAFE操作中的CAS操作，原子性，比较并交换
                    boolean b = UNSAFE.compareAndSwapInt(person, I_OFFSET, person.i, person.i + 1);
                    if(b) System.out.println(UNSAFE.getIntVolatile(person, I_OFFSET));
                    //person.i++;
                    //System.out.println(person.i);
                    try {
                        TimeUnit.MILLISECONDS.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

        new Thread(new Runnable(){
            @Override
            public void run() {
                while (true) {
                    boolean b = UNSAFE.compareAndSwapInt(person, I_OFFSET, person.i, person.i + 1);
                    if(b) System.out.println(UNSAFE.getIntVolatile(person, I_OFFSET));
                    //person.i++;
                    //System.out.println(person.i);
                    try {
                        TimeUnit.MILLISECONDS.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }
}

class Person{
    int i = 0;
}

在ConcurrentHashMap中用到了UNSAFE的CAS操作，比如

两个线程同时进行一个put操作，且都在同一个位置，且segment为null。同时put就会存在并发安全问题，segment被覆盖。而采用CAS则可以不用加锁就保证线程安全。

put方法

  1. 计算key的hash值
  2. 通过hash值获取在segment数组中的下标hashCode & segment[].length -1
  3. 如果segment为null，则通过CAS操作创建一个segment
  4. 调用segment的put方法
  5. 获取segment中entry数组的下标hashCode & hashEntry[].length -1
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    //获取hash值
    int hash = hash(key);
    //获取在segment数组中的下标 
    int j = (hash >>> segmentShift) & segmentMask;
    //取segments数组中第j个位置的值
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

JDK 1.8中