HashMap是容器类中很重要的一个类，Set类是使用Map来实现的，在HashMap基础上产生了ConcurrentHashMap，用途非常广泛，所以需要仔细分析分析。
类定义
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{}
HashMap继承了AbstractMap，实现了Map接口。首先我们看下Map接口有哪些主要方法。
public interface Map<K,V>{
int size();//返回map中的元素个数，也就是key-value的对数。
boolean isEmpty();//判断map是否为空
boolean containsKey(Object key);//返回map中是否包含此key
boolean containsValue(Object value);//返回map中是否包含此value
V get(Object key);//返回此key对应的value，如果不存在则返回null。如果map允许存放null值，那么需要使用containsKey(Object key)来区别这种情况。
//以上都是query operations，下面是modification operations
V put(K key,V value);//将key和value关联起来存放到map中，如果之前不存在key，则返回null,否则返回之前的oldValue。
V remove(Object key);//根据key移除key-value键值对。如果存在key-value，则返回value值，否则返回null。
/* bulk operation*/
void putAll(Map<? extends K, ? extends V> m);//将一个map内的键值对存储到此map中。
void clear();//清空此map
/* views */
Set<K> keySet();//将key以Set<K>的方式返回
Collection<V> values(); //返回values
Set<Map.Entry<K, V>> entrySet(); //返回entrySet
/* Entry interface*/
interface Entry<K,V>{
K getKey();
V getValue();
V setValue();
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
Map接口定义了实现一个Map需要的基本方法，而AbstractMap则产生了一个Map的基本骨架，主要利用entrySet()方法实现了containsValue containsKey size等方法。
主要成员变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默认初始化大小
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量，如果指定了更大的容量，则会使用此容量。
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的load factor
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 存储Entry的数组
transient int size; //key-value键值对的数量
int threshold; //扩容的阈值 超过此值则扩容
final float loadFactor;//load factor
transient int modCount; //HashMap被结构性改变的次数，用来实现fail-fast机制。注意替换value不是结构性改变。
构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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();
}
如果不提供initialCapacity和loadFactor则使用默认值。
主要方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold); //如果数组是空的，那么就扩容
}
if (key == null)
return putForNullKey(value); //hashmap允许null键
int hash = hash(key); //根据key计算hash值
int i = indexFor(hash, table.length);//计算应该放到哪个桶里
//找到桶 如果桶里有相同的key，则将oldValue替换为新value
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);//添加元素到map
return null;
}
首先看看inflateTable(int toSize)方法。
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);
}
这个方法字面意思是使数组膨胀，也就是数组扩容。根据这里面indexFor的方法(后续会说)，数组的大小需要是2的幂次，但是HashMap初始化时可以提供任意initialCapacity，HashMap在put方法中保证了提供一个2的幂次，这个数字稍大于initialCapacity。roundUpToPowerOf2(int size)提供了该功能。
loadFactor表示的是HashMap的充满程度，比如capacity是100，loadFactor是0.75，则意味着键值对数量到了75时就该扩容了。如果loadFactor设置的比较大，则会造成hash冲突会较多，查找时间较长；反之，则造成空间利用率低，扩容频繁，降低性能。一般使用默认的0.75即可。
table = new Entry[capacity];这个表示了HashMap内部的存储结构，是数组+链表的形式。
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;
}
这个方法会返回大于等于number的且距离最近的2的幂次。
接下来我们看看putForNullKey(V value)方法
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
//null键是存放在table[0]里的
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++;
//如果是第一次存放null键 则存放到table[0]里
addEntry(0, null, value, 0);
return null;
}
接下来看一下hash(Object key)这个方法。
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);
}
这个方法对于String类型做了特殊处理，使用了sun.misc里的一个方法计算hash，对于其他的Object，则先获取其hashCode()，然后进行一些不可描述的位运算，最后得到一个hash值。
接下来看看indexFor(int h,int length)。
/**
* Returns index for hash code h.
*/
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);
}
这里面提到了length必须是一个2的幂次才可以。我们通常说HashMap里面计算桶的位置是对length取模(求余)，而在HashTable中确实是这么操作的,int index = (hash & 0x7FFFFFFF) % tab.length;，但是取模操作是一个很耗时间的操作，所以HashMap这里对其进行了改进，采用了位运算来代替取模运算，实际效果也是取模的效果。如果length是2的幂次，则length-1是是诸如0000111111这样的形式，然后h & (length - 1)就相当于是取模操作了。
计算好了位置，则就先去对应位置去找，如果找到了就替换value，如果没有找到就添加一个新的键值对。
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果需要扩容的话 则执行resize方法
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];
//采用头插法将Entry放到第一个位置
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;
}
...
Entry是具体的储存key和value的类，next变量表示了这是一个链表结构。
resize(int capacity)是具体的扩容操作。
void resize(int newCapacity) {
//oldTable代表table
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);
}
/**
* Transfers all entries from current table to newTable.
*/
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;
}
}
}
这里面会有一个rehash的问题，会把每一个Entry都重新放到新的table里。这个操作是比较耗时间的。
到这里基本put方法就说完了。
接下来看一下get方法。
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return 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;
}
这个方法比较简单，就是根据hash找到在数组中的位置，然后沿着链表查找。
接下来看下remove方法，删除一个链表节点。
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;
}
同步
HashMap不是同步容器，解决方法是使用Collections.synchronizedMap将HashMap包装成同步容器，或者使用ConcurrentHashMap。
