50279

对HashMap的理解

关于HashMap的几个常识:

(1)HashMap是一个用于存储Key-Value键值对的集合,每一个键值对也叫做Entry。这些个键值对(Entry)分散存储在一个数组当中,这个数组就是HashMap的主干。

(2)HashMap数组每一个元素的初始值都是Null。允许Null键和Null值,不保证有序。

(3)HashMap的默认初始长度是16,并且每次自动扩展或是手动初始化时,长度必须是2的幂。之所以选择16,是为了服务于key映射到index的Hash算法。

(4)HashMap中有两个很重要的参数,容量(Capacity)和负载因子(Load factor)。当bucket填充的数目(即hashmap中元素的个数)大于capacity*load factor时就需要调整buckets的数目为当前的2倍。

<h4>数据结构</h4>

HashMap的底层数据结果是数据+链表(存在的意思就是为了解决哈希冲突),jdk1.8之后的数据结构是数组+链表+红黑树(在链表>=8个元素的时候,会变为红黑树的结构)

(1)Put方法的原理

调用Put方法的时候发生了什么呢?

比如调用 hashMap.put("apple", 0) ,插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置(index): 

index = Hash(“apple”)

<p class="ztext-empty-paragraph">HashMap数组的每一个元素不止是一个Entry对象,也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时,只需要插入到对应的链表即可,需要注意的是,新来的Entry节点插入链表时,使用的是“头插法”。(之所以放到头部,是因为HashMap的发明者认为后插入的元素被查找的概率更大)

<p class="ztext-empty-paragraph"> 

对key的hashCode()做hash,然后再计算index;
如果没碰撞直接放到bucket里;
如果碰撞了,以链表的形式存在buckets后;
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
如果节点已经存在就替换old value(保证key的唯一性);
如果bucket满了(超过load factor*current capacity),就要resize。

<p class="ztext-empty-paragraph">(2)Get方法的原理

bucket里的第一个节点,直接命中;
如果有冲突,则通过key.equals(k)去查找对应的entry
若为树,则在树中通过key.equals(k)查找,O(logn);
若为链表,则在链表中通过key.equals(k)查找,O(n)。

来源:博客园

作者:哦克Oak

链接:https://www.cnblogs.com/pzyin/p/11426071.html

Recommend