正文
数据结构
。
![]()
![]()
三、数据结构
我们知道在Java中最常用的两种结构是数组和模拟指针(引用)，几乎所有的数据结构都可以利用这两种来组合实现，HashMap也是如此。实际上HashMap是一个“链表散列”，如下是它数据结构：
从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。下面为HashMap构造函数的源码：
public HashMap(int initialCapacity, float loadFactor) { //初始容量不能 if (initialCapacity + initialCapacity); //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; //负载因子不能 if (loadFactor + loadFactor); // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
int capacity = 1; while (capacity capacity this.loadFactor = loadFactor; //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
threshold = (int) (capacity * loadFactor); //初始化table数组
table = new Entry[capacity];
init();
}
从源码中可以看出，每次新建一个HashMap时，都会初始化一个table数组。table数组的元素为Entry节点。
static class Entry implements Map.Entry { final K key;
V value;
Entry next; final int hash; /**
* Creates new entry. */
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}
其中Entry为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，这是非常重要的，正是由于Entry才构成了table数组的项为链表。
上面简单分析了HashMap的数据结构，下面将探讨HashMap是如何实现快速存取的。
![]()
![]()
四、存储实现：put(key,vlaue)
首先我们先看源码
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 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;
}
