#### 构造函数和相关参数 ``` /** * 默认初始容量 16，必须是2的幂次方 * 为什么必须是2的幂次方 * */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 被所有实例共享的，当table还没有膨胀的时候 */ static final Entry<?,?>[] EMPTY_TABLE = {}; transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; transient int size; int threshold; final float loadFactor; transient int modCount; static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; transient int hashSeed = 0; /** * 设置初始化容量和负载因子的构造函数 */ 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(); } /** * 设置初始化容量的构造函数 * 默认负载因子是0.75 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 默认构造函数 * 默认长度是16，默认负载因子是0.75 */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } ``` #### 1、JDK1.7 HashMap put()方法 ``` public V put(K key, V value) { // 空的话就进行初始化 if (table == EMPTY_TABLE) { // put元素时才进行初始化，创建哈希表 inflateTable(threshold); } // 空 直接put if (key == null) return putForNullKey(value); // 计算hashcode，进行异或运算，返回一个哈希值 int hash = hash(key); // 获取数组的下标（哈希桶） int i = indexFor(hash, table.length); // 遍历链表 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 桶里有重复的key的情况 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 桶里无重复的key，新增一个 addEntry(hash, key, value, i); return null; } /** * 检索对象哈希代码，并对结果哈希应用一个补充哈希函数，该函数可抵御质量较差的哈希函 * 数。这一点很关键，因为HashMap使用两个长度哈希表的幂，会遇到在低位没有差异的哈的 * 冲突。注意：空键总是映射到哈希0，因此索引为0。 */ final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } // 异或运算，提高hashcode的散列性，使其分布更加均匀 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); } /** * 算出数组的下标 */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; // hashcode的低位 // 数组的长度减1再与哈希值进行按位与 // 是2的幂次方的话，减1后的每一位都是1 /** 这里就解释了length为什么初始化时必须是2的幂次方数，为了方便计算数组的下标 * 只有它的长度是2的n次方的时候，我对它进行减1操作时才能拿到全部是1的值，再进行按位与时才能快速的得出数组的下标，并且它的分布是均匀的。 */ return h & (length-1); } /** * 为table开辟空间 */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize // 必须是2的幂次方 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化一个数组 table = new Entry[capacity]; 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; // (number - 1) << 1 // 先将number变大，减-1是由于特殊情况，如果是8、16、2的幂次方的情况 // 找到一个小于等于这个数的2的最小次方数 // Integer.highestOneBit((number - 1) << 1) } ``` put()过程： 1. 如果哈希表还未创建，那么创建哈希表 2. 如果键为null，那么调用putForNullKey插入键为null的值 3. 如果键不为null，计算hash值并得到桶中的索引数，然后遍历桶中链表，一旦找到匹配的，那么替换旧值 4. 如果桶中链表为null或链表不为null但是没有找到匹配的，那么调用addEntry方法插入新节点  扩容的逻辑： 1. 如果长度大于扩容的阈值，且要插入的哈希桶不为空的情况下进行扩容 这里是两个条件 (size >= threshold) && (null != table[bucketIndex])，有时我们往往忽视第2个条件，(null != table[bucketIndex])，如果要插入的哈希桶为空的情况下就不会进行扩容 2. 扩容后的容量是扩容前的2倍 3. 新建一个数组，然后调用transfer()方法将元素复制进去。 ``` void addEntry(int hash, K key, V value, int bucketIndex) { // 扩容逻辑 // （1）hashmap存的元素大于阈值 // （2）table[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); } 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++; } /** * 扩容 */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // new一个新的table，新的容量是之前的两倍 Entry[] newTable = new Entry[newCapacity]; // 问题根源，会形成循环链表，造成死锁 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * 判断是否需要rehash */ final boolean initHashSeedAsNeeded(int capacity) { /* * hashSeed 哈希种子 默认为0 * currentAltHashing 大部分情况下是 false */ boolean currentAltHashing = hashSeed != 0; /* * capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD * capacity容量大于Integer的最大值 */ boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean switching = currentAltHashing ^ useAltHashing; if (switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; } return switching; } void transfer(Entry[] newTable, boolean rehash) { // 获取新数组的大小 int newCapacity = newTable.length; // table 是扩容之前的table for (Entry<K,V> e : table) { // 遍历链表 while(null != e) { // 多线程扩容的情况会形成环形链表 Entry<K,V> next = e.next; // 是否进行rehash if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 根据新的容量计算出新的数组下标 int i = indexFor(e.hash, newCapacity); // 相当于重新进行一次put操作 e.next = newTable[i]; newTable[i] = e; e = next; } } } ``` Integer的highestOneBit()方法 ``` public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); } ``` get()方法: 1. 如果键为空，直接调用getForNullKey()方法，否则调用getEntry()方法 2. 计算在哈希桶的下标，然后遍历链表，如果没有找到则返回null ``` public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } 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; } ``` >关于在多线程环境下会造成死循环，*可以看一下下面的文章* >疫苗：JAVA HASHMAP的死循环<br/> >文章链接：https://coolshell.cn/articles/9606.html