详解hashmap内部实现原理
内部数据结构
我要评论
static class entry<k,v> implements map.entry<k,v> {
final k key;
v value;
entry<k,v> next;
int hash;
从上面的数据结构定义可以看出，hashmap存元素的是一组键值对的链表，以什么形式存储呢
transient entry<k,v>[] table = (entry<k,v>[]) empty_table;
可以看出，是以数组形式储存，好的，现在我们知道，hashmap是以数组形式存储，每个数组里面是一个键值对，这个键值对还可以链接到下个键值对。如下图所示:
hashmap的添加
public v put(k key, v value) {
if (table == empty_table) {
inflatetable(threshold);
}
if (key == null)
return putfornullkey(value);
int hash = hash(key);
int i = indexfor(hash, table.length);
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;
}
}
modcount++;
addentry(hash, key, value, i);
return null;
}
这里可以看出，hashmap的添加，首先根据一个entry的hash属性去查找相应的table元素i，然后看这个位置是否有元素存在，如果没有，直接放入，如果有，遍历此次链表，加到表尾
删除
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;
}
删除的话，还是先根据hash在table数组中查找，然后再根据equals在链表中进行查找，这个也是为什么hashmap和hashset等以hash方式进行存储的数据结构要求实现两个方法hashcode和equalsd的原因
学过hash的人都知道，hash表的性能和hash冲突的发生次数有很大关系，但有不能申请过长的table表浪费空间，所以这里有了我们的resize函数
扩容机制
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);
}
这个方法会在put的时候调用,上面put的时候先调用 addentry(hash, key, value, i);方法，然后看addentry方法
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);
}
上面可以看出那么 hashmap 当 hashmap 中的元素个数超过数组大小 *loadfactor 时，就会进行数组扩容，loadfactor 的默认值为 0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为 16，那么当 hashmap 中元素个数超过 16*0.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位 置，而这是一个非常消耗性能的操作，所以如果我们已经预知 hashmap 中元素的个数，那么预设元素的个数能够有效的提高 hashmap 的性能。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
【奥鹏作业答案库网】大工20春《应用统计》在线作业1【奥鹏作业答案】
网友评论