本系列文章所描述的所有类或接口都是基于 JDK 1.7的源码，在其它 JDK 的实现方式中可能会有所不同。
一、实现方式
HashMap 是 Map 实现中最常用的，具体实现方式如下。
二、创建 HashMap
将 loadFactor 设为默认的 0.75，threshold 设置为 16。HashMap 还提供了另外三个构造函数：HashMap(int initialCapacity)、HashMap(int initialCapacity, float loadFactor)、HashMap(Map<? extends K, ? extends V> m)。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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();
}
void init() {
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
三、添加元素 put(K key, V value)
首先判断 Entry<K,V>[] 数组是否为空数组，如果是空数组，则初始化数组。在初始化数组的过程中首先计算 capacity 的值和 threshold 的值，注意：这里才是真正初始化 Entry 数组的大小。创建的 Entry 对象数组的大小，并非传入的初始容量值，而是采用如下方式来决定：
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
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;
}
比如默认传进去的 toSize=16，则计算出来的 capacity=16，其中 Integer.highestOneBit 方法是计算最高的1位，其余位设置为0。如果我们在构造函数中指定初始化容量为5，那么计算出来的 capacity=8。如果我们在构造函数中指定初始化容量为10，那么计算出来的 capacity=16。这也是如果我们在初始化时要指定 HashMap 的容量时设置的值最好设置为2的指数方的值的原因。默认情况下创建的 Entry 对象数组的大小为 16，threshold 为 12。
对于 key 为 null 的情况，HashMap 的做法为获取 Entry 数组中的第一个 Entry 对象，并基于 Entry 对象的 next 属性遍历。当找到了其中 Entry 对象的 key 属性为 null 时，则将其 value 赋值为新的 value，然后返回。如没有 key 属性为 null 的 Entry，则增加一个 Entry 对象，增加时为先获取当前数组的第一个 Entry 对象：e，并创建 Entry 对象，key 为 null，value 为新传入的对象，next 为之前获取的 e，如此时 Entry 数组中已有的大小 ≥ threshold，则将 Entry 数组扩大为当前大小的两倍，扩大时对当前 Entry 对象数组中的元素重新 hash，并填充数组，最后重新设置 threshold 值。
对于 key 不为 null 的情况，首先获取 key 对象本身的 hashCode，然后再对此 hashCode 做 hash 操作。
hash 完毕后，将 hash 出来的值与 Entry 对象数组的大小减 1 的值进行按位与操作，从而得出当前 key 要存储到数组的位置。从这个过程可以看出，可能会出现不同的 key 找到相同的存储位置的问题，也就是数据结构中经典的 hash 冲突的问题了，来看看 HashMap 的解决方法。
在找到要存储的目标数组的位置后，获取该数组对应的 Entry 对象，通过调用 Entry 对象的 next 来进行遍历，寻找 hash 值和计算出来的 hash 值相等，且 key 相等或 equals 的 Entry 对象，如寻找到，则替换此 Entry 对象的值，完成 put 操作，并返回旧的值；如未找到，则往对应的数组位置增加新的 Entry 对象，增加时采取的方法和 key 为 null 的情况基本相同，只是它是替换指定位置的 Entry 对象，可以看出，HashMap 解决冲突采用的是链表的方式，而不是开放地址的方法。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
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++;
addEntry(hash, key, value, i);
return null;
}
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 = 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;
}
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;
}
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;
}
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 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 = 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];
newTable[i] = e;
e = next;
}
}
}
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);
}
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++;
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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) {
}
}
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
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);
}
四、获取元素 get(Object key)
get 的过程和 put 一样，也是根据 key 是否为 null来分别处理的。对于 key 为 null 的情况下，则直接获取数组中第一个 Entry 对象，并基于 next 属性进行遍历，寻找 key 为null 的 Entry 对象，如找到则返回 Entry 对象的 value，如未找到，则返回 null；对于 key 为非 null 的情况下，则对 key 进行 hash 和按位与操作，找到其对应的存储位置，然后获取此位置对应的 Entry 对象，基于 next 属性遍历，寻找到 hash 值相等，且 key 相等或 equals 的 Entry 对象，返回其 value，如未找到，则返回 null。
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 : 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;
}
五、删除元素 remove(Object key)
remove 的过程和 get 类似，只是在找到匹配的 key 后，如数组上的元素等于 key ，则将数组上的元素的值置为其 next 元素的值；如数据上的元素不等于 key，则对链表遍历，一直到找到匹配的 key 或链表的末尾。
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
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;
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;
}
七、判断元素是否存在 containsKey(Object key)
通过调用 getEntry 方法来完成，getEntry 方法和 get 过程基本相同。只是在找到匹配的 key 后，直接返回 Entry 对象，而 containsKey 判断返回的 Entry 对象是否为 null，为 null 则返回 false，不为 null 则返回 true。
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : 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;
}
八、遍历元素 keySet()
在使用 Map 时，经常会通过 keySet 来遍历 Map 对象，调用 keySet 方法后会返回一个 HashMap 中的 KeySet对象实例，此 KeySet 对象继承了 AbstractSet。当调用 iterator 方法时，返回一个 KeyIterator 对象实例，调用 next 方法时，遍历整个数组及 Entry 对象的链表，如在遍历过程中有新的元素加入或删除了元素，则会抛出 ConcurrentModificationException。
HashMap 在遍历时是无法保证顺序的，如果要保证 Map 中的对象是按顺序排列的，最好是使用 TreeMap。
HashMap 是非线程安全的，在并发场景中如果不保持足够的同步，就有可能在执行 HashMap.get时进入死循环，将 CPU 消耗到 100%，在并发场景中可通过 Collections.synchronizedMap、Collections.unmodifiableMap 或自行同步来保障线程安全，但这些实现方式通常性能会在高并发时下降迅速，最好的方法仍然是使用 ConcurrentHashMap。
六、注意要点
对于 HashMap 而言，最要注意的有以下几点：
- HashMap 采用数组方式存储key、value构成的 Entry 对象，无容量限制；
- HashMap 基于 key hash 寻找 Entry 对象存放到数组的位置，对于 Hash 冲突采用链表的方式来解决；
- HashMap 在插入元素时可能会要扩大数组的容量，在扩大容量时需要重新计算 hash，并复制对象到新的数组中；
- HashMap是非线程安全的。
网友评论