Jdk7HashMap源码分析
一、HashMap的成员变量
int DEFAULT_INITIAL_CAPACITY = 16：默认的初始容量为16
int MAXIMUM_CAPACITY = 1 << 30：最大的容量为 2 ^ 30
float DEFAULT_LOAD_FACTOR = 0.75f：默认的加载因子为 0.75f
Entry< K,V>[] table：Entry类型的数组，HashMap用这个来维护内部的数据结构，它的长度由容量决定
int size：HashMap的大小
int threshold：HashMap的极限容量，扩容临界点（容量和加载因子的乘积）
加载因子
- 加载因子是哈希表在元素增加之前可以达到多满的一种尺度，相当于一个阈值。当元素的个数达到阈值时，就会进行扩容。它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。
- 对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，加载因子是表示Hsah表中元素的填满的程度.若加载因子越大,填满的元素越多,好处是,空间利用率高了,但冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了,但空间浪费多了.冲突的机会越大,则查找的成本越高.反之,查找的成本越小
- 因而,查找时间就越小,因此,必须在”冲突的机会”与”空间利用率”之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的”时-空”矛盾的平衡与折衷.
4.系统默认负载因子为0.75，一般情况下我们是无需修改的。
5.当哈希表中的数量超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
二、HashMap的数据结构
我们知道在Java中最常用的两种结构是数组和模拟指针(引用)，几乎所有的数据结构都可以利用这两种来组合实现，HashMap也是如此。实际上HashMap是一个“链表散列”，如下是它数据结构：
从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。下面为HashMap构造函数的源码：
//无参构造器
public HashMap() {
//默认初始容量大小为16,默认的加载因子为0.75f
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
} public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能超过1073741824
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子不能小于等于0,或者加载因子不能是非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//设置加载因子
this.loadFactor = loadFactor;
//设置临界值
threshold = initialCapacity;
//伪构造,里面没有代码
init();
}put()方法代码
public V put(K key, V value) {
//先判断哈希表是否为空,第一次put的话肯定是为空的，
if (table == EMPTY_TABLE) {
// roundUpToPowerOf2方法的作用是将构造器传入的容量初始化大小
//转成最接近2的n字方值,为什么要2的n字方,下面会提到
int capacity = roundUpToPowerOf2(threshold);
//临界值是加载因子*容量大小
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//创建一个Entry数组
table = new Entry[capacity];
//initHashSeedAsNeeded方法的作用:找到与该实例的一个哈希掩码值,使哈希碰撞几率更为小.里
//面会生成一个hashSeed，将会在生成哈希值里面可能会用到。
initHashSeedAsNeeded(capacity);
}
//如果key为null
if (key == null)
//这个方法下面讲解
return putForNullKey(value);
//计算key的哈希值
int hash = hash(key);
//计算改哈希值在哈希表的下标
int i = indexFor(hash, table.length);
//如果刚刚计算出来的下标在哈希表里面为空的话，将不会进入循环
//不为空将遍历table[i]的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该链表上是否有相同的哈希值和相同的地址值,或者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++;
//这个方法下面讲解
addEntry(hash, key, value, i);
return null;
}- 如果为null，则调用putForNullKey：这就是为什么HashMap可以用null作为键的原因，来看看HashMap是如何处理null键的：
private V putForNullKey(V value) {
//查找哈希表中0索引的位置，是否不为空，如果不为空，则遍历0索引的链表
//查找key==null的键值，覆盖并返回旧值。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//将null的键放入哈希表0索引的位置
addEntry(0, null, value, 0);
return null;
}3.添加新结点的方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果结点个数大于或等于临界值和该哈希表指定的索引位置不为null
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容会在重点讲解
resize(2 * table.length);
//这一步就是对null的处理，如果key为null，hash值为0，
//也就是会插入到哈希表的表头table[0]的位置
hash = (null != key) ? hash(key) : 0;
//因为扩容了，需要重新计算哈希表的位置
bucketIndex = indexFor(hash, table.length);
}
//创建Entry结点的操作
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//查找出指定索引的结点对象，目的：形成一个链表
Entry<K,V> e = table[bucketIndex];
//第一个参数书哈希值，第二个是key值，第三个是value值
//第四个哈希表指定索引结点的对象，这样就形成了一个单链链表了。
//为什么要放在链表头，因为好像作者说后面放进去的结点会更大几率使用到。欢迎纠错。
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}5.扩容
void resize(int newCapacity) {
//引用扩容前的Entry数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果扩容前的数组大小如果已经达到最大(2^30)了
//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//创建一个新的哈希表
Entry[] newTable = new Entry[newCapacity];
//将当前所有的哈希表数据复制到新的哈希表
transfer(newTable, initHashSeedAsNeeded(newCapacity));
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);
//第一次循环的newTable[i]为空，赋值给当前结点的下一个元素，
//下面有图会讲解这句代码的含义
e.next = newTable[i];
//将结点赋值到新的哈希表
newTable[i] = e;
e = next;
}
}
}
get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//key为null的处理方法
private V getForNullKey() {
if (size == 0) {
return null;
}
//因为key为null添加的时候是放在哈希表索引0的位置的。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//找到key为null，则终止循环，返回值
if (e.key == null)
return e.value;
}
return null;
}
//获取值
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//计算key的哈希值
int hash = (key == null) ? 0 : hash(key);
//table[indexFor(hash, table.length）这个方法的目的是找到对应的链表，开始遍历
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;
}remove方法
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//判断是在数组下标处还是在数组的单向链表上
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//如果走到这一步，则说明该元素在单向链表上
prev = e;
e = next;
}
return e;
}迭代器
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // 记录索引
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
//找到在数组里第一个元素
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
//如果在这个索引上没有单向链表的话，
if ((next = e.next) == null) {
Entry[] t = table;
//向下个索引查找不为null的元素
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年04月18日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录