在Java集合类中最常用的除了ArrayList外就是HashMap了本文尽自己所能尽量详细的解释HashMap的源码一山还有一山高有不足之处请之处定感谢指定并及时修正
在看HashMap源码之前先复习一下数据结构
Java最基本的数据结构有数组和链表数组的特点是空间连续(大小固定)寻址迅速但是插入和删除时需要移动元素所以查询快增加删除慢链表恰好相反可动态增加或减少空间以适应新增和删除元素但查找时只能顺着一个个节点查找所以增加删除快查找慢有没有一种结构综合了数组和链表的优点呢?当然有那就是哈希表(虽说是综合优点但实际上查找肯定没有数组快插入删除没有链表快一种折中的方式吧)一般采用拉链法实现哈希表哈希表?拉链法?可能一下想不起来不过放张图就了然了
(图片google来的好多都用了文章用了这张图了不知道出处了就没申明作者了)
学计算机的肯定学过这玩意儿也不需要解释都懂的
铺垫了这么多又是数组又是链表还有哈希表拉链法该入正题了我们什么时候用到了这些内容具体它是怎么实现的?
其实我们一直在用(别告诉我你没用过HashMap什么的)可能你一直没去深究没看到它如何实现的所以一直没感受到这里主要分析HashMap的源码就不再多扯其他的了
HashMap继承自AbstractMap实现了Map接口(这些内容可以参考《Java集合类》)来看类的定义
public class HashMap extends AbstractMap implements Map Cloneable Serializable
Map接口定义了所有Map子类必须实现的方法Map接口中还定义了一个内部接口Entry(为什么要弄成内部接口?改天还要学习学习)Entry将在后面有详细的介绍
AbstractMap也实现了Map接口并且提供了两个实现Entry的内部类SimpleEntry和SimpleImmutableEntry
定义了接口接口中又有内部接口然后有搞了个抽象类实现接口抽象类里面又搞了两个内部类实现接口的内部接口有没有点绕为什么搞成这样呢?先不管了先看HashMap吧
HashMap中定义的属性(应该都能看明白不过还是解释一下)
/**
* 默认的初始容量必须是的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = ;
/**
* 最大容量(必须是的幂且小于的次方传入容量过大将被这个值替换)
*/
static final int MAXIMUM_CAPACITY = << ;
/**
* 默认装载因子这个后面会做解释
*/
static final float DEFAULT_LOAD_FACTOR = f;
/**
* 存储数据的Entry数组长度是的幂看到数组的内容了接着看数组中存的内容就明白为什么博文开头先复习数据结构了
*/
transient Entry[] table;
/**
* map中保存的键值对的数量
*/
transient int size;
/**
* 需要调整大小的极限值(容量*装载因子)
*/
int threshold;
/**
*装载因子
*/
final float loadFactor;
/**
* map结构被改变的次数
*/
transient volatile int modCount;
接着是HashMap的构造方法
/**
*使用默认的容量及装载因子构造一个空的HashMap
*/
public HashMap() {
thisloadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//计算下次需要调整大小的极限值
table = new Entry[DEFAULT_INITIAL_CAPACITY];//根据默认容量()初始化table
init();
}
/**
* 根据给定的初始容量的装载因子创建一个空的HashMap
* 初始容量小于或装载因子小于等于将报异常
*/
public HashMap(int initialCapacity float loadFactor) {
if (initialCapacity < )
throw new IllegalArgumentException(Illegal initial capacity: +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//调整最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= || FloatisNaN(loadFactor))
throw new IllegalArgumentException(Illegal load factor: +
loadFactor);
int capacity = ;
//设置capacity为大于initialCapacity且是的幂的最小值
while (capacity < initialCapacity)
capacity <<= ;
thisloadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
/**
*根据指定容量创建一个空的HashMap
*/
public HashMap(int initialCapacity) {
this(initialCapacity DEFAULT_LOAD_FACTOR);//调用上面的构造方法容量为指定的容量装载因子是默认值
}
/**
*通过传入的map创建一个HashMap容量为默认容量()和(mapzise()/DEFAULT_LOAD_FACTORY)+的较大者装载因子为默认值
*/
public HashMap(Map m) {
this(Mathmax((int) (msize() / DEFAULT_LOAD_FACTOR) +
DEFAULT_INITIAL_CAPACITY) DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
上面的构造方法中调用到了init()方法最后一个方法还调用了putAllForCreate(Map m)init方法是一个空方法里面没有任何内容putAllForCreate看方法名就是创建的时候将传入的map全部放入新创建的对象中该方法中还涉及到其他方法将在后面介绍
先看初始化table时均使用了Entry这是HashMap的一个内部类实现了Map接口的内部接口Entry
下面给出MapEntry接口及HashMapEntry类的内容
MapEntry接口定义的方法
K getKey();//获取Key
V getValue();//获取Value
V setValue();//设置Value至于具体返回什么要看具体实现
boolean equals(Object o);//定义equals方法用于判断两个Entry是否相同
int hashCode();//定义获取hashCode的方法
HashMapEntry类的具体实现
static class Entry implements MapEntry {
final K key;
V value;
Entry next;//对下一个节点的引用(看到链表的内容结合定义的Entry数组是不是想到了哈希表的拉链法实现?!)
final int hash;//哈希值
Entry(int h K k V v Entry 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;//返回的是之前的Value
}
public final boolean equals(Object o) {
if (!(o instanceof MapEntry))//先判断类型是否一致
return false;
MapEntry e = (MapEntry)o;
Object k = getKey();
Object k = egetKey();
// Key相等且Value相等则两个Entry相等
if (k == k || (k != null && kequals(k))) {
Object v = getValue();
Object v = egetValue();
if (v == v || (v != null && vequals(v)))
return true;
}
return false;
}
// hashCode是Key的hashCode和Value的hashCode的异或的结果
public final int hashCode() {
return (key==null ? : keyhashCode()) ^
(value==null ? : valuehashCode());
}
// 重写toString方法是输出更清晰
public final String toString() {
return getKey() + = + getValue();
}
/**
*当调用put(kv)方法存入键值对时如果k已经存在则该方法被调用(为什么没有内容?)
*/
void recordAccess(HashMap m) {
}
/**
* 当Entry被从HashMap中移除时被调用(为什么没有内容?)
*/
void recordRemoval(HashMap m) {
}
}
看完属性和构造方法接着看HashMap中的其他方法一个个分析从最常用的put和get说起吧
put()
public V put(K key V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(keyhashCode());
int i = indexFor(hash tablelength);
for (Entry e = table[i]; e != null; e = enext) {
Object k;
if (ehash == hash && ((k = ekey) == key || keyequals(k))) {
V oldValue = evalue;
evalue = value;
erecordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash key value i);
return null;
}
当存入的key是null的时候将调用putForNUllKey方法暂时将这段逻辑放一边看key不为null的情况先调用了hash(int h)方法获取了一个hash值
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately at default load factor)
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
这个方法的主要作用是防止质量较差的哈希函数带来过多的沖突(碰撞)问题Java中int值占个字节即位根据这位值进行移位异或运算得到一个值
static int indexFor(int h int length) {
return h & (length);
}
indexFor返回hash值和table数组长度减的与运算结果为什么使用的是length?应为这样可以保证结果的最大值是length不会产生数组越界问题
获取索引位置之后做了什么?探测table[i]所在的链表所发现key值与传入的key值相同的对象则替换并返回oldValue若找不到则通过addEntry(hashkeyvaluei)添加新的对象来看addEntry(hashkeyvaluei)方法
void addEntry(int hash K key V value int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash key value e);
if (size++ >= threshold)
resize( * tablelength);
}
这就是在一个链表头部插入一个节点的过程获取table[i]的对象e将table[i]的对象修改为新增对象让新增对象的next指向e之后判断size是否到达了需要扩充table数组容量的界限并让size自增如果达到了则调用resize(int capacity)方法将数组容量拓展为原来的两倍
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTablelength;
// 这个if块表明如果容量已经到达允许的最大值即MAXIMUN_CAPACITY则不再拓展容量而将装载拓展的界限值设为计算机允许的最大值
// 不会再触发resize方法而是不断的向map中添加内容即table数组中的链表可以不断变长但数组长度不再改变
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = IntegerMAX_VALUE;
return;
}
// 创建新数组容量为指定的容量
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
// 设置下一次需要调整数组大小的界限
threshold = (int)(newCapacity * loadFactor);
}
结合上面给出的注释调整数组容量的内容仅剩下将原table中的内容复制到newTable中并将newTable返回给原table即上面代码中的transfer(newTable);table = newTable;来看transfer(Entry[] newTable)方法
void transfer(Entry[] newTable) {
// 保留原数组的引用到src中
Entry[] src = table;
// 新容量使新数组的长度
int newCapacity = newTablelength;
// 遍历原数组
for (int j = ; j < srclength; j++) {
// 获取元素e
Entry e = src[j];
if (e != null) {
// 将原数组中的元素置为null
src[j] = null;
// 遍历原数组中j位置指向的链表
do {
Entry next = enext;
// 根据新的容量计算e在新数组中的位置
int i = indexFor(ehash newCapacity);
// 将e插入到newTable[i]指向的链表的头部
enext = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
从上面的代码可以看出HashMap之所以不能保持元素的顺序有以下几点原因第一插入元素的时候对元素进行哈希处理不同元素分配到table的不同位置;第二容量拓展的时候又进行了hash处理;第三复制原表内容的时候链表被倒置
一个put方法带出了这么多内容接着看看putAll吧
public void putAll(Map m) {
int numKeysToBeAdded = msize();
if (numKeysToBeAdded == )
return;
// 为什么判断条件是numKeysToBeAdded不是(numKeysToBeAdded+tablelength)>threshold???
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + );
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = tablelength;
while (newCapacity < targetCapacity)
newCapacity <<= ;
if (newCapacity > tablelength)
resize(newCapacity);
}
for (Iterator> i = mentrySet(erator(); ihasNext(); ) {
MapEntry e = inext();
put(egetKey() egetValue());
}
}
先回答上面的问题为什么判断条件是numKeysToBeAdded不是(numKeysToBeAdded+tablelength)>threshold???
这是一种保守的做法明显地我们应该在(numKeysToBeAdded+tablelength)>threshold的时候去拓展容量但是考虑到将被添加的元素可能会有Key与原本存在的Key相同的情况所以采用保守的做法避免拓展到过大的容量
接着是遍历m中的内容然后调用put方法将元素添加到table数组中
遍历的时候涉及到了entrySet方法这个方法定义在Map接口中HashMap中也有实现后面会解释HashMap的这个方法其它Map的实现暂不解释
下面介绍在put方法中被调用到的putForNullKey方法
private V putForNullKey(V value) {
for (Entry e = table[]; e != null; e = enext) {
if (ekey == null) {
V oldValue = evalue;
evalue = value;
erecordAccess(this);
return oldValue;
}
}
modCount++;
addEntry( null value );
return null;
}
这是一个私有方法在put方法中被调用它首先遍历table数组如果找到key为null的元素则替换元素值并返回oldValue;否则通过addEntry方法添加元素之后返回null
还记得上面构造方法中调用到的putAllForCreate吗?一口气将put操作的方法看完吧
private void putAllForCreate(Map m) {
for (Iterator> i = mentrySet(erator(); ihasNext(); ) {
MapEntry e = inext();
putForCreate(egetKey() egetValue());
}
}
先将遍历的过程放在一边因为它同样涉及到了entrySet()方法剩下的代码很简单只是调用putForCreate方法逐个元素加入
private void putForCreate(K key V value) {
int hash = (key == null) ? : hash(keyhashCode());
int i = indexFor(hash tablelength);
for (Entry e = table[i]; e != null; e = enext) {
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k)))) {
evalue = value;
return;
}
}
createEntry(hash key value i);
}
该方法先计算需要添加的元素的hash值和在table数组中的索引i接着遍历table[i]的链表若有元素的key值与传入key值相等则替换value结束方法若不存在key值相同的元素则调用createEntry创建并添加元素
void createEntry(int hash K key V value int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash key value e);
size++;
}
这个方法的内容就不解释了上面都解释过
至此所有put相关操作都解释完毕了put之外另一个常用的操作就是get下面就来看get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(keyhashCode());
for (Entry e = table[indexFor(hash tablelength)];
e != null;
e = enext) {
Object k;
if (ehash == hash && ((k = ekey) == key || keyequals(k)))
return evalue;
}
return null;
}
该方法分为key为null和不为null两块先看不为null的情况先获取key的hash值之后通过hash值及tablelength获取key对应的table数组的索引遍历索引的链表所找到key相同的元素则返回元素的value否者返回null不为null的情况调用了getForNullKey()方法
private V getForNullKey() {
for (Entry e = table[]; e != null; e = enext) {
if (ekey == null)
return evalue;
}
return null;
}
这是一个私有方法只在get中被调用该方法判断table[]中的链表是否包含key为null的元素包含则返回value不包含则返回null为什么是遍历table[]的链表?因为key为null的时候获得的hash值都是
添加(put)和获取(get)都结束了接着看如何判断一个元素是否存在
HashMap没有提供判断元素是否存在的方法只提供了判断Key是否存在及Value是否存在的方法分别是containsKey(Object key)containsValue(Object value)
containsKey(Object key)方法很简单只是判断getEntry(key)的结果是否为null是则返回false否返回true
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry getEntry(Object key) {
int hash = (key == null) ? : hash(keyhashCode());
for (Entry e = table[indexFor(hash tablelength)];
e != null;
e = enext) {
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k))))
return e;
}
return null;
}
getEntry(Object key)也没什么内容只是根据key对应的hash值计算在table数组中的索引位置然后遍历该链表判断是否存在相同的key值
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = ; i < tablength ; i++)
for (Entry e = tab[i] ; e != null ; e = enext)
if (valueequals(evalue))
return true;
return false;
}
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = ; i < tablength ; i++)
for (Entry e = tab[i] ; e != null ; e = enext)
if (evalue == null)
return true;
return false;
}
判断一个value是否存在比判断key是否存在还要简单就是遍历所有元素判断是否有相等的值这里分为两种情况处理value为null何不为null的情况但内容差不多只是判断相等的方式不同
这个判断是否存在必须遍历所有元素是一个双重循环的过程因此是比较耗时的操作
接着看HashMap中删除相关的操作有remove(Object key)和clear()两个方法
remove(Object key)
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : evalue);
}
看这个方法removeEntryKey(key)的返回结果应该是被移除的元素如果不存在这个元素则返回为nullremove方法根据removeEntryKey返回的结果e是否为null返回null或evalue
removeEntryForKey(Object key)
final Entry removeEntryForKey(Object key) {
int hash = (key == null) ? : hash(keyhashCode());
int i = indexFor(hash tablelength);
Entry prev = table[i];
Entry e = prev;
while (e != null) {
Entry next = enext;
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k)))) {
modCount++;
size;
if (prev == e)
table[i] = next;
else
prevnext = next;
erecordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
上面的这个过程就是先找到table数组中对应的索引接着就类似于一般的链表的删除操作而且是单向链表删除节点很简单在C语言中就是修改指针这个例子中就是将要删除节点的前一节点的next指向删除被删除节点的next即可
clear()
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = ; i < tablength; i++)
tab[i] = null;
size = ;
}
clear()方法删除HashMap中所有的元素这里就不用一个个删除节点了而是直接将table数组内容都置空这样所有的链表都已经无法访问Java的垃圾回收机制会去处理这些链表table数组置空后修改size为
这里为什么不直接操作table而是通过tab呢?希望有知道的大侠指点一二
主要方法看的差不多了接着看一个上面提到了好几次但是都搁在一边没有分析的方法entrySet()
entrySet()
public Set> entrySet() {
return entrySet();
}
private Set> entrySet() {
Set> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
为什么会有这样的方法只是调用了一下entrySet而且entrySet的名称看着就很奇怪再看entrySet方法中为什么不直接return entrySet!=null?entrySet:(entrySet = new EntrySet)呢?
上面的疑问还没解开但是先看entrySet这个属性吧在文章开头的属性定义中并没有给出这个属性下面先看一下它的定义
private transient Set> entrySet = null;
它是一个内容为MapEntry的Set看看在哪些地方往里面添加了元素
为什么上面的那句话我要把它标成红色?因为这是一个陷阱在看代码的时候我就陷进去了
仔细看EntrySet这个类
private final class EntrySet extends AbstractSet> {
public Iterator> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof MapEntry))
return false;
MapEntry e = (MapEntry) o;
Entry candidate = getEntry(egetKey());
return candidate != null && candidateequals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMapthisclear();
}
}
看到了什么?这个类根本就没属性它只是个代理因为它内部类可以访问外部类的内容debug的时候能看到的属性都是继承或者外部类的属性输出的时候其实也是调用到了父类的toString方法将HashMap中的内容输出了
keySet()
public Set keySet() {
Set ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
是不是和entrySet()方法很像!
private final class KeySet extends AbstractSet {
public Iterator iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMapthisremoveEntryForKey(o) != null;
}
public void clear() {
HashMapthisclear();
}
}
同样是个代理类containsremoveclear方法都是调用的HashMap的方法
values()
public Collection values() {
Collection vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection {
public Iterator iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMapthisclear();
}
}
values()方法也一样是代理只是Values类继承自AbstractCollention类而不是AbstractSet
还有一个重要的内容没有进行说明那就是迭代器HashMap中的entrySet()keySet()values()等方法都使用到了迭代器Iterator的知识其他集合类也有使用到迭代器
