如果你准备面试Java后端方向的工程师,那么HashMap可以说是面试中的重中之重,你去10家公司面试,可能8家公司都会会问道。所以可见HashMap相关的知识点对于我们面试来说有多么重要,接下来就让我们走进HashMap的大门吧!
1.什么是HashMap
HashMap是Java当中一种数据结构,是一个用于存储Key-Value键值对的集合,每一个键值对也叫作Entry实体。
HashMap 数据结构为 数组+链表,其中:链表的节点存储的是一个 Entry 对象,每个Entry 对象存储四个属性(hash,key,value,next)。
2.HashMap存储原理
首先,初始化 HashMap,提供了有参构造和无参构造,具体的关于HashMap的构造函数如下所示,无参构造中,容器默认的数组大小 initialCapacity 为 16,且数组大小只允许为2的整数次幂,默认加载因子loadFactor 为0.75。容器的阈值为 initialCapacity * loadFactor,默认情况下阈值为 16 * 0.75 = 12。当存储在HashMap集合中的Entry数目大于容器的阈值,则容器需要扩容,使其容量变为原来的两倍。
HashMap();//构造一个具有默认 初始容量 (16) 和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity);//构造一个带 指定初始容量 和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor);//构造一个带指定初始容量和加载因子的空 HashMap。
接下来,我们对HashMap的put方法进行探索!
第一步:通过 HashMap 自己提供的hash 算法算出当前 key 对应的hash 值;
int hash=key.hashCode();
第二步:通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置;
static int indexFor(int hash, int length) {
// hash 为key 的 hash值;length 是数组长度
return hash & (length-1);
}
第三步:判断size 是否已经达到了当前阈值,如果没有,继续;如果已经达到阈值,则先进行数组扩容,将数组长度扩容为原来的2倍。
请注意:size 是当前容器中已有 Entry 的数量,不是全部Entry所占数组空间的大小。
第四步:将当前对应的 hash,key,value封装成一个 Entry,去数组中查找当前位置有没有元素,如果没有,放在这个位置上;如果此位置上已经存在链表,那么遍历链表,如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true,则把原来节点上的value 返回,将当前新的 value替换掉原来的value,如果遍历完链表,没有找到key 与当前 key equals为 true的,就把刚才封装的新的 Entry插入到对应链表的尾部,即当前链表的最后一个元素。(注意:在JDK1.8之前,是插入到链表的头部,即采用的是头插法)
OK!到目前为止,我们已经将当前的 key-value 存储到了容器中。
在put方法的实现原理中,就出现了一个经典的面试题!
即:为什么 HashMap使用这种方式(hash & (length-1))计算在数组中位置呢?
在数据结构中,简单的Hash函数只需要取模就可以了。而HashMap用&运算主要是提升计算性能。那么这又会带来一个新的问题,为什么&运算要与length-1呢?回看HashMap初始化容量大小的时候,数组长度length必须是2的整数次幂(如果手动传参为n,HashMap会自动转换长度为距离n最近的2的整数次幂)。只有这样,hash&(length-1)的值才会和hash%length计算的结果保持一致。这就是它的原因所在。采用这种方式,即提升了CPU计算性能,也保证了数据在Hash表中的均匀分布。
读者如果不理解其中的原理,可以自行编写代码测试一下:
public static void main(String[] args) {
int length = 16; //定义数组长度为2的整次幂,2^4
//定义key,并计算k的hash值
String k = "China";
int hash = k.hashCode();
//分别使用两种方式计算在数组中的位置
int index1 = hash % length;
int index2 = hash & (length - 1);
//验证结果
System.out.println(index1 == index2);
//结果为 true
}
于此同时,这里还可以引申出另外一个问题?
即:为什么hashmap的容量是2的幂次方?
1.计算机内&运算速度较快,至少比%速度要快;
2.当length为2的整数次幂时,会满足一个公式:(length-1)&hash=hash%length;
3.采用(n-1)&hash来计算索引位置时,当n为2的幂次方的时候,n-1转换为二进制时可以保证低位全都是1,所以元素存储在哈希表中的位置完全取决于其hash值,而Java中的hashCode()方法能够满足元素的均匀分布,因此就会导致元素索引分布均匀。文章来源:https://www.toymoban.com/news/detail-568183.html
3.HashMap和HashTable 的异同
区别 | HashMap | HashTable |
---|---|---|
是否线程安全 | 否 | 是 |
数据结构 | 数组+链表+红黑树 | 数组+链表 |
是否允许键值为null | 是 | 否 |
定位算法 | 采用的是&运算 | 采用的是%运算 |
扩容算法 | 容量扩充为原来的2倍 | 容量扩充为原来的2倍+1 |
链表插入 | 将新节点插入到链表的尾部 | 将新节点插入到链表的头部 |
继承的类 | 继承abstractMap抽象类 | 继承Dictionary抽象类 |
实现的接口 | 实现Map接口 | 实现Map接口 |
默认容量大小 | 16 | 11 |
默认负载因子 | 0.75 | 0.75 |
4.HashMap采用的API
文章来源地址https://www.toymoban.com/news/detail-568183.html
package a;
import java.util.HashMap;
import java.util.Map.Entry;
public class Main{
public static void main(String[] args){
HashMap<String,Integer> mp = new HashMap<String,Integer>();
mp.put("one",1); //存放键值对
System.out.println(mp.get("one")); //通过键取值,输出 1
System.out.println(mp.get("1")); //通过键取值,不存在,输出 null
System.out.println("====================");
System.out.println(mp.containsKey("one")); //HashMap中是否包含该键,输出true
System.out.println(mp.containsKey("two")); //不包含该键,输出false
System.out.println("====================");
System.out.println(mp.containsValue(1)); //HashMap中是否包含该值,输出true
System.out.println(mp.containsValue(2)); //不包含该值,输出false
System.out.println("====================");
System.out.println(mp.isEmpty()); //判断是否为空,输出false
System.out.println(mp.size()); //输出 HasMap 的长度,1
System.out.println("====================");
mp.remove("one"); //从HashMap中删除该键,值也会被删除
System.out.println(mp.get("one")); //输出null
System.out.println(mp.containsKey("one")); //输出false
System.out.println(mp.containsValue(1)); //输出false
//也可以通过 mp.remove("one",1); 把键和值一起删掉
System.out.println("====================");
//重新添加键值对
mp.put("one", 1);
mp.put("two", 2);
mp.put("three", 3);
System.out.println(mp.values());//输出所有值,[1, 2, 3]
System.out.println(mp.keySet());//输出所有键,[one, two, three]
System.out.println(mp.entrySet());//输出所有键和值,[one=1, two=2, three=3],中括号
System.out.println("====================");
HashMap<String,Integer> mp2 = new HashMap<String,Integer>();
mp2.put("four", 4);
mp.putAll(mp2); //添加同类型另一个HashMap,放进头部
System.out.println(mp); //输出整个HashMap的键和值,{four=4, one=1, two=2, three=3},大括号
System.out.println("====================");
mp.replace("one", 5); //替换键的值,java8才有
mp.replace("two", 2 , 6); //替换键的旧值为新值
System.out.println(mp); //输出{four=4, one=5, two=6, three=3}
System.out.println("====================");
Object mp3 = mp.clone(); //克隆一个,顺序随机
System.out.println(mp3); //输出{two=6, three=3, four=4, one=5}
System.out.println("====================");
for(String key:mp.keySet()) //遍历整个HashMap的键
System.out.print(key+' ');//输出four one two three
System.out.println();
for(Integer values:mp.values()) //遍历整个HashMap的值
System.out.print(values+' ');//输出36373835,并不是4 5 6 3 ,说明该方法不能输出值
for(Entry<String,Integer> entry:mp.entrySet()) { //遍历整个HashMap,输出键值
String key = entry.getKey();
Integer value = entry.getValue();
System.out.print(key+'='+value+' '); //输出four=4 one=5 two=6 three=3
}
System.out.println("====================");
mp.clear(); //清空数组
System.out.println(mp); //输出{}
System.out.println("====================");
}
}
到了这里,关于HashMap原理详解及常用API介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!