广州金融网站设计,电子商务网站建设和运营,app运营模式,网站开发有很多种吗源码分析jdk1.7下的HashMap我们都知道1.7版本的hashmap的底层是数组加链表构成的#xff0c;那么今天我们就来自己分析一波源码~篇幅有点长#xff0c;废话不多说#xff0c;直接开始分析~「属性声明」//初始化容量 static final int DEFAULT_INITIAL_CAPACITY 1 4;… 源码分析jdk1.7下的HashMap我们都知道1.7版本的hashmap的底层是数组加链表构成的那么今天我们就来自己分析一波源码~篇幅有点长废话不多说直接开始分析~「属性声明」//初始化容量 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;int threshold;「构造方法」//自定义初始化容量和加载因子会进行判断两个值合不合法// The default initial capacity - MUST be a power of two. 容量必须是2的幂次方public HashMap(int initialCapacity, float loadFactor)//自定义初始化容量使用默认的加载因子public HashMap(int initialCapacity) //使用默认的初始化容量和默认的加载因子public 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中该方法为空没有实现在LinkedList才有实现所以这里不做研究 }「put方法」public V put(K key, V value) { //当前table数组为空则去进行初始化大小在这里我们就能够知道在构造方法中为什么要将初始化容量赋值给threshold了根据我的理解其实就是起到一个懒初始化的效果吧就是当你去put第一个值的时候它才去进行初始化数组的大小 if (table EMPTY_TABLE) { inflateTable(threshold); // 跳到1 } if (key null) return putForNullKey(value); int hash hash(key); int i indexFor(hash, table.length); for (Entry 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(threshold) private void inflateTable(int toSize) { // Find a power of 2 toSize 根据注释可以知道是找到一个大于等于toSize的2的幂次方 // 例如toSize5 时则capacity此时就会等于8 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; }我们继续往下点 // 这个函数看上去很是简洁全是位运算那么它就是是在干嘛呢 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); }❝我们举个例子来验证一下它是干嘛的(下面图片左移为右移)❞image-20201205160204696❝不知道大家有没有发现一个规律最后返回的结果跟我们传进去的i有什么关系吗刚刚调用highestOneBit 的roundUpToPowerOf2这个函数官方的注释已经告诉我们是寻找一个大于等于toSize的2的幂次方image-20201205160747608❞那我们回到 highestOneBit 这个函数传进去5返回的是4传进去14返回的是8有了上面的穿插我们应该不难发现该函数的作用恰巧与 roundUpToPowerOf2 的目的相反highestOneBit 它是找出小于等于i的2的幂次方的数即5 - 4, 15- 8。那么我们的疑问来了为什么要有五次右移操作呢而且右移的次数也不一样下面我们一起探究~❝第一次右移了1位第二次右移了2位第三次右移了4位·····到了第五次右移16位一共合起来总共右移了 31位。不知道大家有没有觉得答案正在步步逼近我们int类型在内存中占4个字节一共32位。假设i非常的大整整占满了32位然后我们上面将一个整型的字整整右移了31位这样的效果岂不是能把后31位全部置为了1接下来下面的操作得到的这个数再减去它无符号右移后的数结果不就是 0010 ····(此处省略28个0)。与原来的数 1xxx ····(此处省略28个xx代表0或1)对比不就是找到了小于等于i的2的幂次方吗是不是很奇妙~❞好了那么现在我们要一步步往上返回去了因为我们从刚刚函数一直往底层深究现在要往上面返回了~//此时我们返回到这里highestOneBit是传进去5返回4 //然后该函数是传进去5返回8//很明显是相反的那么它是怎么实现的呢/**假设现在number等于5它最终回去调用这个Integer.highestOneBit((number - 1) 下面我们都用位运算表示 0000 0101 - 0000 0001 0000 0100 此时调用highestOneBit函数传进去的是8,小于等于8的2幂次方的数不就是8吗此时roundUpToPowerOf2该函数不就得到的数不就是大于等于5的2的幂次方的数吗 **/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; }这时候我们只能感慨实现这几个函数的外国佬在当时早已把位运算用得出神入化继续往上返回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开辟了一个大小为capacity的数组了。 table new Entry[capacity]; initHashSeedAsNeeded(capacity); }好了来来回回游荡了这么久我们就要又回到put函数了public V put(K key, V value) { if (table EMPTY_TABLE) { inflateTable(threshold); } if (key null) //key为null时调用下面的方法去将null-value加进去 //这里可以自己复习的时候点进去看因为里面很简单易懂这里节省时间不单独 //跟下面的循环一样的 return putForNullKey(value); //跳到下面解释1 int hash hash(key); int i indexFor(hash, table.length); //跳到下面解释2 for (Entry 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; } }//当put进去的key算出来的位置此时为null时则会执行到这里跳到解释3 modCount; addEntry(hash, key, value, i); return null; } int hash hash(key); //算出key的哈希值 int i indexFor(hash, table.length); //这里讲一下hashmap的每一个key的存储规则我们知道1.7它是用链表数组去实现的那么每次我们put进去一对k-v //它是怎么去存储的呢 这两行就是算出该key具体放在数组中哪个位置它是利用key的哈希值去模上数组的长度 //最后算出来的就是它在数组中存储的下标indexFor的源码在下面 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); //为什么是减1呢因为数组的下标是从0开始的 } 由于hash()函数涉及到哈希种子方面的知识这里就先不做解释了(因为我还没搞懂--!)。 //这里的循环其实很容易懂我们看下面的图就是可以知道 //当put进去的key原来已经存在时则会替换掉原来的value然后返回旧的值 for (Entry 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); //这里没有实现在LinkedHashMap有实现涉及LRU缓存结构return oldValue; } }❝需要注意一点的就是每次put进去的key都是放在链表的头部也就是将往下挤❞image-20201205165507120在这里引用一下不知道谁说的一句话 Dont BBshow me the code 我们写个demo测试一下 public class HashMapTest { public static void main(String[] args) { HashMap hashMap new HashMap(); System.out.println(hashMap.put(1, 10)); System.out.println(hashMap.put(1, 20)); } }运行输出结果很明显第一次put进去值此时hashmap还是空的将1-10put进去后返回oldval为null第二次put 1-20 此时就会覆盖原来的10然后返回oldval为10此时get(1)将为等于20。image-20201205170306350 // hash为hash值 bucketIndex为上面算出来的key要放进去的下标 void addEntry(int hash, K key, V value, int bucketIndex) { // 这里是对hashmap进行扩容下面单独讲 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); } //这个函数就是简单的将key添加进去 void createEntry(int hash, K key, V value, int bucketIndex) { Entry e table[bucketIndex]; table[bucketIndex] new Entry(hash, key, value, e); size; //标记table数组中已存储key-val的个数为了判断是否需要扩容 } Entry(int h, K k, V v, Entry n) { value v; next n; key k; hash h; }上面基本都把该肝的都肝完了现在我们来探究一波扩容的问题 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); }好了在前面出现的 threshold 这个属性值现在又出现了我们知道size的作用是表示现在我们hashmap中所有的k-v键值对的个数此时如果 超过了 threshold并且当前要存储的位置的下标中已经有值了(这两个条件缺一不可) 则会进行扩容。// threshold这个值是怎么算出来的我们可以看这个式子// capacity * loadFactor 初始化容量*加载因子// 已默认的容量和加载因子为例子 static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 static final float DEFAULT_LOAD_FACTOR 0.75f; static final int MAXIMUM_CAPACITY 1 30;// 可以算出 capacity * loadFactor 16*0.75 12// 取小的值赋值给 threshold最大容量非常的大所以此时默认情况 threshold 12threshold (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);也就是说当哈希表中的元素大于等于12时此时想要put进去一个键值对我们通过上面的解释知道put进去值的过程首先需要通过hash(key)算出hash值然后再模上数组的长度这样就算出了下标index假设此时 table[index]! null,则会发生扩容不然的话则不会发生扩容。(size threshold) (null ! table[bucketIndex]) //这两个条件缺一不可下面进行代码测试「Test1」public class HashMapTest { public static void main(String[] args) throws Exception { HashMap map new HashMap();//我们用循环put进去15个k-vfor (int i 1; i 15; i){ map.put(testi,test); }//下面通过反射这个骚操作取一下里面的值进行验证//不会反射的可以去OB一下我很久之前发的文章 Class extends HashMap mapType map.getClass(); Method capacity mapType.getDeclaredMethod(capacity); capacity.setAccessible(true); System.out.println(capacity : capacity.invoke(map)); Field size mapType.getDeclaredField(size); size.setAccessible(true); System.out.println(size : size.get(map)); Field threshold mapType.getDeclaredField(threshold); threshold.setAccessible(true); System.out.println(threshold : threshold.get(map)); Field loadFactor mapType.getDeclaredField(loadFactor); loadFactor.setAccessible(true); System.out.println(loadFactor : loadFactor.get(map)); }}大家猜一下结果会是怎么样的呢先不要着急往下看理解一下代码然后再心中或者纸上写下你的猜测❝我猜测 capacity16 size15 threshold12 loadFactor0.75❞我们来看看结果image-20201205192442480你猜对了嘛其实结果还是很容易理解的全是默认的值因为此时根本就没有满足扩容的条件再次重复下扩容的条件 sizethreshold table[index]!null接下来我们进行测试「Test2」//为了节省篇幅我就仅仅贴出与上面不同的代码//这次我还是put进去15个k-v唯一与上个测试不一样的是put进去的k-vfor (int i 1; i 15; i){ map.put(i,i*10);}我们在来猜一下输出的结果❝结果跟上面的一样capacity16 size15 threshold12 loadFactor0.75❞输出的结果肯定和上面的不一样啦测试才有意义不然的话就没有意义了。运行输出我们可以发现image-20201205192907999好家伙团灭居然和我们预想的值不一样那究竟是怎么回事呢我们再回过头来分析一下扩容的条件 sizethresholdtable[index]!null因为很明显它进行了扩容说明满足了上面的两个条件。❝那么现在我们的问题来了Test1和Test2的区别在哪里我们可以看到同样put进去15个值1512 很明显满足第一个条件那么为什么Test1中不满足第二个条件然后Test2就满足呢下面让我画个图解答这些疑惑~❞image-20201205194545524在这一引入一个名词哈希碰撞哈希碰撞叫什么呢正如Test2一样在put进去第15个key-val的时候在经过哈希计算下标值的时候两个不同的hash值算出来了相同的下标就称为哈希碰撞。「小结」 默认的容量为16加载因子为0.75阈值即threshold12。那么哈希表最多存储多少个值后才会进行扩容呢最多可以存11151 27个怎么算出来的呢在极端情况下在第一个位置可以put进去11个k-v此时小于阈值12不会发生扩容然后接下来在剩余的15个位置中put进去k-v此时size大于阈值但是没有发生哈希碰撞不会扩容接下来再put进去一个k-v此时必定会发生哈希碰撞所以就发生了扩容所以才有了 11151。image-20201205200007191我们知道了在什么情况下会发生扩容那么接下来我们就来看一下是怎么个扩容法//调用resize函数//传进去两倍的oldtable.lengthresize(2 * table.length);hash (null ! key) ? hash(key) : 0;bucketIndex indexFor(hash, table.length);void resize(int newCapacity) { Entry[] oldTable table; //old数组容量如果等于最大容量 130 这么大直接将阈值设置为一样的大小然后返回。 int oldCapacity oldTable.length; if (oldCapacity MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return; } //新建一个数组数组的长度为原来的两倍上面传进来的参数 Entry[] newTable new Entry[newCapacity]; //调用transfer函数 initHashSeedAsNeeded函数为初始化哈希种子的值HashSeed transfer(newTable, initHashSeedAsNeeded(newCapacity)); table newTable; //算出新的阈值 threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);}void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (Entry e : table) { //对应图中的1while(null ! e) { Entry next e.next; //对应了图中的2if (rehash) { e.hash null e.key ? 0 : hash(e.key); }int i indexFor(e.hash, newCapacity); e.next newTable[i]; //对应图中的3 newTable[i] e; //对应4 e next; //对应5 } } }下面画图理解那个没有底色的圆圈代表null为了画图效果而把它加上image-20201205203907879image-20201205204350912 因为还不懂得怎么画动态图就用两个静态图描述了这个动态的过程如何往复最后变成的样子为image-20201205204950130我们可以发现扩容后链表发生了反转。还有一点需要注意的是每个k-v放在新数组中还是原来的下标吗要是一样的话岂不是没有扩容的意义所以下标还是会有所不同的情况的这行代码就是算出新的下标int i indexFor(e.hash, newCapacity);//这里做个假设原来的hash值为1717%4 1 17%8 1此时算出来的下标都是1//假设hash值为21 21%41 21%85 14此时可以发现下标出现了不一样//因为每次扩容都是将原来的容量*2所以我们不难发现key放在新数组的位置要么就不变要么就是原来下标原来的容量到这里整个过程就已经讲完了。要是你从头看到这里那么我为你的坚持点个赞肝了一天终于把jdk1.7的hashmap的源码分析透了。当你面试的时候面试官问起你就可以吊打面试官问的所有问题了但是hashmap还不止于此因为在jdk1.8版本中它将引用红黑树所以jdk1.8版本的hashmap则由 链表数组红黑树 构成接下来我也会进行源码分析一波研究透彻然后继续肝出来。在看源码的过程中也很艰难但是坚持下来的收获远远是你意想不到的。「最后以上源码分析如有错误恳请指正。」
