HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
下面分五部分简单介绍:
一、HashMap构造方式
数组+模拟指针(引用)
所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。
HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
table是数组,数组中每个元素是Entry,即链表
二、如何存放数据
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
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;
}
}
// 如果i索引处的Entry为null,表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
首先,判断key是否为空,是的话调用putForNullKey;
其次,对key.hashcode()进行hash()的映射;
再次,根据indexFor()找到数组下标i
再再次,如果table[i]不为空,遍历链接,确定是否有相同的key;有则替换value,返回oldvalue;
最后,添加entry到table[i]
三、如何取数据
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.value;
}
return null;
}
首先,判断是否为,是的话调用getForNullKey;
其次,计算hash、下标
再次,遍历查找;找到,返回value;
最后,没找到,返回null
四、哈希函数
上面的代码中,重点在于hash(key.hashCode())
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
据说加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。但不懂。
>>>的意思为,右移,高位补0
>>的意思为,右移,高位补符号位
如何根据hash()值,取数组下标
static int indexFor(int h, int length) {
return h & (length-1);
}
HashMap的大小为2^n,length-1的二进制,相应位数全为1,使得数据可以均匀分布
采用&操作,比%速度快
Java源码中,HashMap的最大值为1<<30,即2^30
int的最大值为2^31-1,不采用此的原因即为HashMap的大小为2^n
五、HashMap的resize(rehash)
元素多了,需要扩容;ArrayList也是如此。
当HashMap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。
默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
六、疑惑
hash函数的设计,不懂,待学习,求指点
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
修改转自:http://zhangshixi.iteye.com/blog/672697
- 大小: 13.5 KB
分享到:
相关推荐
hashmap的底层及源码解析,很适合大家的学习,不要积分。
hashmap实现原理.pdf
基于HashMap的用户标签处理兼Java中HashMap实现原理研究
主要介绍了深入解析java HashMap实现原理的相关资料,需要的朋友可以参考下
主要介绍了Jdk1.8 HashMap实现原理详细介绍的相关资料,需要的朋友可以参考下
。
。
主要介绍了java 中HashMap实现原理深入理解的相关资料,需要的朋友可以参考下
Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧
HashMap是基于哈希表的Map接口实现,提供了所有可选的映射操作,并允许使用null值和null建,不同步且不保证映射顺序。本文将记录一下研究HashMap实现原理。
HashMap底层原理.md
主要介绍了Java HashMap实现原理的分析,帮助大家更好的理解和使用Java,感兴趣的朋友可以了解下
HashMap底层原理
HashMap的实现原理
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
HashMap底层实现原理共6页.pdf.zip
NULL 博文链接:https://zhangshixi.iteye.com/blog/672697