通过这篇文章我想回答下列几个问题:
1、HashMap的数据存储结构?
2、存储数据的逻辑?
3、key为null是怎么存储的?
4、怎么根据key取数据的?
5、为什么初始容量必须是2的n次方?
第一个问题:hashmap的数据存储结构
如上图,HashMap由一个数组和一系列的链表组成,存储的数据类型为Entry,一个HashMap的内部类
Entry{hash,key,value,next}。
数组的长度为2的n次方,默认值为16,如果自己设置的值不为2的n次方,则由hashmap自己处理为2的n次方,比如说:
HashMap<String,String> hsm = new HashMap<String,String>(13);
源码如下:
public HashMap(int initialCapacity, float loadFactor) {
。。。。
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1; //实际效果就是2的n次方,当大于initialCapacity后停止循环
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor); //数组扩容临界值
table = new Entry[capacity]; //用计算后的容量初始化数组大小
。。。。
}
传入13,实际数组大小为16。
第二个问题:存储数据的逻辑
以刚才new的HashMap为例,存入 hsm.put("abc", "奥运、亚运都是浮云,有能耐整好春运");
看源码:
public V put(K key, V value) {
if (key == null) //如果key为null,执行特殊存储操作,在问题3中详细回答
return putForNullKey(value);
int hash = hash(key.hashCode()); //再次hash
int i = indexFor(hash, table.length); //查找在数组中的存储位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果数组当前位置不为null,循环数组对应位置的链表
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果存在符合hash和key的条件的entry
V oldValue = e.value;
e.value = value;
e.recordAccess(this); //啥也没干
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); //如果数组当前位置为null,则插入当前entry
return null;
}
查找在数组中的存储位置,源码:
static int indexFor(int h, int length) {
return h & (length-1);
}
如果length为2的n次方,则length-1的二进制为1111...,比如现在(16-1)为1111,经过计算后返回值一定在数组长度范围内。
新增Entry到数组中,源码:
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//new一个新的Entry,并存储在数组的bucketIndex位置上
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//判断数组是否需要扩容
if (size++ >= threshold)
resize(2 * table.length);
}
第三个问题:key为null是怎么存储的
源码:
private V putForNullKey(V value) {
//static final Object NULL_KEY = new Object();
//如果key为null,则用默认的NULL_KEY的hashcode来查找数组中位置
//我还看过不用indexFor(),直接 i=0 的实现,个人认为这种实现更好
int hash = hash(NULL_KEY.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.key == NULL_KEY) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
第四个问题:怎么根据key取数据的
源码:
public V get(Object key) {
if (key == null)//key为null则用特殊方法取value
return getForNullKey();
int hash = hash(key.hashCode());
//根据key的hash值取数组位置
//如果不为null,则循环挂靠在该位置上的链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//如果找到则返回value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
private V getForNullKey() {
//取默认NULL_KEY的hash值,查找数组位置
int hash = hash(NULL_KEY.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> e = table[i];
while (true) {
if (e == null)
return null;
if (e.key == NULL_KEY)
return e.value;
e = e.next;
}
modCount++;
addEntry(hash, (K) NULL_KEY, value, i);
return null;
}
第五个问题:为什么初始容量必须是2的n次方
看源码:
static int indexFor(int h, int length) {
return h & (length-1);
}
所有的存储和查找都是通过这个方法查找数组中的位置的。
举个不是2的n次方的例子,如果长度为13会发生什么情况?
13-1的二进制为: 1100
也就是说hash值以...1100、...1101、 ...1110、 ...1111为结尾的一系列的key都会落到数组[12]的位置上,换句话说这个位置的链表会很长,通过hash散列的效果差,查找效率会低。
- 大小: 29.7 KB
分享到:
相关推荐
hashmap实例 hashmap实例hashmap实例hashmap实例
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
hashmap相关的面试题
HashMap介绍和使用
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized,所以HashMap很快...
HashMap存放.doc
hashmap的底层及源码解析,很适合大家的学习,不要积分。
hashMap排序,hashmap使用还是比较频繁。这时自己写的一个实现hashmap排序的例子
HashMap为什么是线程不安全的?如何解决HashMap的线程不安全问题?
Javascript实现和操作HashMap,压缩包里面有hashmap定义和操作的例子
模拟java中的HashMap类js类对象,可以与js的Array类对象配合使用
Hashmap详解
这个文档“ HashMap详解(通俗易懂)”很好的阐述了hashmap的底层数据结构示意,希望对学习java的人有帮助
HashMap类.rar
HASHMAP缓存.txt HASHMAP缓存.txt
Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序...
记得刚毕业那会准备面试,看过不少面试题,里面有个说出HashMap和HashTable不同的题目,我那会面试的时候也遇到不少次这个问题,还隐约记得当时的回答是这样的: HashTable是比较旧的版本;HashTable是线程安全的,...
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
C语言实现hashMap,包含创建hashMap、插入hashMap、查找hashMap、删除hashMap,已经若干经典的hash函数。文章链接:https://blog.csdn.net/sxf1061700625/article/details/109594495
hashmap dfa关键字替换。 附上main测试明细结果,替换时间 ok ok ok ok 。