今天我看了一下HashMap,作为java用的最多的集合，我们有必要去了解一下其底层的实现原理。
1.hashMap概述
hashMap底层是数组+ 链表的形式，因此其具有查询快，插入删除也快的特点。它是基于哈希表的 Map 接口的实现。其是以key-value的形式存在，也就是键值对
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
由其定义来看，实现了Cloneable，Serializable接口，继承了AbstractMap接口
因此它是可以克隆，可以被序列化的
2.hashMap构造函数
这里构造具有一个默认初始容量（16）和负载因子（0.75）
- 初始容量：其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量
- 负载因子：衡量其容量自动增加之前可以达到多满的一种尺度，即散列表的空间的使用程度
- 负载因子越大表示散列表的装填程度越高，反之愈小
- 负载因子越大，空间利用率越高，同时查找效率就越低
3.HashMap的数据结构
HashMap底层实现是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。下面为HashMap构造函数的源码：
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能<0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
//初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能 < 0
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;
//设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
threshold = (int) (capacity * loadFactor);
//初始化table数组（关键）
table = new Entry[capacity];
init();
}
}
总结：初始容量不能 < 0 不能 > 2^30,负载因子不能< 0
- 可以看出初始化的话HashMap 会初始化一个Entry数组，其元素为Entry 下面我们看Entry这个内部类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
//指向下一个Entry
Entry<K,V> next;
final 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为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，这是非常重要的，正是由于Entry才构成了table数组的项为链表。
4.HashMap的快速存储put(Key K,Value V)
public V put(K key, V value) {
//当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode()); ------(1)
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length); ------(2)
//从i出开始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同，则直接覆盖value，返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
}
4.1分析
源码我们可以知道put方法的过程为：
1.判断是否为null，是则接调用putForNullKey方法，不是则计算hash
2.然后根据hash值搜索在table数组中的索引位置
3.如果table数组在该位置处有元素，则通过比较是否存在相同的key
4.若存在，则覆盖掉之前的value，否则将该元素保存在链表头
4.2迭代处
- 先看迭代处。此处迭代原因就是为了防止存在相同的key值，若发现两个hash值（key）相同时，HashMap的处理方式是用新value替换旧value，这里并没有处理key，这就解释了HashMap中没有两个相同的key。
- 在看（1）、（2）处。这里是HashMap的精华所在。首先是hash方法，该方法为一个纯粹的数学计算，就是计算h的hash值。
- 以上目的就是为了减少Hash碰撞，尽可能均匀分布在hash表中。
4.3HashMap具体实现装key-value
void addEntry(int hash, K key, V value, int bucketIndex) {
//获取bucketIndex处的Entry也就是hash计算出来的位置
Entry<K, V> e = table[bucketIndex];
//将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry指向原来的 Entry,也就是Entry.next = e
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的个数超过极限了，则容量扩大两倍
if (size++ >= threshold)
resize(2 * table.length);
}
}
- 链表的产生
- 这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象，那么新添加的Entry对象将指向原有的Entry对象，形成一条Entry链，但是若bucketIndex处没有Entry对象，也就是e==null,那么新添加的Entry对象指向null，也就不会产生Entry链了。
- 扩容
随着HashMap中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。
该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
网友评论