程序=数据结构+算法

数据结构

数组+链表+红黑树
数组:一段连续的存储空间单元存储数据
特点:查询0(1) 删除插入0(N) 查询快,插入慢
链表:一个非连续\非顺序的存储结构
特点:插入\删除时间复杂度0(1) 查找遍历时间复杂度0(N) 插入快,查询慢

JDK7和JDK8的区别

  1. JDK7的结构由数组和链表组成,JDK8由数组和链表+红黑树组成
  2. JDK8的插入方式将原本的头插法变成了尾插法
    jdk7之所以将entity的插入方法设计为头插法,是因为设计人员认为后面插入的比较容易被找到,而且不需要遍历查找哪个元素是最后一个元素
  3. Jdk7插入时需要判断链表是否需要扩容,再插入,而jdk8插入时是先插入后再判断是否需要扩容

    算法

    哈希算法(幂等性),就是把任意长度值(key)通过哈希算法变成固定长度的key(地址)通过这个地址进行访问的数据结构.它通过一个关键的码值映射到表中,位置来访问记录,以加快查询的速度
    image.png
    HashCode:通过字符串的ASCII码再进行取模(mod),算出hash表中的下标
    为什么要取模?
    因为数组是由一个连续的存储单元存储数据,如果没有取模,那么假设一个字符串的出的ASCII码为485,那么如果把这个数值作为下标,那么数组的长度一定要比485大才行,那么这将导致数据冗余,而且hashmap的数组长度默认为16,取模一定程度上能够保证算出来的索引<16,所以需要取模,节约空间
    存在的问题
    hash冲突(碰撞)
    如果两个字符串算出来的ASCII码一致,取模后地址也一样,那么就会导致地址冲突
    image.png
    解决方法
    链表解决这个问题,将冲突的元素使用头插法(jdk7)或尾插法(jdk8)加入链表中
    JDK8为什么使用红黑树?
    因为如果使用链表查询的话,每次找是从头部开始插入,查也是从头开始,那么链表的长度为100,我们要找的在98,那么就要从头开始向下查,需要找98次,这样就导致了效率过低,所以引入了红黑树
    链表—>查询次数7image.png
    红黑树—>查询次数4image.png
    那为什么jdk8还用链表呢?
    jdk8的hashmap一开始并不是直接就为红黑树,而是链表,转换成红黑树的条件是链表的长度达到一定的阈值才会转换为红黑树,这个阈值就是8
    为什么转变为红黑树的阈值是8?
    因为红黑插入时需要判断插入的值,并进行左旋或右旋,也就是查询快,插入慢;而链表是插入快,查询慢;鱼与熊掌不可兼得

    扩容机制

    扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
  • capacity 即容量，默认16。
  • loadFactor 加载因子，默认是0.75
  • threshold 阈值。阈值=数组容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

    触发时机

    一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。
    HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（即永远不会超出阈值了）。

两个版本的扩容机制

JDK7的扩容机制

  • 空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。
  • 有参构造函数：根据参数确定容量、负载因子、阈值等。
  • 第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。
  • 如果不是第一次扩容，则HashMap原理 - 图5

JDK8的扩容机制

  1. 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
  2. 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 HashMap原理 - 图6。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！）
  3. 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

注意

首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容； 不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；

元素迁移

JDK7 HashMap的内部数据保存的都是链表。因此逻辑相对简单：在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值（也有可能不计算），找到新数组中的对应位置，以头插法插入新的链表。

  • 因为是头插法，因此新旧链表的元素位置会发生转置现象,也就是链表装入新数组后是反向的,例如:1,2,3,4,5,6,1作为链表首个,装入新数组的时候是从头部开始拿,那么新数组插入先进的就越底下。
  • 元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转）


JDK8 因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图： image.png 数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。

在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了

  • JDK8在迁移元素时是正序的，不会出现链表转置的发生。
  • 如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。

常用方法的原理

PUT方法

执行流程

image.png

  1. 先对key进行运算,得到key的hashcode
  2. 判断hashmap对象中的数组是否为空或null,如果是那么执行resize()方法进行扩容
  3. 判断table数组的首个元素的key是否与传入的key相同,如果是则覆盖,否则就判断table[i]是否为treeNode(红黑树节点),如果是则向红黑树中插入数据,否则遍历链表找到对应的key覆盖值,如果判断得知链表的长度大于8,那么会将链表转换为红黑树结构,在红黑树中插入数据
  4. 插入成功后,判断实际存在的键值对是否超过了最大容量,如果超过,则进行扩容

    对应源码

    ```java public V put(K key, V value) { // 对key的hashCode()做hash return putVal(hash(key), key, value, false, true); }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node[] tab; Node p; int n, i; // 步骤①：tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步骤②：计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 步骤③：节点key存在，直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步骤④：判断该链为红黑树 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 步骤⑤：该链为链表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key,value,null); //链表长度大于8转换为红黑树进行处理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); break; } // key已经存在直接覆盖value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } }

  1.  ++modCount;
  2.  // 步骤⑥：超过最大容量 就扩容
  3.  if (++size > threshold)
  4.      resize();
  5.  afterNodeInsertion(evict);
  6.  return null;

}

  1. <a name="ivVx8"></a>
  2. ### Get方法
  3. 首先我们知道数组中的元素是由Entry对象组成的
  4. ```java
  5. class Entry{
  6. key,
  7. value,
  8. index,
  9. hash
  10. }

get(key)也会进行根据key的hashcode获得所对应的数组下标,如果找到该下标的链表遍历比对,
如果entry的hash值比对不上,则看还有没有next,有则看next中的entry,否则返回null