注意：Java1.7和Java1.8中的HashMap实现有较大改动
Java1.7 HashMap
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- 标记接口Cloneable，用于表明
HashMap对象会重写java.lang.Object#clone()方法，HashMap实现的是浅拷贝（shallow copy）。 - 标记接口Serializable，用于表明
HashMap对象可以被序列化
比较有意思的是，HashMap同时继承了抽象类AbstractMap与接口Map，因为抽象类AbstractMap的签名为
public abstract class AbstractMap<K,V> implements Map<K,V>
Stack Overflow上解释到：
在语法层面继承接口
Map是多余的，这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的，起到了文档的作用
AbstractMap相当于个辅助类，Map的一些操作这里面已经提供了默认实现，后面具体的子类如果没有特殊行为，可直接使用AbstractMap提供的实现。
It's evil, don't use it.
Cloneable这个接口设计的非常不好，最致命的一点是它里面竟然没有clone方法，也就是说我们自己写的类完全可以实现这个接口的同时不重写clone方法。
关于Cloneable的不足，大家可以去看看《Effective Java》一书的作者给出的理由，在所给链接的文章里，Josh Bloch也会讲如何实现深拷贝比较好，我这里就不在赘述了[1]。
HashMap结构如下图所示[3]：
HashMap结构示意图
如图中所示HashMap的底层主要是基于数组和链表来实现的
transient Entry<K,V>[] table;
数据存放在table数组中，元素在数据中的位置通过Entry类的hash值来计算，通过链表法来解决hash冲突，所以有比较高的查询速度，如下图所示[2]：
链表法解决hash冲突
HashMap的属性
//hashmap的默认数组长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//hashmap中数组的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子，到达75%容量时进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存放数据的数组，大小一定是2的n次方
transient Entry<K,V>[] table;
//存放键值对的数量
transient int size;
//触发扩容的阈值，计算公式为capacity * load factor
int threshold;
//负载因子
final float loadFactor;
//用于记录HashMap被修改的次数
transient int modCount;
//useAltHashing表示是否要对字符串键的HashMap使用备选哈希函数，用于减少hash冲突发生的概率
transient boolean useAltHashing;
//对键进行哈希码计算的随机种子hashSeed
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
影响HashMap的性能参数
loadFactor
负载因子越大，表示散列表装填的元素越多，空间利用率越高，发生hash冲突的机会更高，导致链表长度会越来越长，查询效率降低
负载因子越小，表示散列表装填的元素越少，数据变稀疏后冲突的机会减小了，空间利用率变低，查询效率更高
HashMap的构造方法
//指定初始容量和负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor)
//指定负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor)
//默认无参构造方法
public HashMap()
//传入参数为Map对象的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
HashMap的内部类
Entry<K,V>静态内部类，实现了单向链表的功能，用next成员变量来级连起来
/** Entry是单向链表。
* 它是 “HashMap链式存储法”对应的链表。
*它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
**/
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;
}
//判断两个Entry是否相等，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() {
//用key的hash值与上value的hash值作为Entry的hash值
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
//put方法覆盖已经存在的key时调用此方法
void recordAccess(HashMap<K,V> m) {
}
//当移除键值对的时候调用此方法
void recordRemoval(HashMap<K,V> m) {
}
}
HashMap的主要方法
- hash方法
final int hash(Object k) {
int h = 0;
//如果useAltHashing的值为true，并且键的类型为String，则对字符串键使用备选哈希函数，否则，返回用于对键进行哈希码计算的随机种子hashSeed
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
其中hash运算规则以h=0x7FFFFFFF为例，则上面最后两步对h的运算过程如下图[4]：
hash计算规则
在哈希表容量（也就是buckets或slots大小）为length的情况下，为了使每个key都能在冲突最小的情况下映射到[0,length)（注意是左闭右开区间）的索引（index）内，一般有两种做法：
- 让length为素数，然后用
hashCode(key) mod length的方法得到索引 - 让length为2的指数倍，然后用
hashCode(key) & (length-1)的方法得到索引
HashTable用的是方法1，HashMap用的是方法2。关于方法1为什么要用素数，可以参考这里。
重点说说方法2的情况，方法2其实也比较好理解[1]：
因为length为2的指数倍，所以
length-1所对应的二进制位都为1，然后在与hashCode(key)做与运算，即可得到[0,length)内的索引
但是这里有个问题，如果hashCode(key)的大于length的值，而且hashCode(key)的二进制位的低位变化不大，那么冲突就会很多，举个例子：
Java中对象的哈希值都32位整数，而HashMap默认大小为16，那么有两个对象那么的哈希值分别为：
0xABAB0000与0xBABA0000，它们的后几位都是一样，那么与16异或后得到结果应该也是一样的，也就是产生了冲突。
造成冲突的原因关键在于16限制了只能用低位来计算，高位直接舍弃了，所以我们需要额外的哈希函数而不只是简单的对象的hashCode方法了。
具体来说，就是HashMap中hash函数干的事了
首先有个随机的hashSeed，来降低冲突发生的几率
然后如果是字符串，用了
sun.misc.Hashing.stringHash32((String) k);来获取索引值最后，通过一系列无符号右移操作，来把高位与低位进行异或操作，来降低冲突发生的几率
右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该就是把高位与低位做异或运算，至于这几个数是如何选取的，就不清楚了，网上搜了半天也没统一且让人信服的说法，大家可以参考下面几个链接：
- http://stackoverflow.com/questions/7922019/openjdks-rehashing-mechanism/7922219#7922219
- http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function/9336103#9336103
- http://stackoverflow.com/questions/14453163/can-anybody-explain-how-java-design-hashmaps-hash-function/14479945#14479945
- indexFor方法
//h表示通过hash(Object k)方法计算得来的哈希码，length表示桶的数量（即数组的长度）
static int indexFor(int h, int length) {
return h & (length-1);
}
将哈希码和length进行按位与运算映射到闭区间[0,length-1]中
- put方法
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//得到key的hash值
int hash = hash(key);
//找到hash值所在桶的位置
int i = indexFor(hash, table.length);
//当新增的key所对应的索引i，对应table[i]中已经有值时，进入循环体
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断是否存在本次插入的key，如果存在用本次的value替换之前oldValue，相当于update操作
//并返回之前的oldValue
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;
}
- addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
////如果增加一个元素会后，HashMap的大小超过阈值，需要resize
if ((size >= threshold) && (null != table[bucketIndex])) {
//增加的幅度是之前的1倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//扩容后，桶的数量增加了，故需要重新对键进行哈希值计算
bucketIndex = indexFor(hash, table.length);
}
//在指定的桶中创建一个新的对象以存储我们传入的键值对
createEntry(hash, key, value, bucketIndex);
}
- createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) {
//首先得到该索引处的冲突链Entries，有可能为null，不为null
Entry<K,V> e = table[bucketIndex];
//把新的Entry添加到链表的队首，也就是说后插入的在前面
//需要注意的是table[bucketIndex]本身并不存储节点信息，它只保存了单向链表的头指针，数据都存放在单链表中
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
- resize方法
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];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//重新hash
boolean rehash = oldAltHashing ^ useAltHashing;
//对原来的数据转移至新的桶数组中，在迁移过程中，桶的位置会发生变化
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
- transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍历当前的table，将里面的元素添加到新的newTable中
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;
}
}
}
- get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
- getForNullKey方法
private V getForNullKey() {
//key为null的Entry用于放在table[0]中，找到table[0]中key为null的值并返回
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
- getEntry方法
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
//首先定位到索引在table中的位置，然后遍历链表，查找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方法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
- removeEntryForKey方法
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
//遍历单链表，删除指定key值的Entry
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的数据结构决定了它有几点特性：
- 不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能改变（resize的情况）
- put、get操作的时间复杂度为O(1)
- 遍历其集合视角的时间复杂度与其容量（capacity，槽的个数）和现有元素的大小（entry的个数）成正比，所以如果遍历的性能要求很高，不要把capactiy设置的过高或把平衡因子（load factor，当entry数大于capacity*loadFactor时，会进行resize，reside会导致key进行rehash）设置的过低
- 由于HashMap是线程非安全的，这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变（添加、删除entry，只改变entry的value的值不算结构改变），那么会报ConcurrentModificationException，专业术语叫
fail-fast，尽早报错对于多线程程序来说是很有必要的
HashMap的序列化[1]
从源代码中可以看到保存Entry的table数组为transient的，也就是说在进行序列化时，并不会包含该成员，这是为什么呢？
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
为了解答这个问题，我们需要明确下面事实：
Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值
我们可以试想下面的场景：
我们在机器A上算出对象A的哈希值与索引，然后把它插入到HashMap中，然后把该HashMap序列化后，在机器B上重新算对象的哈希值与索引，这与机器A上算出的是不一样的，所以我们在机器B上get对象A时，会得到错误的结果。
所以说，当序列化一个HashMap对象时，保存Entry的table是不需要序列化进来的，因为它在另一台机器上是错误的。
因为这个原因，HashMap重现了writeObject与readObject 方法
- writeObject方法
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator<Map.Entry<K,V>> i =
(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
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());
}
}
}
- readObject方法
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 hashSeed (can only happen after VM boot)
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
sun.misc.Hashing.randomHashSeed(this));
// Read in number of buckets and allocate the bucket array;
s.readInt(); // ignored
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
int initialCapacity = (int) Math.min(
// capacity chosen by number of mappings
// and desired load (if >= 0.25)
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
int capacity = 1;
// find smallest power of two which holds all mappings
while (capacity < initialCapacity) {
capacity <<= 1;
}
table = new Entry[capacity];
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
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);
}
}
- putForCreate方法
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
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);
}
参考文献
[1] http://www.importnew.com/16650.html
[2] https://www.cnblogs.com/ITtangtang/p/3948406.html
[3] http://www.importnew.com/28263.html
[4] https://www.cnblogs.com/rogerluo1986/p/5851300.html
网友评论