1. HashMap的数据结构
HashMap实际上是一个“链表散列”的数据结构，是数组与链表的结合体。HashMap底层就是一个数组结构，数组的每一项又是一个链表。当新建一个HashMap时就会初始化一个数组。如下图所示：
Entry类是HashMap中的内部类，其中有两个属性分别代表“键、值”。数组中每个元素是Entry类型的，它持有指向下一个元素的引用，这就构成了链表。以下是其源码：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
//other code……..
}
2. HashMap的存取过程
HashMap的存储方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key); //根据key计算出hash值
int i = indexFor(hash, table.length); //由hash值求索引
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;
}
可以看出，先计算出key的hash值（依赖于key.hashCode()实现），由hash值求出table数组的索引。在该索引位置对应的链表结构中依次查找，看是否已经存在了具有与该key相同（依赖于key.equals()实现）的元素。若找到了则更新这个元素的value，否则为这个key新创建一个entry，保存在链头（最先保存的元素放在链尾）。
HashMap的读取方法：
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) {
//空的Map，返回null
if (size == 0) {
return null;
}
//根据key计算hash值
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;
}
可以看出，读取的时候也是先根据key计算出hash值，根据hash值计算出数组索引，然后遍历索引对应的链表直到找到并返回该元素，如果仍然未找到则返回null，表示该key不存在。
3. HashMap的扩容机制（rehash）
它有3个构造方法：
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();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
使用无参的构造方法，默认的初始容量（initialCapacity）为16，加载因子（loadFactor）为0.75。
若（数组已使用的大小>=总容量*加载因子），表示此时再向HashMap中添加新元素的话，出现hash碰撞的可能性会很大，因此会把数组的总容量提升至原总容量的2倍。即在默认情况下，若数组中的元素超过12时，将数组的大小提升至32。然后重新计算每个元素在数组中的索引，并对发生hash碰撞的元素依次追加到索引对应的链表中。这个过程叫做rehash。这是个非常耗性能的操作，所以，如果可以预估且设置HashMap的初始大小则可以有效避免rehash，提高性能。
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);
}
TIPS:
- HashMap和Hashtable的区别
Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高些；但如果多线程访问同一个Map对象，使用Hashtable实现类更好。
Hashtable不允许使用null作为key和value，如果为null，则引发NullPointerException异常；但HashMap可以使用null作为key或value。 - Object.hashCode()和这里提到的HashMap.hash()的关系
首先，Object.hashCode()方法是属于Object类的，而Java中所有的类都继承自Object类，所以所有的类都具有hashCode方法。
Object中hashCode()方法的定义：
public native int hashCode();
它是一个native方法，表明默认是交给操作系统实现的。我们自己定义的类可以重写这个方法的实现，如果没有，那么就会调用其父类（直到Object类）中的这个方法。它的用途是根据这个对象，返回一个整型数值。
下面再看看HashMap.hash()方法的实现：
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);
}
方法签名上可以看出也是根据一个对象，返回一个整型数值。然而在其实现中，它调用了该对象自身的hashCode方法。因此，不难看出当一个对象作为HashMap的KEY时，其被分到哪个slot中与其自身的hashCode()方法是有关系的。
这也就是为什么会提倡在自定义一个类的时候，最好同时重写其equals()和hashCode()方法。因为，这个类的对象有可能被别人当作HashMap的KEY使用。
从另一个角度看，如果你将要使用了一个自定义的类的对象当作HashMap的KEY，一定要先去该类的定义中看看有没有重写equals()和hashCode()方法。
-- EOF --
