Java7源码分析
先看下Java7里的HashMap实现，有了上面的分析，现在在源码中找具体的实现。
//HashMap里的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//Entry对象，存key、value、hash值以及下一个节点
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
//默认数组大小，二进制1左移4位为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4；
//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当前存的键值对数量
transient int size;
//阈值 = 数组大小 * 负载因子
int threshold;
//负载因子变量
final float loadFactor;
//默认new HashMap数组大小16，负载因子0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//可以指定数组大小和负载因子
public HashMap(int initialCapacity, float loadFactor) {
//省略一些逻辑判断
this.loadFactor = loadFactor;
threshold = initialCapacity;
//空方法
init();
}
</pre>
|
</figure>
以上就是HashMap的一些先决条件，接着看平时put操作的代码实现，put的时候会遇到3种情况上面已分析过，看下Java7代码：
public V put(K key, V value) {
//数组为空时创建数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key为空单独对待
if (key == null)
return putForNullKey(value);
//①根据key计算hash值
int hash = hash(key);
//②根据hash值和当前数组的长度计算在数组中的索引
int i = indexFor(hash, table.length);
//遍历整条链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//③情况1.hash值和key值都相同的情况，替换之前的值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
//返回被替换的值
return oldValue;
}
}
modCount++;
//③情况2.坑位没人,直接存值或发生hash碰撞都走这
addEntry(hash, key, value, i);
return null;
}
先看上面key为空的情况(上面画图的时候总要在第一格留个空key的键值对)，执行 putForNullKey() 方法单独处理，会把该键值对放在index0，所以HashMap中是允许key为空的情况。再看下主流程：
步骤①.根据键值算出hash值 — > hash(key)
步骤②.根据hash值和当前数组的长度计算在数组中的索引 — > indexFor(hash, table.length)
static int indexFor(int h, int length) {
//hash值和数组长度-1按位与操作，听着费劲？其实相当于h%length;取余数(取模运算)
//如：h = 17，length = 16;那么算出就是1
//&运算的效率比%要高
return h & (length-1);
}
步骤③情况1.hash值和key值都相同，替换原来的值，并将被替换的值返回。
步骤③情况2.坑位没人或发生hash碰撞 — > addEntry(hash, key, value, i)
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前hashmap中的键值对数量超过阈值
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容为原来的2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//计算在新表中的索引
bucketIndex = indexFor(hash, table.length);
}
//创建节点
createEntry(hash, key, value, bucketIndex);
}
如果put的时候超过阈值，会调用 resize() 方法将数组大小扩大为原来的2倍，并且根据新表的长度计算在新表中的索引(如之前17%16 =1，现在17%32=17)，看下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];
//步骤②将键值对转移到新的数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//步骤③将新数组的引用赋给table
table = newTable;
//步骤④修改阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
上面的重点是步骤②，看下它具体的转移操作
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;
}
}
}
这段for循环的遍历会使得转移前后键值对的顺序颠倒(Java7和Java8的区别)，画个图就清楚了，假设石头的 key 的 hash 值为5，盖伦的 key 的 hash 值为37，这样扩容前后两者还是在5号坑。第一次：
image
第二次
image
最后再看下创建节点的方法
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
创建节点时，如果找到的这个坑里面没有存值，那么直接把值存进去就行了，然后size++；如果是碰撞的情况，
image
前面说的以单链表头插入的方式就是这样(盖伦：”老王已被我一脚踢开！“)，总结一下Java7 put流程图
image
相比put，get操作就没这么多套路，只需要根据key值计算hash值，和数组长度取模，然后就可以找到在数组中的位置(key为空同样单独操作)，接着就是遍历链表，源码很少就不分析了。
网友评论