一、全文介绍
1、HashMap数据结构介绍
2、数据的插入过程以及查找过程
3、HashMap初始大小计算以及重要属性介绍
4、常会被问到的问题。
二、HashMap数据结构
HashMap是由数组和链表结构组成。这种结构有两个好处：1、查找比纯链表快，插入删除比纯数组快；2、可以解决HashCode冲突。
hashmap.png
三、数据的插入过程以及查找过程（jdk1.7）
1、插入数据过程文字描述
1.1、判断存储Table是否为空，如果为空初始化，然后判断key是否为空，如果为空判断table[0]是否有值，无值插入
数据，有值替换value。
1.2、key不为空，则根据key计算数组中的index（先计算key的hash值，然后与table的表的长度减1做与运算）。
1.3、找数组中对应位置有没有存储数据，如果没有存入，如果有遍历数组上的所有数据，查看有没有数据hash值相
等key相等的。如果有则替换。
1.4、如果没有找到则添加数据，首先会查看是否需要增容，如果需要增容，并且重新计算index值，如果不需要的话
生成一个实体，并且存放在表头。
2、插入数据过程流程图描述(为了避免流程图过于复杂去除了key为null的过程)
HashMap插入过程.png
3、获取数据的过程文字描述
3.1、判断key是否为空，为空时查看table[0]是否有Entry,有则返回，没有则返会null
3.2 、key不为空，根据key计算相应的index 值，遍历相应的链表找到key相等的Entry返回
4、获取数据流程图（较为简单，省略）
四、HashMap初始大小以及重要成员变量介绍
1、重要属性
int threshold; // table所能容纳的key-value对极限 （table.length(数组)＊loadFactor）
final float loadFactor; // 负载因子(1个系数可以大于1)
int modCount; //HashMap内部结构发生变化的次数,替换不增加
int size; //实际存在的键值对数量
2、常见参数初始大小
Table长度初始大小16
loadFactor负载因子为0.75
五、常被问到的问题
1、为什么table的长度通常为2的倍数
为2的倍数与index的计算有关，能够减少index的冲突。
table 长度为2的倍数那 长度减1 后用二进制表示就全为1；这样做与运算取决于Hashcode的后几位
table length 为16
0100 &1111=4
0110&1111=6
0111&1111=7
table length 为6
0100&0101=4
0110&0101=4
0111&0101=5
2、怎么扩容
2.1、新申请两倍的数组大小
2.2、重新计算index，并放入新的数组中
3、假设hashcode冲突，100个数据需要将HashMap初始为多大比较合适
这个主要考虑table的长度和负载因子及扩容
table长度为2的倍数，那128比较合适但128*0.75=96。小于100因此还是需要扩容。所以应该取256。
4、key值和value值是否可以为null
key和value值都可以为null
网友评论