JDK底层实现源码分析系列(四) HashMap源码分析
“合抱之木 生于毫末 九层之台 起于累土 千里之行 始于足下”
前言
JDK 版本1.7
注:JDK1.8对HashMap进行重构 引入了红黑树 大幅优化HashMap的查找速度
Collection 大家族
LinkedList 继承树
分析
概述
HashMap是基于哈希表,实现Map接口的非同步集合,允许使用Null键和Null值,但是不保证映射的顺序，特别是他不保证集合中的顺序恒久不变
内部维护着一个数组用来存放数据,并且每个数组的元素都是一个单向链表
使用get()获取数据put()存放数据,内部基于hash算法会尽可能的将元素分布均匀在数组中
在查找元素时先计算hash值,因为对同一个对象取hash值返回的都是相同的,用hash值去取模数组的长度就可以快速获取那一条链表
但是求余操作本身也是一种高耗费的操作, 所以HashMap的size会通过算法永远为2的n次方, 可以利用位操作来高效实现求余。要找到数组中当前序号指向的元素，可以通过mod操作，hash mod array length = array index，优化后可以通过：hash & （array length－1） = array index实现。比如一共有16个，3&（16－1）=3，HashMap就是用这个方式来定位数组元素的，这种方式比取模的速度更快。
成员变量
/**
* 默认容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量 1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认加载系数
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* Entry类型的数组 实际上为一个链表
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* map的大小
*/
transient int size;
/**
* HashMap的容量阈值 当threshold="容量*系数"时HashMap就会增加容量
* @serial
*/
int threshold;
/**
* 加载系数
*
* @serial
*/
final float loadFactor;
/**
* 实现fail-fast机制
*/
transient int modCount;
/**
* int最大值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
构造方法
HashMap一共有四个构造方法
/**
* 构造一个空的HashMap使用默认的容量16和默认的加载系数0.75
*
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个空的HashMap使用指定容量,默认的加载系数0.75
*
* @param initialCapacity 指定容量
* @throws IllegalArgumentException
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个空的HashMap使用指定容量和加载系数
*
* @param initialCapacity 指定容量
* @param loadFactor 加载系数
* @throws IllegalArgumentException
*/
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
/**
* 构造一个空的HashMap并把m的数据全部放入
*
* @param m 指定map
* @throws NullPointerException
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
内部类
HashMap的内部类非常多,一共有9个,基本上都是用来遍历集合的,但是有个内部类非常重要Entry他是整个HashMap存储元素的对象,基本上所有的方法都会使用到他
- static class Entry
- private final class EntryIterator extends HashIterator
- private final class EntrySet extends AbstractSet
- private abstract class HashIterator
implements Iterator - private static class Holder
- private final class KeyIterator extends HashIterator
- private final class KeySet extends AbstractSet
- private final class ValueIterator extends HashIterator
- private final class Values extends AbstractCollection
存储
存储元素时调用put(K key, V value)调用addEntry(int hash, K key, V value, int bucketIndex)调用createEntry(int hash, K key, V value, int bucketIndex)进行插入元素
前面所说的取模优化就在put()代码的第13行,下面代码则保证HashMap的容量始终为2的指数幂
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
之所以调用这么多次是因为考虑到让子类继承/实现HashMap可以重写方法实现自己的特点操作
/**
* 在map中插入指定key-value
* 如果之前的map中包含此key,则替换他
*
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold); // 扩容2倍
}
if (key == null)
return putForNullKey(value); // 允许key为null插入value
int hash = hash(key); // 计算hash
int i = indexFor(hash, table.length); // 获取数组的index （hash & (table.length-1);）
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))) { // 存在此key
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue; // 返回替换value
}
}
modCount++;
addEntry(hash, key, value, i); // 无此key 添加元素i为数组索引
return null;
}
/**
* 在指定数组index位置的链表最后插入新节点
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { // 扩容数组
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex); // 真正新建节点的方法
}
/**
* 新建链表节点
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; // 直接定位 获取bucketIndex节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 新建节点放入bucketIndex节点 并让其内部下个节点指向原来的节点
size++; // 容量加1
}
/**
* 根据对象计算hash值 此算法加入了高位计算，防止地位不变，高位变话时造成的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();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
查找数据
/**
* 根据指定的key查找对应的value
* key 可以为null
*
*/
public V get(Object key) {
if (key == null)
return getForNullKey(); // 查找key为null的value
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 根据指定的key查找对应的value
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key); // 计算hash值
for (Entry<K,V> e = table[indexFor(hash, table.length)]; // 变量数组hash位置的链表
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e; // 返回value
}
return null;
}
扩容机制
当HashMap中的元素越来越多的时候,hash的冲突几率也会越来越高，应为数组的长度是固定的16。不进行扩容的话会出现拉链过长的情况导致进行get()数据的时候效率变得非常低,所以HashMap会对数组进行扩容。
这时候HashMap最消耗性能的情况就来了,原数组的全部数据都必须通过transfer()全部重新计算放入新数组
那么什么情况下HashMap才会进行扩容呢？
当HashMap的元素个数超过数组size>size*loadFactor如默认数组大小16,当size > (16*0.07=12)时会将数组扩大至原来的2倍
如果要保证HashMap获取元素的效率建议利用空间换效率,在定义HashMap时将loadFactor设置的小一点,或者直接定义数组的长度,可以明显的提高HashMap的效率
/**
* 设置HashMap的数组长度为两倍并从新计算hash值赋值到新数组中
*/
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];
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);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
fail-fast机制
HashMap也同样实现了fail-fast机制。
遍历方式
初始化数据
private HashMap<Integer, Integer> map = new HashMap<>();
@Before
public void data() {
for (int i = 0; i < 1000; i++) {
map.put(i, i);
}
}
根据entrySet()获取HashMap的key-valueSet集合遍历
@Test
public void entrySet() throws Exception {
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
}
根据keySet()获取HashMap的keySet集合遍历
@Test
public void keySet() throws Exception {
for (Integer key : map.keySet()) {
System.out.println("Key = " + key + ", Value = " + map.get(key));
}
}
根据values()获取HashMap的collection集合遍历
@Test
public void values() throws Exception {
Integer value = null;
Iterator iterator= map.values().iterator();
while (iterator.hasNext()) {
value = (Integer)iterator.next();
System.out.println("Value = " + value);
}
}
总结
要问我阅读HashMap源码的收获,那就是我今天了解一个人
Java界大牛,Collections就是他编写的,并且util.concurrent并发包也是他编写的,非常佩服他
HashMap的扩容操作效率非常非常低,在有大量数据时,初始化HashMap时应估算其大小,避免频繁的扩容
HashMap是非线程安全的,在迭代时如果有其他线程修改值,会触发fail-fast抛出异常
HashMap的计算index值使用的优化取余操作可以应用到其他场景
JDk1.8对于HashMap进行了重构,在单个链表节点大于8时会转换成红黑树来存储,大大提高了大量数据查找时的速度,有时间会去仔细研究下
著作权声明
本文首次发布于 Binux Blog，转载请保留以上链接