简述HashMap及其常用API总结

男娘i 2023-10-01 22:41 25阅读 0赞

**一、什么是HashMap**  
HashMap是Java当中一种数据结构，是一个用于存储Key-Value键值对的集合，每一个键值对也叫作Entry实体。  
HashMap 数据结构在jdk1.7及之前是数组+链表，在jdk1.8中。为了优化大数据量场景下的性能低下问题，引入了红黑树，当满足一定临界条件时链表会转化为红黑树，所以jdk1.8之后的数据结构就是数组+链表+红黑树。  
其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）。  
![在这里插入图片描述][f2191b7e3e3b4994b8fe48615ec7f245.png]  
**二、HashMap存储原理**  
**1、初始化 HashMap**  
初始化 HashMap提供了有参构造和无参构造,具体的关于HashMap的构造函数如下所示，无参构造中，容器默认的数组大小 initialCapacity 为 16，且数组大小只允许为2的整数次幂，默认加载因子loadFactor 为0.75。容器的阈值为 initialCapacity \* loadFactor，默认情况下阈值为 16 \* 0.75 = 12。当存储在HashMap集合中的Entry数目大于容器的阈值，则容器需要扩容，使其容量变为原来的两倍。

//构造一个具有默认 初始容量 (16)  和 默认加载因子 (0.75) 的空 HashMap。
    HashMap();
    //构造一个带 指定初始容量 和 默认加载因子 (0.75) 的空 HashMap。
    HashMap(int initialCapacity);
    //构造一个带指定初始容量和加载因子的空 HashMap。
    HashMap(int initialCapacity, float loadFactor);

**2、解析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表中的均匀分布。  
**那么又为什么hashmap的容量一定是2的幂次方呢？**  
原因如下：  
1.计算机内&运算速度较快，至少比%速度要快；  
2.当length为2的整数次幂时，会满足一个公式:(length-1)&hash=hash%length;  
3.采用(n-1)&hash来计算索引位置时，当n为2的幂次方的时候，n-1转换为二进制时可以保证低位全都是1，所以元素存储在哈希表中的位置完全取决于其hash值，而Java中的hashCode()方法能够满足元素的均匀分布，因此就会导致元素索引分布均匀。  
**三、HashMap和HashTable 的异同**  
![在这里插入图片描述][c745cb9e9ba849fea196d5922de0ebeb.png]**四、HashMap常用API**

HashMap<String,String> map = new HashMap<>();
            map.put("name","zhangsan");     //添加,若key存在，直接修改值
            map.replace("name","mazi");     //修改
            map.get("name");    //根据key--获取value
            map.containsKey("name");     //是否包含某个key
            map.remove("name");     //  根据key删除
            map.remove("name","zhangsan");      //根据key,value删除
            map.clear();     //清空
            map.isEmpty();   //判断是否为空
            map.keySet();    //所有key----返回一个set集合
            map.values();    //所有value
            map.size();      //长度
            map.entrySet();     //返回一个entry

[f2191b7e3e3b4994b8fe48615ec7f245.png]: https://img-blog.csdnimg.cn/f2191b7e3e3b4994b8fe48615ec7f245.png
[c745cb9e9ba849fea196d5922de0ebeb.png]: https://img-blog.csdnimg.cn/c745cb9e9ba849fea196d5922de0ebeb.png