最近看到几篇精彩的文章:
存取之美 —— HashMap原理、源码、实践
Hash碰撞与拒绝服务攻击
这些文章让我收获良多, 但是有些地方说的不够详细, 在此写下本人对上述文章的总结和理解, 希望可以给需要的朋友带来一些帮助.
1. 概述
HashMap在底层采用数组+链表的形式存储键值对.
在HashMap中定义了一个内部类Entry<K, V>, 该内部类是对key-value的抽象. Entry类包含4个成员: key, value, hash, next. key和value的意义很清晰, hash表示key的hash值, next是指向下一个Entry对象的引用.
HashMap内部维护了一个Entry<K, V>[] table, 数组table中的Entry元素是一个Entry链表的头结点(理解这一点很重要).?
2. put/get方法
向HashMap中添加键值对时, 程序会根据key的hashCode值计算出hash值, 然后对hash值取模, 模数是table.length. 假如取模的结果为index, 则取出table[index]. table[index]可能为null, 也可能是一个Entry对象. 如果为null, 则直接存储. 否则计算key.equals(table[index].key), 如果为false, 就取出table[index].next, 继续调用key的equals方法, 直到equals方法返回true, 或者比较完链表中所有Entry对象.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
// 对hashCode值进行二次hash得到最终的hash值
int hash = hash(key.hashCode());
// 根据hash值定位数组中的索引位置
int i = indexFor(hash, table.length);
// 遍历table[i]位置处的链表
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果hash值相同且equals返回true, 则替换原来的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++;
// 如果之前函数没有return, 将该键值对插入table[i]链表中
addEntry(hash, key, value, i);
return null;
}
理解了put方法, 那么get方法就会很容易理解:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
// 首先根据hash值计算index, 然后取出index处的链表的头结点. 遍历链表.
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;
}
??
3. HashMap的容量和索引位置确定
前面没有叙述HashMap的容量问题, 是因为容量是与索引位置计算紧密相关的.
理解HashMap的容量就需要关注成员变量size, loadFactor, threshold.
size表示HashMap中实际包含的键值对个数.
loadFactor表示负载因子, loadFactor的值越大, 则对table数组的利用率越大, 相当于节省内存空间. 但是loadFactor的值增大, 同时也会导致hash冲突的概率增加, 从而使得程序效率降低. loadFactor的取值应该兼顾内存空间和效率, 默认值为0.75.
threshold表示极限容量, 计算公式为threshold = (int)(capacity * loadFactor); ?当size达到threshold时, 就需要对table数组扩容.
HashMap的容量大小就是table.length. 由于java中取模是一个效率低下的操作, 所以出于性能的考虑, HashMap的容量被设计为2的N次方. 如此hash%table.length就可以转换为hash&(table.length-1). 与运算的效率比取模运算高效很多.
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);
// 计算大于initialCapacity的最小的2的N次方数
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 求出极限容量
threshold = (int) (capacity * loadFactor);
// table的容量被设计为2的N次方
table = new Entry[capacity];
init();
}
如果使用无参的构造函数创建HashMap, 则容量默认为16, 负载因子默认为0.75.
indexFor函数用于确定索引位置:
static int indexFor(int h, int length) {
// 当length为2的N次方时相当于h%table.length, 但效率要高效很多
return h & (length - 1);
}
?
4. rehash
前面提到过, 当size达到threshold时, 就需要对table数组扩容. 调用put函数向HashMap中插入一个键值对时会调用到addEntry(hash, key, value, i)方法:
void addEntry(int hash, K key, V value, int bucketIndex) {
// 取出索引处的Entry对象
Entry<K, V> e = table[bucketIndex];
// 更新索引处链表的头结点, 并使新的头结点的next属性指向原来的头结点
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
// 当size大于threshold时扩容数组, 容量增加至原来的2倍. 保证table的容量始终是2的N次方
if (size++ >= threshold)
resize(2 * table.length);
}
resize用于扩容数组. 数组的length增加大了, 那么HashMap中已有的键值对就必须重新进行hash, 这就是rehash. 如果不进行rehash, 就会使得put和get时table数组的length不同, 从而导致get方法无法取出原先put存入的键值对.
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);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
// 对已有的键值对进行rehash
for (int j = 0; j < src.length; j++) {
// 得到j处的链表的头结点
Entry<K, V> e = src[j];
// 遍历链表
if (e != null) {
src[j] = null;
do {
// 进行rehash
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
从源码可以看出, rehash对性能的影响是非常大的, 因此我们应该尽量避免rehash的发生. 这就要求我们预估需要存入HashMap的键值对的数量, 根据数量在创建HashMap对象时指定合适的容量和负载因子.
5. hash碰撞和HashMap的退化
hash碰撞在HashMap中的表现为: 不同的key, 计算出相同的index. 如果对所有的key调用indexFor方法的返回值都是相同的, 那么HashMap就退化为链表, 这对性能的影响也是非常大的. 几个月前的闹得沸沸扬扬的hash碰撞攻击就是基于这样的原理.
常用的web框架都会将请求中的参数保存在HashMap(或HashTable)中, 如果客户端根据Web应用框架采用的Hash函数来通过某种Hash攻击的方式获得大量的碰撞, 那么HashMap就会退化为链表, 服务器有可能处理一次请求要花上十几分钟甚至几个小时的时间...
6. 线程安全
HashMap是线程不安全的, 如果遍历HashMap的过程中修改了HashMap, 那么就会抛出java.util.ConcurrentModificationException异常:
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;
}
modCount是HashMap的成员变量, 用于表示HashMap的状态. expectedModCount是遍历初始时modCount的值. 如果在遍历过程中改变了modCount的值就会导致modCount和expectedModCount不相等, 从而抛出异常. put, clear, remove等方法都会导致modCount的值改变.
?
相关文章
