vlambda博客
学习文章列表

/** * The default initial capacity - MUST be a power of two. * 默认初始容量大小 */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * MUST be a power of two <= 1<<30. * hashMap最大容量，可装元素个数 */static final int MAXIMUM_CAPACITY = 1 << 30;/** * The load factor used when none specified in constructor. * 加载因子，如容量为16，默认阈值即为16*0.75=12,元素个数超过(包含)12且，扩容 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/** * 空数组，默认数组为空，初始化后才才有内存地址，第一次put元素时判断，延迟初始化 */static final Entry<?,?>[] EMPTY_TABLE = {};

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //1.如果原来数组容量等于最大值了，2^30,设置扩容阈值为Integer最大值，不需要再扩容 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //2.创建新数组对象  Entry[] newTable = new Entry[newCapacity]; //3.将旧数组元素转移到新数组中,分析一 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //4.重新引用新数组对象和计算新的阈值 table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}

/** * Transfers all entries from current table to newTable. * 从当前数组中转移所有的节点到新数组中 */void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //遍历旧数组 for (Entry<K,V> e : table) { //1,首先获取数组下标元素 while(null != e) { //2.获取数组该桶位置链表中下一个元素 Entry<K,V> next = e.next; //3.是否需要重新该元素key的hash值 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } //4，重新确定在新数组中下标位置 int i = indexFor(e.hash, newCapacity); //5.头插法：插入新链表该桶位置，若有元素，就形成链表，每次新加入的节点都插在第一位，就数组下标位置 e.next = newTable[i]; newTable[i] = e; //6.继续获取链表下一个元素  e = next; } }}

//传入容量值返回是否需要对key重新Hashfinal boolean initHashSeedAsNeeded(int capacity) { //1.hashSeed默认为0,因此currentAltHashing为false boolean currentAltHashing = hashSeed != 0; //2,sun.misc.VM.isBooted()在类加载启动成功后，状态会修改为true // 因此变数在于，capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD，debug发现正常情况ALTERNATIVE_HASHING_THRESHOLD是一个很大的值,使用的是Integer的最大值 boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); //3,两者异或，只有不相同时才为true，即useAltHashing =true时，dubug代码发现useAltHashing =false， boolean switching = currentAltHashing ^ useAltHashing; if (switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; } //正常情况下是返回false，即不需要重新对key哈希 return switching;}

public V put(K key, V value) { //1,若当前数组为空，初始化 if (table == EMPTY_TABLE) { //分析1 inflateTable(threshold); } //2,若put的key为null,在放置在数组下标第一位，索引为0位置，从该源码可知 // hashMap允许 键值对 key=null,但是只能有唯一一个 if (key == null) // 分析2 return putForNullKey(value); //3,计算key的hash，这里与1.8有区别  //分析3  int hash = hash(key); // 4,确定在数组下标位置，与1.8相同 int i = indexFor(hash, table.length); // 5，遍历该数组位置,即该桶处遍历 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))) { // 找到相同的key，则覆盖原value值，返回旧值 V oldValue = e.value; e.value = value; //该方法为空，不用看 e.recordAccess(this); return oldValue; } } //因为hashMap线程不安全，修改操作没有同步锁， //该字段值用于记录修改次数，用于快速失败机制 fail-fast,防止其他线程同时做了修改，抛出并发修改异常 modCount++; // 6,原数组中没有相同的key，以头插法插入新的元素 //分析4 addEntry(hash, key, value, i); return null;}

private void inflateTable(int toSize) { // Find a power of 2 >= toSize //1.该方法非常重要，目的为了得到一个比toSize最接近的2的幂次方的数， // 且该数要>=toSize,这个2的幂次方方便后面各种位运算 // 如：new HashMap(15),指定15大小集合，内部实际 创建数组大小为2^4=16 // 分析见下 int capacity = roundUpToPowerOf2(toSize); //2，确定扩容阈值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //3，初始化数组对象 table = new Entry[capacity]; initHashSeedAsNeeded(capacity);}

private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative";//如果number大于等于最大值 2^30，赋值为最大，主要是防止传参越界，number一定是否非负的  return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; //核心在于Integer.highestOneBit((number - 1) << 1) 此处}

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

 i |= (i >> 1);  0001****| 00001*** ---------- 00011*** #保证左边2位是1

 i |= (i >> 2);  00011***| 0000011* ---------- 0001111* #保证左边4位是1

 i |= (i >> 4);  0001111*| 00000001 ---------- 00011111 #把高位以下所有位变为1了，该数还是只有5位，该计算可将8位下所有的置为1

i - (i >>> 1);#此时 i= 00011111 00011111- 00001111 #无符号右移1位--------- 00010000 #拿到值

private V putForNullKey(V value) { //1.直接table[0] 位置获取，先遍历链表(这里对该数组位置统称为链表，可能没有元素，或者只有一个元素，或者链表)查找是否存在相同的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++; //此时注意添加节点时，第一个0即代表数组下标位置,后面会分析该方法 addEntry(0, null, value, 0); return null;}

final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } //k的hashCode值 与hashSeed 异或  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);}

void addEntry(int hash, K key, V value, int bucketIndex) { //总元素个数大于等于阈值 且 当前数组下标已存在元素了：扩容 if ((size >= threshold) && (null != table[bucketIndex])) { //1，扩容，上面已分析过代码 resize(2 * table.length); //2,计算新加key的hash值，key为null的hash值为0 hash = (null != key) ? hash(key) : 0; //3，确保计算的数组下标一定在数组有效索引内，见分析5 bucketIndex = indexFor(hash, table.length); } // 4，扩容后再插入新数组中 createEntry(hash, key, value, bucketIndex);}//分析5static int indexFor(int h, int length) { // 与数组长度-1与运算，一定可以确保结果值在数组有效索引内，且均匀分散 return h & (length-1);}// 进一步分析插入节点方法void createEntry(int hash, K key, V value, int bucketIndex) { //1,首先获取新数组索引位置元素 Entry<K,V> e = table[bucketIndex]; //2,头插法插入新节点， Entry构造方法第4个参数e表示指定当前新增节点的next指针指向该节点，形成链表 table[bucketIndex] = new Entry<>(hash, key, value, e); //3,map元素个数+1 size++;}