HashMap：

• 版本差异：
  • HashMap1.7:
    • 采用头插法，可能会导致链表循环_{（尾节点意外指向头节点或意外操作[插入已有元素]，或无 环检测）}
  • HashMap1.8:
    • 采用尾插法，数据结构相比之前的数组+链表，多了一个红黑树
• 哈希冲突：
  • 哈希函数：接收一个输入，然后通过一个计算而得到一个特殊的值，这个值作为索引而在数组中快速找到相应的数据
    • 哈希值最大只有32位数，如果哈希值数量超过2的32次方
      • 就必然会有重复的哈希值，这就是哈希冲突
  • 解决方法：
    • 再散列法：若p=H（key）冲突时，以p为基础再Hash计算，p1=H（p），以此类推。
      • 要求：Hash表长度大于数据量
    • 再哈希法：采用不同的算法，R1=H1（key1）冲突时，采用R2=H2（key1）
    • 链地址法：将相同Hash值的元素构成一个链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在链表中进行。
      • 适用于经常进行插入和删除的情况。
      • HashMap采用的是链地址法
    • 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
• 默认加载（负载）因子：0.75
• Key的索引存储计算方式：
  • 根据Key的值计算出HashCode的值，然后再根据HashCode计算出Hash值，根据hash&（length-1）计算出存储的位置
    • 为什么hash要和length-1相与？
      • 为了将哈希值转换成一个合法的、不会导致数组越界的下标。
      • 最直观的做法就是取模运算
        • 但是性能效率低
      • 用length-1的位与运算巧妙代替
        • 当 length 是 2 的n次方时，h& (length-1) 运算等价于对length取模（h%length），但性能效率更高
        • HashMap数组的长度length为什么是2的幂次方？
          • 2 的 N 次幂有助于减少碰撞的几率。如果 length 为2的幂次方，则 length-1 转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非常的快，而且空间不浪费。
          • 如果length不是2的n次方的话,以length=15为例，hash值与14（length-1）[即1110]相与时,得到的最后一位永远都是0,所以末尾为1的位置处是存不进数据的,会造成极大的内存浪费

• 线程安全
  • 如果在插入数据时多个线程命中了同一个槽，可能会有数据覆盖的情况发生
• 解决方案：
  • 直接就加锁，但是会牺牲性能
  • 使用hashTable，其实就是加了synchronized锁（悲观锁），性能更高
  • 使用concurrentHashMap，本质是减少了锁的粒度，减少线程竞争来保证高效

HashSet：无序唯一的元素集合

• 高性能：
  • 数据结构：哈希表，键值对形式性能高效
  • hashcode（）：向HashSet添加对象时，会调用该对象的hashcode（）方法，返回哈希码。
  • 哈希码：HashSet会计算桶的索引，快速索引
    • 元素存储：将元素存储到哈希码索引对应的位置
      • [Tips]哈希冲突：哈希码互相相同
        • {解决方案}:在桶内部存储链表或树,发生冲突后会将新元素添加到该桶的树或者链表中