JDK1.7HashMap源码分析
JDK1.7及以前的版本中的HashMap底层是采用数组加链表的方式存储数据的，当hash值冲突时会在对应的节点以链表的方式来存储这些hash冲突的值。
整个HashMap源码主要关注的点有：
- 扩容算法
- put方法
- get方法
先看下HashMap的几个常量
// 初始容量16static final int DEFAULT_INITIAL_CAPACITY = 16;// 最大容量static final int MAXIMUM_CAPACITY = 1 << 30;// 加载因子，加载因子的作用在于当存储的容量大于等于存储容量乘以加载因子时，会触发扩容static final float DEFAULT_LOAD_FACTOR = 0.75f;// 存储键值对对应的Entry数组transient Entry<K,V>[] table;// 键值对的个数transient int size;// 表示一个阈值，当size超过了threshold就会扩容int threshold;// map结构修改和删除次数，累加transient int modCount;
下面看下HashMap的构造方法
// DEFAULT_INITIAL_CAPACITY = 16,DEFAULT_LOAD_FACTOR = 0.75f
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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的指数的值作为初始容量
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 初始化阈值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化Entry数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// 空方法
init();
}
调用HashMap的构造方法时，如果没有指定容量大小和加载因子则会默认创建一个16容量的Entry数组，如果指定了容量大小，则会根据位运算算法找一个大于等于initialCapacity并且是2的指数的值作为初始容量。
下面看下Entry类
// 静态内部类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; // 下一个entry节点
int hash;
/**
* 构造函数，每次都用新的节点指向链表的头结点。新节点作为链表新的头结点
*/
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;
}
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() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K,V> m) {
}
void recordRemoval(HashMap<K,V> m) {
}
}
从Entry的结构可以看出，每次创建一个Entry对象时，会把当前链表上的头结点作为新插入结点的next结点，从jvm知识我们可以知道，对象和数组是存放在堆中的，而且堆是不连续的内存空间，当一个新结点被put进来时，会把当前链表头结点所在的内存引用指向新结点，新结点的next指向以前的头结点，也就是所谓的头插法。
下面看下put方法
/*
* 1. 通过key的hash值确定table下标
* 2. 查找table下标，如果key存在则更新对应的value
* 3. 如果key不存在则调用addEntry()方法
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key); // 重点!!!
int i = indexFor(hash, table.length); // 查找对应的数组下标
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 没有在相同hash值的链表中找到key相同的节点
modCount++;
addEntry(hash, key, value, i); // 在i位置对应的链表上添加一个节点
return null;
}
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) { // 寻找数组0位置对应的链表key值为null的节点，进而更新value值
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); // 在数组0位置对应的链表上添加一个节点
return null;
}
从上面的代码可以看出
- 当key为空时，寻找数组的第0个位置，遍历第0个位置的链表，如果存在key为空的值，则将新的value覆盖旧的value，如果不存在key为空的情况，则在链表的头部添加一个节点。
key不为空时
- 通过相应的位运算算出key的hash值，在根据hash值与数组的长度确定数组table的下标，
- 遍历table[i]上的链表，如果key存在，则覆盖原来的value，不存在则在头部添加新结点
下面看下addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { // 如果数据大小已经超过阈值并且数组对应的bucket不为空，则需要扩容
resize(2 * table.length); // 扩容
hash = (null != key) ? hash(key) : 0; // key为null的时，hash值设为0
bucketIndex = indexFor(hash, table.length); // 确定是哪一个链表（bucket下标）
}
createEntry(hash, key, value, bucketIndex);
}
扩容
如果当前存储的容量大于加载因子乘以数组大小时，则会扩容
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);
boolean rehash = oldAltHashing ^ useAltHashing; // 是否需要重新计算hash值
transfer(newTable, rehash); // 将table的数据转移到新的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) { //将这一个链表遍历添加到新的数组对应的bucket中
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方法
/**
* 得到 key = null 对应的value值
*/
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* 根据key得到对应的value值
*/
public V get(Object key) {
if (key == null)
return getForNullKey(); // 如果key为null，则调用getForNullKey()
Entry<K,V> entry = getEntry(key); // 重点在getEntry()函数
return null == entry ? null : entry.getValue();
}
/**
* 根据key得到对应的Entry对象
*/
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) { // 遍历hash值相同（通过key得到）的那个bucket（链表）
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get方法逻辑
- 当key为空时，遍历数组第0个位置上的链表，如果存在key为空值，则返回这个key对应的value，如果不存在返回空
当key不为空时
- 通过相应的位运算算出key的hash值，在根据hash值与数组的长度确定数组table的下标，
- 遍历tablep[i]上的链表，判断是否存在和key相等的值，存在则返回value，不存在返回空
若有收获，就点个赞吧
0 人点赞
