共计 23450 个字符，预计需要花费 59 分钟才能阅读完成。
筆記對原始碼解讀的理解以及面試經常問到的問題。
HashMap 的資料結構
資料結構中有陣列和連結串列來實現對資料的儲存，但這兩者基本上是兩個極端。
陣列
陣列儲存區間是連續的，佔用記憶體嚴重，故空間複雜的很大。但陣列的二分查詢時間複雜度小，為 O(1)；陣列的特點是：定址容易，插入和刪除困難；
連結串列
連結串列儲存區間離散，佔用記憶體比較寬鬆，故空間複雜度很小，但時間複雜度很大，達 O(N)。連結串列的特點是：定址困難，插入和刪除容易。
雜湊表
那麼能不能綜合兩者的特性，做出一種定址容易，插入刪除也容易的資料結構？答案是肯定的。雜湊表（(Hash table）既滿足了資料的查詢方便，同時不佔用太多的內容空間，使用也十分方便。
雜湊表有多種不同的實現方法，接下來解釋的是最常用的一種方法—— 拉鍊法，可以理解為“連結串列的陣列”，如圖：
從上圖可以理解為 Hashmap 中存放數據的 Entry 透過 % 運算得到最後放入陣列的格子中，比如 hash 為 16%16 得 0 則直接放到 [0] 中，不過這樣的計算效率太低，後面會接著說原始碼上針對這部分做了哪些改進，接著是每個 Entry 中都帶著 next 節點指向下個 Entry 形成單向連結串列。
原始碼分析
package java.util;
import java.io.*;
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* 默认初始容量，默认为 2 的 4 次方 = 16，2 的 n 次方是为了加快 hash 计算速度，；；减少 hash 冲突，，，h & (length-1)，，1111111
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，默认为 2 的 30 次方，*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子，默认为 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当数组表还没扩容的时候，一个共享的空表对象
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 数组表，大小可以改变，且大小必须为 2 的幂
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* 当前 Map 中 key-value 映射的个数
*/
transient int size;
/**
* 下次扩容阈值，当 size > capacity * load factor 时，开始扩容
*/
int threshold;
/**
* 负载因子
*/
final float loadFactor;
/**
* Hash 表结构性修改次数，用于实现迭代器快速失败行为
*/
transient int modCount;
/**
* 容量阈值，默认大小为 Integer.MAX_VALUE
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 静态内部类 Holder，存放一些只能在虚拟机启动后才能初始化的值
*/
private static class Holder {
/**
* 容量阈值，初始化 hashSeed 的时候会用到该值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
// 获取系统变量 jdk.map.althashing.threshold
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold"));
int threshold;
try {threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// jdk.map.althashing.threshold 系统变量默认为 -1，如果为 -1，则将阈值设为 Integer.MAX_VALUE
if (threshold == -1) {threshold = Integer.MAX_VALUE;}
// 阈值需要为正数
if (threshold < 0) {throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {throw new Error("Illegal value for'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
/**
* 计算 hash 值的时候需要用到
*/
transient int hashSeed = 0;
/**
* 生成一个空的 HashMap, 并指定其容量大小和负载因子
*
*/
public HashMap(int initialCapacity, float loadFactor) {
// 保证初始容量大于等于 0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" +
initialCapacity);
// 保证初始容量不大于最大容量 MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactor 小于 0 或为无效数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" +
loadFactor);
// 负载因子
this.loadFactor = loadFactor;
// 下次扩容大小
threshold = initialCapacity;
init();}
/**
* 生成一个空的 HashMap, 并指定其容量大小，负载因子使用默认的 0.75
*
*/
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 生成一个空的 HashMap, 容量大小使用默认值 16，负载因子使用默认值 0.75
*/
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 根据指定的 map 生成一个新的 HashMap, 负载因子使用默认值，初始容量大小为 Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
*/
public HashMap(Map<? extends K, ? extends V> m) {this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
// 返回 >=number 的最小 2 的 n 次方值，如 number=5，则返回 8
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;
}
/**
* 对 table 扩容
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 找一个值（2 的 n 次方，且 >=toSize）int capacity = roundUpToPowerOf2(toSize);
// 下次扩容阈值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// internal utilities
void init() {}
/**
* 初始化 hashSeed
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
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;
}
/**
* 生成 hash 值
*/
final int hash(Object k) {
int h = hashSeed;
// 如果 key 是字符串，调用 un.misc.Hashing.stringHash32 生成 hash 值
//Oracle 表示能生成更好的 hash 分布，不过这在 jdk8 中已删除
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);
}
/**
* 返回 hash 值的索引，采用除模取余法，h & (length-1)操作 等价于 hash % length 操作，但 & 操作性能更优
*/
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);
}
/**
* 返回 key-value 映射个数
*/
public int size() {return size;}
/**
* 判断 map 是否为空
*/
public boolean isEmpty() {return size == 0;}
/**
* 返回指定 key 对应的 value
*/
public V get(Object key) {
//key 为 null 情况
if (key == null)
return getForNullKey();
// 根据 key 查找节点
Entry<K,V> entry = getEntry(key);
// 返回 key 对应的值
return null == entry ? null : entry.getValue();}
/**
* 查找 key 为 null 的 value，注意如果 key 为 null，则其 hash 值为 0，默认是放在 table[0]里的
*/
private V getForNullKey() {if (size == 0) {return null;}
// 在 table[0]的链表上查找 key 为 null 的键值对，因为 null 默认是存在 table[0]的桶里
for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null)
return e.value;
}
return null;
}
/**
* 判断是否包含指定的 key
*/
public boolean containsKey(Object key) {return getEntry(key) != null;
}
/**
* 根据 key 查找键值对，找不到返回 null
*/
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}
// 如果 key 为 null，hash 值为 0，否则调用 hash 方法，对 key 生成 hash 值
int hash = (key == null) ? 0 : hash(key);
// 调用 indexFor 方法生成 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;
}
/**
* 向 map 存入一个键值对，如果 key 已存在，则覆盖
*/
public V put(K key, V value) {
// 数组为空，对数组扩容
if (table == EMPTY_TABLE) {inflateTable(threshold);
}
// 对 key 为 null 的键值对调用 putForNullKey 处理
if (key == null)
return putForNullKey(value);
// 生成 hash 值
int hash = hash(key);
// 生成 hash 值索引
int i = indexFor(hash, table.length);
// 查找是否有 key“相等”的键值对，有的话覆盖
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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 操作次数加一，用于迭代器快速失败行为
modCount++;
// 在指定 hash 值索引处的链表上增加该键值对
addEntry(hash, key, value, i);
return null;
}
/**
* 存放 key 为 null 的键值对，存放在索引为 0 的链表上，已存在的话，替换
*/
private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 已存在 key 为 null，则替换
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 操作次数加一，用于迭代器快速失败行为
modCount++;
// 在指定 hash 值索引处的链表上增加该键值对
addEntry(0, null, value, 0);
return null;
}
/**
* 添加键值对
*/
private void putForCreate(K key, V value) {
// 生成 hash 值
int hash = null == key ? 0 : hash(key);
// 生成 hash 值索引，int i = indexFor(hash, table.length);
/**
* key“相等”，则替换
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
// 在指定索引处的链表上创建该键值对
createEntry(hash, key, value, i);
}
// 将制定 map 的键值对添加到 map 中
private void putAllForCreate(Map<? extends K, ? extends V> m) {for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
/**
* 对数组扩容
*/
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个指定大小的数组
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//table 索引替换成新数组
table = newTable;
// 重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 拷贝旧的键值对到新的哈希表中
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历旧的数组
for (Entry<K,V> e : table) {while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
}
// 根据新的数组长度，重新计算索引，int i = indexFor(e.hash, newCapacity);
// 插入到链表表头
e.next = newTable[i];
// 将 e 放到索引为 i 处
newTable[i] = e;
// 将 e 设置成下个节点
e = next;
}
}
}
/**
* 将制定 map 的键值对 put 到本 map，key“相等”的直接覆盖
*/
public void putAll(Map<? extends K, ? extends V> m) {int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
// 空 map，扩容
if (table == EMPTY_TABLE) {inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
/*
* 判断是否需要扩容
*/
if (numKeysToBeAdded > threshold) {int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
// 依次遍历键值对，并 put
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
/**
* 移除指定 key 的键值对
*/
public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 移除指定 key 的键值对
*/
final Entry<K,V> removeEntryForKey(Object key) {if (size == 0) {return null;}
// 计算 hash 值及索引
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 头节点为 table[i]的单链表上执行删除节点操作
while (e != null) {
Entry<K,V> next = e.next;
Object k;
// 找到要删除的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 删除指定键值对对象(Entry 对象)
*/
final Entry<K,V> removeMapping(Object o) {if (size == 0 || !(o instanceof Map.Entry))
return null;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
// 得到数组索引
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 开始遍历该单链表
while (e != null) {
Entry<K,V> next = e.next;
// 找到节点
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 清空 map，将 table 数组所有元素设为 null
*/
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
/**
* 判断是否含有指定 value 的键值对
*/
public boolean containsValue(Object value) {if (value == null)
return containsNullValue();
Entry[] tab = table;
// 遍历 table 数组
for (int i = 0; i < tab.length ; i++)
// 遍历每条单链表
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
/**
* 判断是否含有 value 为 null 的键值对
*/
private boolean containsNullValue() {Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
/**
* 浅拷贝，键值对不复制
*/
public Object clone() {
HashMap<K,V> result = null;
try {result = (HashMap<K,V>)super.clone();} catch (CloneNotSupportedException e) {// assert false;}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min((int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
// 内部类，节点对象，每个节点包含下个节点的引用
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* 创建节点
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// 获取节点的 key
public final K getKey() {return key;}
// 获取节点的 value
public final V getValue() {return value;}
// 设置新 value，并返回旧的 value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断 key 和 value 是否相同, 两个都“相等”，返回 true
public final boolean equals(Object o) {if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {return getKey() + "=" + getValue();}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) { }
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {}}
/**
* 添加新节点，如有必要，执行扩容操作
*/
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);
}
/**
* 插入单链表表头
*/
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++;
}
//hashmap 迭代器
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // 下个键值对索引
int expectedModCount; // 用于判断快速失败行为
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {return next != null;}
final Entry<K,V> nextEntry() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
//ValueIterator 迭代器
private final class ValueIterator extends HashIterator<V> {public V next() {return nextEntry().value;
}
}
//KeyIterator 迭代器
private final class KeyIterator extends HashIterator<K> {public K next() {return nextEntry().getKey();}
}
////KeyIterator 迭代器
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {public Map.Entry<K,V> next() {return nextEntry();
}
}
// 返回迭代器方法
Iterator<K> newKeyIterator() {return new KeyIterator();
}
Iterator<V> newValueIterator() {return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {return new EntryIterator();
}
// Views
private transient Set<Map.Entry<K,V>> entrySet = null;
/**
* 返回一个 set 集合，包含 key
*/
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {public Iterator<K> iterator() {return newKeyIterator();
}
public int size() {return size;}
public boolean contains(Object o) {return containsKey(o);
}
public boolean remove(Object o) {return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {HashMap.this.clear();
}
}
/**
* 返回一个 value 集合，包含 value
*/
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection<V> {public Iterator<V> iterator() {return newValueIterator();
}
public int size() {return size;}
public boolean contains(Object o) {return containsValue(o);
}
public void clear() {HashMap.this.clear();
}
}
/**
* 返回一个键值对集合
*/
public Set<Map.Entry<K,V>> entrySet() {return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {public Iterator<Map.Entry<K,V>> iterator() {return newEntryIterator();
}
public boolean contains(Object o) {if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {return removeMapping(o) != null;
}
public int size() {return size;}
public void clear() {HashMap.this.clear();
}
}
/**
* map 序列化, 可实现深拷贝
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
if (table==EMPTY_TABLE) {s.writeInt(roundUpToPowerOf2(threshold));
} else {s.writeInt(table.length);
}
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {for(Map.Entry<K,V> e : entrySet0()) {s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
/**
* 反序列化，读取字节码转为对象
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor:" +
loadFactor);
}
// set other fields that need values
table = (Entry<K,V>[]) EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count:" +
mappings);
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {inflateTable(capacity);
} else {threshold = capacity;}
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// These methods are used when serializing HashSets
int capacity() { return table.length;}
float loadFactor() { return loadFactor;}
}
}上述轉自: HashMap 源码分析
探討 Hashmap 存取
既然是線性陣列，為什麼能隨機存取？這裡 HashMap 用了一個小演算法，大致是這樣實現：
// 存储时:
int hash = key.hashCode(); // 这个 hashCode 方法这里不详述, 只要理解每个 key 的 hash 是一个固定的 int 值
int index = hash % Entry[].length;
Entry[index] = value;
// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];put
疑問：如果兩個 key 通過 hash%Entry[].length 得到的 index 相同，會不會有覆蓋的危險？
這裡 HashMap 裡面用到鏈式資料結構的一個概念。上面我們提到過 Entry 類裡面有一個 next 屬性，作用是指向下一個 Entry。打個比方，第一個鍵值對 A 進來，通過計算其 key 的 hash 得到的 index=0，記做:Entry[0] = A。一會後又進來一個鍵值對 B，通過計算其 index 也等於 0，現在怎麼辦？HashMap 會這樣做:B.next = A,Entry[0] = B, 如果又進來 C，index 也等於 0, 那麼 C.next = B,Entry[0] = C；這樣我們發現 index= 0 的地方其實存取了 A,B,C 三個鍵值對, 他們通過 next 這個屬性連結在一起。所以疑問不用擔心。也就是說陣列中儲存的是最後插入的元素。到這裡為止，HashMap 的大致實現，我們應該已經清楚了。
public V put(K key, V value) {if (key == null)
return putForNullKey(value); //null 总是放在数组的第一个链表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// 遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果 key 在链表中已存在，则替换为新 value
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;
}
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 参数 e, 是 Entry.next
// 如果 size 超过 threshold，则扩充 table 大小。再散列
if (size++ >= threshold)
resize(2 * table.length);
}當然 HashMap 裡面也包含一些優化方面的實現，這裡也說一下。比如：Entry[]的長度一定後，隨著 map 裡面資料的越來越長，這樣同一個 index 的鏈就會很長，會不會影響效能？HashMap 裡面設定一個因子，隨著 map 的 size 越來越大，Entry[]會以一定的規則加長長度。
get
public V get(Object key) {if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
// 先定位到数组元素，再遍历该元素处的链表
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.equals(k)))
return e.value;
}
return null;
}null key 的存取
null key 總是存放在 Entry[]陣列的第一個元素。
private V putForNullKey(V value) {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++;
addEntry(0, null, value, 0);
return null;
}
private V getForNullKey() {for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null)
return e.value;
}
return null;
}確定陣列 index：hashcode % table.length 取模
HashMap 存取時，都需要計算當前 key 應該對應 Entry[]陣列哪個元素，即計算陣列下標；演算法如下：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {return h & (length-1);
}按位取並，作用上相當於取模 mod 或者取餘 %。
這意味著陣列下標相同，並不表示 hashCode 相同。
table 初始大小
public HashMap(int initialCapacity, float loadFactor) {
.....
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();}注意 table 初始大小并不是构造函数中的 initialCapacity！！而是 >= initialCapacity 的 2 的 n 次幂！！！！
解決 hash 衝突的辦法
- 開放定址法（線性探測再雜湊，二次探測再雜湊，偽隨機探測再雜湊）
- 再雜湊法
- 鏈地址法
- 建立一個公共溢位區
Java 中 hashmap 的解決辦法就是採用的鏈地址法。
再散列 rehash 过程
當雜湊表的容量超過預設容量時，必須調整 table 的大小。當容量已經達到最大可能值時，那麼該方法就將容量調整到 Integer.MAX_VALUE 返回，這時，需要建立一張新表，將原表的對映到新表中。
/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
*
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];
if (e != null) {src[j] = null;
do {
Entry<K,V> next = e.next;
// 重新计算 index
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}常見問題
如果兩個鍵的 hashcode 相同，你如何獲取值物件？
當我們呼叫 get()方法，HashMap 會使用鍵物件的 hashcode 找到 bucket 位置，然後獲取值物件。找到 bucket 位置之後，會呼叫 keys.equals()方法去找到連結串列中正確的節點，最終找到要找的值物件。
如果 HashMap 的大小超過了負載因子 (load factor) 定義的容量，怎麼辦？
hashMap 預設的負載因子大小為 0.75，也就是說，當一個 map 填滿了 75% 的 bucket 時候，和其它集合類 (如 ArrayList 等) 一樣，將會建立原來 HashMap 大小的兩倍的 bucket 陣列，來重新調整 map 的大小，並將原來的物件放入新的 bucket 陣列中。這個過程叫作 rehashing，因為它呼叫 hash 方法找到新的 bucket 位置。
當重新調整 HashMap 大小的時候，確實存在條件競爭，因為如果兩個執行緒都發現 HashMap 需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，儲存在連結串列中的元素的次序會反過來，因為移動到新的 bucket 位置的時候，HashMap 並不會將元素放在連結串列的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那麼就死迴圈了。
為什麼 String, Interger 這樣的 wrapper 類適合作為鍵？
String, Interger 這樣的 wrapper 類作為 HashMap 的鍵是再適合不過了，而且 String 最為常用。因為 String 是不可變的，也是 final 的，而且已經重寫了 equals()和 hashCode()方法了。其他的 wrapper 類也有這個特點。不可變性是必要的，因為為了要計算 hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的 hashcode 的話，那麼就不能從 HashMap 中找到你想要的物件。不可變性還有其他的優點如執行緒安全。如果你可以僅僅通過將某個 field 聲明成 final 就能保證 hashCode 是不變的，那麼請這麼做吧。因為獲取物件的時候要用到 equals()和 hashCode()方法，那麼鍵物件正確的重寫這兩個方法是非常重要的。如果兩個不相等的物件返回不同的 hashcode 的話，那麼碰撞的機率就會小些，這樣就能提高 HashMap 的效能。
我們可以使用自定義的物件作為鍵嗎？
你可能使用任何物件作為鍵，只要它遵守了 equals()和 hashCode()方法的定義規則，並且當物件插入到 Map 中之後將不會再改變了。如果這個自定義物件時不可變的，那麼它已經滿足了作為鍵的條件，因為當它建立之後就已經不能改變了。
我們可以使用 CocurrentHashMap 來代替 Hashtable 嗎？
Hashtable 是 synchronized 的，但是 ConcurrentHashMap 同步效能更好，因為它僅僅根據同步級別對 map 的一部分進行上鎖。ConcurrentHashMap 當然可以代替 HashTable，但是 HashTable 提供更強的執行緒安全性。
為什麼需要使用 Hashcode？
Java 中的集合（Collection）有兩類，一類是 List，再有一類是 Set。前者集合內的元素是有序的，元素可以重複；後者元素無序，但元素不可重複。那麼這裡就有一個比較嚴重的問題了：要想保證元素不重複，可兩個元素是否重複應該依據什麼來判斷呢？這就是 Object.equals 方法了。但是，如果每增加一個元素就檢查一次，那麼當元素很多時，後新增到集合中的元素比較的次數就非常多了。也就是說，如果集合中現在已經有 1000 個元素，那麼第 1001 個元素加入集合時，它就要呼叫 1000 次 equals 方法。這顯然會大大降低效率。
於是，Java 採用了雜湊表的原理。雜湊演算法也稱為雜湊演算法，是將資料依特定演算法直接指定到一個地址上。可以這樣簡單理解，hashCode 方法實際上返回的就是物件儲存位置的映像。
這樣一來，當集合要新增新的元素時，先呼叫這個元素的 hashCode 方法，就能定位到它應該放置的儲存位置。如果這個位置上沒有元素，它就可以直接儲存在這個位置上，不用再進行任何比較了；如果這個位置上已經有元素了，就呼叫它的 equals 方法與新元素進行比較，相同的話就不存了，不相同就表示發生衝突了，散列表對於衝突有具體的解決辦法，但最終還會將新元素儲存在適當的位置。這樣一來，實際呼叫 equals 方法的次數就大大降低了，幾乎只需要一兩次。
正文完
spring
学习了
cskepper
非常有用，已经顺利解决
Yosheng
這可能是代理服務器的問題了...
淑淑
我在大陸使用了VPN 照著你說的操作 但是出現無法透過代理伺服器連線 我的電腦是W7 也下載了兼容版 用了大概一個星期後今天LINE就無法使用VPN了 這種要怎樣解決
SADFISH
我无法播放语音是为什么呀楼主
RickyEric
請問微信是多少呢