JDK 1.7 HashMap,ConcurrentHashMap源码解析

骑猪看日落 2023-06-15 12:28 136阅读 0赞

## HashMap ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70][]

### 静态常量 ###

/**
    * The default initial capacity - MUST be a power of two. 
    * 初始容量是2的幂:16
    */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
    * The maximum capacity, used if a higher value is implicitly specified
    * by either of the constructors with arguments.
    * MUST be a power of two <= 1<<30.
    * 最大容量
    */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
    * The load factor used when none specified in constructor.
    * 加载因子，0.75
    * 初始大小=16，当数组大小达到16*0.75=12时，扩容
    * 扩容目的：减短链表
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

### put ###

先走一遍整体流程，再详细看方法

public V put(K key, V value) {
        // 初始化数组,threshold = 16
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        
        // HashMap的key可以为null，将null放到index=0的位置
        if (key == null)
            return putForNullKey(value);
        
        // 为什么不直接key.hashCode()，而是要进行其他操作? 让数据更加分散
        int hash = hash(key);
        
        // 数组下标，初始时，一定在 0~15
        int i = indexFor(hash, table.length);
        
        // 遍历链表，如果键重复，使用新值覆盖旧值，并且返回旧值
        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;
            }
        }
    
        // 用于快速失败，HashMap的线程是不安全的，所以在其他线程操作时改变了HashMap的结构，就需要抛出异常
        modCount++;
        
        // 键未重复，创建链表，加到数组中；扩容
        addEntry(hash, key, value, i);
        
        return null;
    }

**1. inflateTable**

/**
    * Inflates the table.
    */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
    
        // 修改临界值，初始时，threshold = 12
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        
        // 初始化数组，size=16
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

**2. putForNullKey**

/**
    * Offloaded version of put for null keys
    */
    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++;
        
        // 将null的键放入哈希表0索引的位置
        addEntry(0, null, value, 0);
        return null;
    }

**3. addEntry**

void addEntry(int hash, K key, V value, int bucketIndex) {
        // size >= 12并且该位置已经有链表，扩容。多线程情况下，扩容死循环问题？
        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);
    }

**4. createEntry**

void createEntry(int hash, K key, V value, int bucketIndex) {
        // 当前数组下标的节点对象
        Entry<K,V> e = table[bucketIndex];
        // 放入链表头
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        // key-value size++
        size++;
    }

**5. indexFor**

/**
    * Returns index for hash code h.
    */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        // 初始length=16，length-1=15，与任何h&，其值肯定在 0~15
        return h & (length-1);
    }

### get ###

get比较简单

public V get(Object key) {
        // 获取key为null的值，index=0的地方
        if (key == null)
            return getForNullKey();
        
        Entry<K,V> entry = getEntry(key);
    
        return null == entry ? null : entry.getValue();
    }

**1. getForNullKey**

private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

**2. getEntry**

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
    
        int hash = (key == null) ? 0 : hash(key);
        
        // 遍历链表，拿数据
        // indexFor(hash, table.length)，获取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 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 1][]

静态常量就不说了，先来看看 **HashEntry** 和 **Segment** 对象的定义

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
    
        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        ...
    }
    
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
        static final int MAX_SCAN_RETRIES =
                Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
    
        transient volatile HashEntry<K,V>[] table;
        transient int count;
        transient int modCount;
        transient int threshold;
        final float loadFactor;
    
        Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
            this.loadFactor = lf;
            this.threshold = threshold;
            this.table = tab;
        }
        
        ...
    }

操作和HashMap可以类比，就不详说了，具体说说两个地方。

**1. 初始化ConcurrentHashMap对象**

// 初始化segment数组和segment[0]，其他的HashEntry数组不会立即初始化，用到的时候，再初始化
    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;

**2. put操作的线程安全实现 ensureSegment**

// while + CAS 乐观锁的实现，并发安全
    while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
            break;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191122154407837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191122154843622.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5,size_16,color_FFFFFF,t_70