在Java開發中，我們經常會像如下方式以下創建一個HashMap：
Map<String, String> map = new HashMap<String, String>();一、什么是容量？
在Java中，保存資料有兩種比較簡單的資料結構：陣列和鏈表，HashMap底層就是陣列+鏈表（jdk1.8后底層是陣列+鏈表+紅黑樹）， 在HashMap中，有兩個比較容易混淆的關鍵欄位：size和capacity ，這其中capacity就是Map的容量，而size我們稱之為Map中的元素個數， 簡單打個比方就更容易理解了：HashMap就是一個“桶”，那么容量（capacity）就是這個桶當前最多可以裝多少元素--也就是陣列的長度，而元素個數（size）表示這個桶已經裝了多少元素，Map<String, String> map = new HashMap<String, String>();
map.put("hello", "Java");
map.put("hell", "Java");
map.put("hel", "Java");
map.put("he", "Java");
/*
* 通過反射獲取
*/
Class<?> 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));二、什么是hash？
我們知道，容量就是一個HashMap中”桶”的個數，那么，當我們想要往一個HashMap中put一個元素的時候，需要通過一定的演算法計算出應該把他放到哪個桶中，這個程序就叫做hash，三、hash的實作
hash的具體實作上，由兩個方法int hash(Object k)和int indexFor(int h, int length)（在jdk1.8后沒有這個方法了）來實作，int hash(Object k)：該方法主要是將Object轉換成一個整型數， int indexFor(int h, int length)：該方法主要是將hash()生成的整型數轉換成鏈表陣列中的下標，我們先來看下原始碼：
static int indexFor(int h, int length) {
return h & (length-1);
}(h = k.hashCode()) ^ (h >>> 16)得到hash值
indexFor方法通過h & (length-1)得到下標，其中的兩個引數h表示元素的hash值，length表示HashMap的容量，
i=(n-1)&hash和上面的運算一樣，其中的兩個引數n表示HashMap的容量，hash表示元素的hash值，
那么h & (length-1) 是什么意思呢？
其實就是取模，Java之所以使用位運算(&)來代替取模運算(%)，最主要的考慮就是效率，
位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對記憶體資料（二進制）進行操作，不需要轉成十進制，因此處理速度非常快，那么，為什么可以使用位運算(&)來實作取模運算(%)呢？實作的原理如下：
a%b在當b為2^n時可簡化為a&(b-1)
證明:
1.當b為2^n時,b-1的二進制為011..11(0后面跟n個1).此時a&(b-1)即取a二進制右面n位
2.當b為2^n時,a/b的意義就是a右移n位，而右移的n位的值，就是a%b的值6 % 8 = 6 ，6 & 7 = 6
10 % 8 = 2 ，10 & 7 = 2
17 % 8 = 1 ，17 & 7 = 1在JDK 8中，關于默認容量的定義如上原始碼 ，其故意把16寫成1<<4，就是提醒開發者，這個地方要是2的冪，注釋中的 aka 16 也是jdk1.8中新增的，Also Known As 16 -- 又名16既然我們需要把容量設定為2^n，那么HashMap是如何保證其容量一定可以是2^n的呢？ 要做到這一型別容量，HashMap在指定容量初始化時以及自動擴容時都做了處理，
四、指定容量初始化
以下是《Java開發手冊》中的一段話：int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
···以此類推int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
System.out.println((n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1); 五、自動擴容
指定容量初始化后，往集合中put元素時，元素個數超過閾值后怎么辦呢？這時候就需要擴容了， HashMap有擴容機制，就是當達到擴容條件時會進行擴容，擴容條件就是當HashMap中的元素個數（size）超過閾值（threshold）時就會自動擴容，通過resize方法進行擴容，newCap = oldCap << 1;
newThr = oldThr << 1;HashMap m = new HashMap(15);
Class<?> mapType = m.getClass();
Field threshold = mapType.getDeclaredField("threshold");
threshold.setAccessible(true);
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("容量：" + capacity.invoke(m) + " 閾值：" + threshold.get(m) + " 元素數量：" + m.size());
for (int i = 0; i < 25; i++) {
m.put(i, i);
System.out.println("容量：" + capacity.invoke(m) + " 閾值：" + threshold.get(m) + " 元素數量：" + m.size());
}六、總結
HashMap作為一種資料結構，元素在put的程序中需要進行hash運算，目的是計算出該元素存放在hashMap中的具體位置， hash運算的程序其實就是先對key用hash()方法得到一個hash值，再用hash值對Map的容量進行取模得到下標，而JDK的工程師為了提升取模的效率，使用位運算代替了取模運算，這就要求Map的容量一定得是2的冪， 為了保證任何情況下Map的容量都是2的冪，HashMap在兩個地方都做了限制， 首先是，如果用戶制定了初始容量，那么HashMap會計算出比該數大的第一個2的冪作為初始容量， 另外，在擴容的時候，也是進行成倍的擴容，即16變成32，32變成64，轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/523155.html
標籤：其他
上一篇：python基礎-流程控制