HashMap是面试中经常被问到的一个问题，不管是初级还是中级以及高级，都会问到，只不过深度不一样，今天我们就详细解析一下HashMap的源码,为了大家能碎片时间看完，我们分为多篇文章解析，首先从1.7JDK版本开始解析，
基本概念我且以为大家都知道，那么我们开始1.7JDK的源码看起,下图就是HashMap数据结构
put方法
代码语言：javascript复制 public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null) //1.key为null处理
return putForNullKey(value);
int hash = hash(key); //2.计算hash值
int i = indexFor(hash, table.length);//3.找到数组的下表
for (Entry<K,V> e = table[i]; e != null; e = e.next) { //4.遍历链表找到对应的值
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//5.如果找到对应的key,就会覆盖值，返回老值oldValue
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//6.如果找不到就新增一个Entry节点
modCount ;
addEntry(hash, key, value, i);
return null;
}
- 首先处理key=null的情况
- 如果不等于null,就会计算key的hash值
- 找到数组的下标
- 根据下标循环遍历链表
- 如果找到对应的key,就会覆盖值
- 如果没有找到就会新增一个Entry节点
然后我们再看看put里面的重要逻辑方法，首先我们看看
putForNullKey
代码语言：javascript复制 private V putForNullKey(V value) {
//1.对于key=null的值，统一放到table[0]中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//2.找到key为null的值，就会替换旧值，然后旧值
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount ;
//3.这里是在table[0]中没有找到，则新建一个key=null的entry
addEntry(0, null, value, 0);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//4.如果size超过threshold且table[0]不为null,
if ((size >= threshold) && (null != table[bucketIndex])) {
//5.进行扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//6.重新进行计算下标
bucketIndex = indexFor(hash, table.length);
}
//7.使用头插法进行新增节点
createEntry(hash, key, value, bucketIndex);
}
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 ;
}putForNullKey逻辑比较简单，首先选择table[0]位置的链表，然后对链表做遍历找到key=null的节点，将新值替换旧值，然后旧的值,如果未找到,则新增一个key为null的Entry节点
其中addEntry的逻辑是新增一个entry,他还负责扩容机制,扩容之后就会进行迁移数据，即把旧数组的链表转移到新数组，然后重新计算下标，然后使用头插法新增节点
hash方法和indexFor方法
代码语言：javascript复制 //扰动函数就是为了减少hash冲突
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//这里使用与运算,性能会更好，且hashMap的长度是2的次幂
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);
}这里hash函数是为了尽可能的均匀分布，减少hash冲突,其中就是想保留高位和低位，然后高位和低位进行与运算，而indexFor是为了计算数组下标即实际的存储位置,使用与位运算是为了更高的性能
这里为什么HashMap的长度必须是2的次幂
- 降低发生碰撞的概率，使散列更均匀,
- 如果是长度是2的次幂，那么length-1的二进制最后一位一定是1，在hash值做与运算的时候，最后一位就可能是1，也可能是0,即不是偶数就是奇数,但是如果length不是2的次幂，则length-1就是一个偶数，因此导致h&(length-1)只能是奇数，就会浪费一半的空间
get方法
代码语言：javascript复制 public V get(Object key) {
if (key == null)
//1.如果key=null，则遍历数组的table[0]，获取到对应的value,否则返回null
return getForNullKey();
//2.key!=null，调用下面方法获取
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) {
//3.如果size=0.则返回null
if (size == 0) {
return null;
}
//4.计算key的hash值
int hash = (key == null) ? 0 : hash(key);
//5.根据hash值计算下标,然后循环遍历链表获取对应可以的value
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;
}
get方法就比较简单，如果key=null,就在table[0]链表中获取对应的值，如果key!=null,就计算key的hash值，计算下标位置，然后遍历对应的链表找到对应的value,否则返回null
