少侠，师傅说氪hashMap先氪基本概念

    JDK文档中如是说”基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使
用null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相
同。）不保证映射的顺序“
实际就是说:
   1.HashMap是Map接口的实现,因此内部使用key,value存储
   2.HashMap内部元素是无序的

键值对存储优点呢？

对key进行Hash运算，通过hash值除以数组长度-1确定存储位置， 则get时同理通过hash值除以
数组长度-1获取存储位置的值，这种方式可直接定位值

那怎么理解无序性？

public class HashMapTest {
public static void main(String[] args) {

    Map<Integer,String> map=new HashMap();

    map.put(21,"abc");
    map.put(12,"abc");
    map.put(3,"abc");
    map.put(5,"abc");
    map.put(16,"abc");
    map.put(20,"abc");


    System.out.println("循环遍历结果：");
    for(Integer key:map.keySet()){
        System.out.print(key +" -> ");
    }
}

}

循环遍历结果：

16 -> 3 -> 20 -> 21 -> 5 -> 12

元素存放图

元素存放图.png

原因：

存储位置通过Hash运算和数组.length-1确定，这种方式确定的存储位置，只能保证键值对无序存储

HahMap使用的数据结构

1. 数组：
  - 只能存储同一种数据类型的数据。
  - 一旦初始化，长度固定。
  -  数组中的元素与元素之间的内存地址是连续的。
  优缺点摘要 ：
     空间连续存储单元，索引访问元素，随机读取效率很高，则其查找速度快。查询时间复杂为O（1）。
     插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中要往后移的，且大小固定不易动态扩展。且占用内存严重，空间复杂也很大。 
     总结：大数据量情况下，提供高效的查询，低效的插入和删除

数组.png

2. 链表：
   -物理空间不连续的存储单元
   -运行时可以动态添加
   简要：元素内容由存储内容及下一个元素地址，称为单向链表；元素内容由存储内容，上一个元素地址及下一个元素地址，称为双向链表；
  优缺点摘要 ：
     1.空间不连续的存储单元，空间复杂度较小，时间复杂度较大
     2.插入删除效率较高。较数组使用索引的查询方式，查询效率较低
     总结：在大数据量的情况下，提供的高效的插入和删除，采用无索引的查询方式，低效的随机访问能力（查询）

单向链表.png

补充：数组与链表的时间复杂度，空间复杂度比较呢？

数组时间复杂度概要.png

链表时间复杂度概要.png

在了解红黑树之前呢我们先了解HashMap的主要方法

• put(K,V)方法

  1.首先将k,v封装到Node对象当中（节点）。
  2.然后它的底层会调用K的hashCode()方法得出hash值。
  3.通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

• get(K,V)方法

  1.先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
  2.通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

  补充：HashMap重写了equals方法，Object的equals之比较对象是否相等，增加了对象相等再去比较值是否相等的情况；重写了hashCode方法，如果
  hashCode不相等，那么这个对象则不相等，省去的equals的那一步
  

随机增删、查询效率都很高的原因是？

原因: 增删是在链表上完成的，而查询只需扫描部分，则效率高。

• 扩容方法 resize()方法

  扩容原理：还没看懂
  那就梳理几个理解性的问题
  什么时候扩容？ 答曰：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(知道这个阈字怎么念吗？不念fa值，念yu值四声)---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。
  怎么理解扩容？答曰：重新计算数组容量；每个数组单元都链接有链表，数组单元越多越能装。
  为什么设置加载因子，有什么用？ 答曰：首先明确数组查询快，插入慢，占空间大，链表插入快，查询慢，占空间下；元素最先存到数组上，发生哈希冲突后存入链表。数组越长空间越大，冲突越多查询越快；
  旨在平衡这两点，根据统计学规律这个0.75，hashMap整体性能最高

部分内容与图片摘自网络，如有侵权请转达！！