HashMap源码分析(一)
2020-01-20 16:03:03来源:博客园 阅读 ()
HashMap源码分析(一)
基于JDK1.7 HashMap源码分析
概述
HashMap是存放键值对的集合,数据结构如下:
- table被称为桶,大小(capacity)始终为2的幂,当发生扩容时,map容量扩大为两倍
- HashMap采用拉链法解决Hash冲突,发生冲突时,新元素采用头插法插入到对应桶的链表中
HashMap有几个重要字段:
- size:HashMap键值对的数量
- capacity:桶数量,即table.length,默认16
- loadFactor:负载因子,度量负载程度,基于时间和空间的权衡,默认0.75
- threshold:阈值,当
size>=threshold
将发生扩容,threshold=capacity * loadFactor
。
JDK1.7 源码分析
属性
/**
* 默认初始容量 (必须是2的幂)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 空表
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* hash table
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* 键值对数目
*/
transient int size;
/**
* 阈值 (等于capacity * load factor).
*/
int threshold;
/**
* 负载因子
*/
final float loadFactor;
/**
* HashMap 结构性变化次数
* 用于快速失败
*/
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
构造函数
/**
* 构造函数
*/
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();
}
/**
* 构造函数,默认负载因子
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数,默认初始容量和负载因子
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数,通过map构造
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//初始化table
inflateTable(threshold);
//赋值到新map
putAllForCreate(m);
}
Hash函数
Hash函数是获取对象处理后的hash值,为了让hash值散列更加均匀,减少碰撞,
扰动函数(Hash函数)对hashCode进行一些位运算。
/**
* 扰动函数(减少碰撞几率)
*/
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);
}
确定桶下标
确定桶下标的常用方式:hash % table.length
,为了提高运行效率,
用位运算替代模运算。
能够这样做的前提,table.length必须是2的幂,这也是table的长度始终是2的幂的原因之一。
/**
* 确定桶下标
*/
static int indexFor(int h, int length) {
// length必须是2的幂
return h & (length-1);
}
Put操作
put
注意HashMap的值比较方法:e.hash == hash && ((k = e.key) == key || key.equals(k))
public V put(K key, V value) {
//空数组,则分配内存空间(延迟初始化)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//null键处理
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
//若key已经存在,则替换
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;
}
}
//key不存在,则新增
modCount++;
addEntry(hash, key, value, i);
return null;
}
inflateTable
HashMap的空间分配不是在构造函数中完成的,而是采用延迟初始化
的方式,当第一个元素put时,才会进行空间分配。
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//分配空间
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
putForNullKey
HashMap与HashTable的区别其中一点便是,前者key value都可以为null,后者都不能为null。
为null的键存放在table[0]中,即第一个桶。
/**
* null键插入
*/
private V putForNullKey(V value) {
/**
* null键存放在table[0]中(table[0]中不全是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++;
//添加Entry
addEntry(0, null, value, 0);
return null;
}
扩容
当向HashMap添加一个不存在的key时(即size将增大),添加之前扩容检查。
扩容触发条件为:数量达到阈值并且发生Hash冲突。
扩容本质上,新建一个数组,使用头插法将旧map的元素拷贝到新map中。
addEntry
添加键值对时,检验是否需要扩容。扩容的条件:数量达到阈值并且发生Hash冲突
/**
* 添加Entry
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//扩容条件:size大于阈值并且发生碰撞
if ((size >= threshold) && (null != table[bucketIndex])) {
//容量扩为2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//确定新桶下标
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
resize
当扩容时:
- 容量已经达到最大值,仅调整阈值
- 容量未达到最大值,扩大table空间,并将旧map数据添加到新map中
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);
}
transfer
实际上,扩容本质是新建一个数组,然后在把数据复制过去,复制过程中,元素需要重新定位桶标
所以,多次扩容对性能影响很大
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;
}
}
}
createEntry
从Entry
的构造函数中next = n;
可以看出元素插入链表使用的头插法。
void createEntry(int hash, K key, V value, int bucketIndex) {
//table下标中第一个元素
Entry<K,V> e = table[bucketIndex];
/**
* 构造方法中 next = e; 可见 使用的头插法插入到链表中
*/
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
get操作
/**
* 获取值
* 返回null有两种可能:1.不存在对应的键值对;2.存在key,但值为null
* 可以通过 {@link #containsKey containsKey} 进行区分
*/
public V get(Object key) {
if (key == null)
//获取key为null的值
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
//可见,null的key存放在table[0]中,即第一个桶中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
//确定桶下标后,遍历链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判断key是否相等。先比较的hash值,再比较的地址,最后比较equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
原文链接:https://www.cnblogs.com/smtx/p/12219679.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:五、JVM之堆内存
- 你说研究过Spring里面的源码,循环依赖你会么? 2020-06-09
- 通俗理解spring源码(六)—— 默认标签(import、alias、be 2020-06-07
- HashMap:源代码(构造方法、put、resize、get、remove、rep 2020-06-04
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- HashMap1.7和1.8,红黑树原理! 2020-06-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash