🔎【Java 源码探索】深入浅出的分析 HashMap（JDK7）

static class Entry<K,V> implements Map.Entry<K,V> {        final K key;        V value;     //存储指向下一个Entry的引用，单链表结构        Entry<K,V> next;    //对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算        int hash;        /**         * Creates new entry.         */        Entry(int h, K k, V v, Entry<K,V> n) {            value = v;            next = n;            key = k;            hash = h;        }

//默认初始化化容量,即16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，即2的30次方static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态static final Entry<?,?>[] EMPTY_TABLE = {};
//空的存储实体transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//实际存储的key-value键值对的个数transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考thresholdint threshold;
//负载因子，代表了table的填充度有多少，默认是0.75final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationExceptiontransient int modCount;
//默认的threshold值static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//计算Hash值时的key种子值transient int hashSeed = 0;

    //通过初始容量和状态因子构造HashMap    public HashMap(int initialCapacity, float loadFactor) {        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;    // init方法在HashMap中没有实际实现，不过在其子类如     // linkedHashMap中就会有对应实现        init();    }
    //通过扩容因子构造HashMap,容量去默认值，即16    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }
    //装载因子取0.75，容量取16，构造HashMap      public HashMap() {         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);    }  
    //通过其他Map来初始化HashMap，   // 容量通过其他Map的size来计算，装载因子取0.75      public HashMap(Map<? extends K, ? extends V> m) {          this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);        inflateTable(threshold);//初始化HashMap底层的数组结构        putAllForCreate(m);//添加m中的元素    }

public V put(K key, V value) {        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)        if (table == EMPTY_TABLE) {            inflateTable(threshold);//分配数组空间        }       //如果key为null，存储位置为table[0]或table[0]的冲突链上        if (key == null)            return putForNullKey(value);        int hash = hash(key);  //对key的hashcode进一步计算，确保散列均匀        int i = indexFor(hash, table.length);//获取在table中的实际位置        for (Entry<K,V> e = table[i]; e != null; e = e.next) {        //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现                return oldValue;            }        }        modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败        addEntry(hash, key, value, i);//新增一个entry        return null;    }

/** * Offloaded version of put for null keys */private V putForNullKey(V value) {    // for循环处理key为空的情况    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;}

private void inflateTable(int toSize) {//capacity一定是2的次幂        int capacity = roundUpToPowerOf2(toSize);//此处为threshold赋值，取capacity*loadFactor和  MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1        threshold = (int) Math.min(capacity * loadFactor,                   MAXIMUM_CAPACITY + 1);    //分配空间        table = new Entry[capacity];    //选择合适的Hash因子        initHashSeedAsNeeded(capacity);}

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;}

final int hash(Object k) {        int h = hashSeed;    //这里针对String优化了Hash函数，是否使用新的Hash函数和Hash    // 因子有关          if (0 != h && k instanceof String) {            return sun.misc.Hashing.stringHash32((String) k);        }        h ^= k.hashCode();        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }

    //返回数组下标    static int indexFor(int h, int length) {        return h & (length-1);    }

 void addEntry(int hash, K key, V value, int bucketIndex) {    //当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍        if ((size >= threshold) && (null != table[bucketIndex])) {            resize(2 * table.length);            hash = (null != key) ? hash(key) : 0;      //扩容后重新计算插入的位置下标            bucketIndex = indexFor(hash, table.length);        }        //把元素放入HashMap的桶的对应位置        createEntry(hash, key, value, 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);    //这保证了新插入的元素总是在链表的头    //元素个数+1      size++; }

 //按新的容量扩容Hash表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));    //修改HashMap的底层数组        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;        //如果是重新Hash，则需要重新计算hash值.                if (rehash) {                    e.hash = null == e.key ? 0 : hash(e.key);                }        //定位Hash桶                int i = indexFor(e.hash, newCapacity);        //元素连接到桶中,这里相当于单链表的插入，总是插入在最前面                e.next = newTable[i];        //newTable[i]的值总是最新插入的值                newTable[i] = e;                e = next;//继续下一个元素              }          }      }  

//根据Hash值和Hash表的大小选择合适的Hash桶      static int indexFor(int h, int length) {          return h & (length-1);      }  

    //获取key值为key的元素值      public V get(Object key) {          if (key == null)//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑              return getForNullKey();          Entry<K,V> entry = getEntry(key);//获取实体  
        return null == entry ? null : entry.getValue();//判断是否为空，不为空，则获取对应的值      }  
    //获取key为null的实体      private V getForNullKey() {          if (size == 0) {//如果元素个数为0，则直接返回null              return null;          }          //key为null的元素存储在table的第0个位置          for (Entry<K,V> e = table[0]; e != null; e = e.next) {              if (e.key == null)//判断是否为null                  return e.value;//返回其值          }          return null;    }  

//获取键值为key的元素      final Entry<K,V> getEntry(Object key) {          if (size == 0) {//元素个数为0              return null;//直接返回null          }  
        int hash = (key == null) ? 0 : hash(key);//获取key的Hash值          for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度，定位到Hash桶               e != null;               e = e.next) {//进行遍历              Object k;              if (e.hash == hash &&                  ((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key，合适则返回值                  return e;          }          return null;      }