1，儲存方式
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
transient int size;
int threshold; // 負載因子
final float loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
transient int modCount; // 修改次數
public HashMap(int initialCapacity, float loadFactor) {
...
threshold = initialCapacity;
...
}
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
}
1）内部儲存為：HashMapEntry[]，而HashMapEntry為明顯的連結清單特征，是以可以記住，HashMap的儲存方式為數組+連結清單
2）HashMap的儲存單元：(hash,key,value,bucketIndex)共同存儲
2，自增方式
public V put(K key, V value) {
// table為空時，建立table，threshold初始值為4
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 擷取 key的hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// 擷取 hashcode對Length的求餘，Length的值一定是2的次幂
int i = indexFor(hash, table.length);
// 周遊，當key的hashCode和equal相等時，更新資料
for (HashMapEntry<K,V> 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;
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
/**
* {1 - 1}, {2 - 2}, {3 - 4}, {8 - 8}, {9 - 16}
*
* @param number 輸入參數
* @return 傳回值，一定為2的次幂
*/
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
/**
* 等價于 h % length
* @param h hashCode值
* @param length 2的次幂值
* @return 求餘值
*/
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);
}
/**
* 添加資料，解決Hash沖突問題
*
* @param hash key的hash值
* @param key key值
* @param value value值
* @param bucketIndex key的hash值，對容量求出的 bucketIndex
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果達到了最大容量，則擴容；并重新計算bucketIndex和hash值
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴容
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* 擴容
* @param newCapacity 新的容量大小，2的次幂值
*/
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
* 注意是所有(包含數組和連結清單)，而不是頭部；這是為了解決平攤之後，可能餘值不一樣的問題
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
/**
* 如果原先資料為空，則增加一條資料
* 如果原先資料不為空，則“舊資料”成為“新資料”的next
* 該處為連結清單形式
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
這裡的問題很多，面試問的最多的也是這一段，接下來一一回答
1）HashMap的實作原理：利用hashCode值将(hash,key,value, next)共同存儲，并采用數組+連結清單的形勢實作。
hash：擴容時，重新計算bucketIndex使用
key、value：儲存内容
next：上一次儲存的對象
2）如何解決HashCode碰撞：拉鍊法，即：以數組的節點作為連結點，延伸出一個連結清單進行存儲。
具體儲存的方法為：createEntry(...)，每次放入都是作為一個連結清單節點放入
3）大小超過負載因子時：擴容，将原先所有資料從新計算bucketIndex再次安放。
容量：值永遠為2的次幂，為了使得(h & length - 1) == h % length公式成立
負載因子：當 存入的值，大于負載因子*容量 時，将會發生 refash(擴容)；擴容執行了建立數組，并且将原先資料搬移過去，是很耗費性能的事，而hashCode是散列分布的，在容量快滿時，很有可能計算出重複的值。可以分析出，負載因子高時，可能導緻連結清單較長的可能性大，周遊時需要的時間增長；負載因子低時，連結清單長的可能性很小，但數組會較大；是以0.75為折中方案
4）多線程，同時擴充，發生了條件競争：可能出現死循環，是以多線程操作，需要線程安全的保障
5）為什麼HashMap的容量總是2的次幂：計算BucketIndex時，加快運作是速度。使得(h & length - 1) == h % length成立
3，查詢資料
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 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<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;
}
1）先計算出hashCode值，擷取到數組中的連結清單節點；
2）依據連結清單的頭部，依次執行equal方法，找出符合要求的value
4，整體大小
public int size() {
return size;
}
大小，則是通過使用一個全局量記錄。需要擷取時，擷取即可
5，外話
1）和Hashtable對比的影響性能的差別有：(更多的差別，就不列舉)
HashMap線程不安全，hashtable線程安全
HashMap容量為2的次幂，hashtable容量不是，是以hashMap在計算bucketIndex時，效率高很多
2）Map的子類中，還有幾個有意思的集合，可以去研究
IndentityHashMap：采用數組的偶數儲存Key，偶數+1儲存Value
TreeMap：采用維持紅黑樹，進而保障查詢資料的效率
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)