HashMap

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap

• 基础知识
  • 位运算
    • https://blog.csdn.net/xiaopihaierletian/article/details/78162863
    • 类型
      • 与运算&
        • 简介
          • 两个操作数都为1，结果为1，否则为0
        • 实例
          • 0&0=0,0&1=0,1&1=1
      • 异或^
        • 简介
          • 两个值不同为1，相同为0
        • 实例
          • 0^0=0,0^1=1,1^0=1
      • 或运算|
        • 简介
          • 两个数只要有一个为1，结果就为1，否则为0
        • 实例
          • 0|1=1,0|0=0,1|1=1
      • 取反运算~
        • 简介
          • 按二进制取反
        • 实例
          • ~1=0，~0=1
      • 左位移<<
        • 简介
          • num<<value，num转为2进制向左位移value位，乘上2^n
        • 实例
          • <<
            • num<<1
              • 1010
                • 10100
      • 右位移>>
        • 简介
          • num>>value，num转为2进制向右位移value位，带符号右移，正数高位补零，负数补1
        • 实例
          • >>
            • num>>1
              • 1010
                • 0101
      • >>>
        • 简介
          • 无符号右移，忽略符号位，右移后左边空出来的位用0填充，移出右边的丢弃
        • 实例
          • -14 >>>2
          • 11111111 11111111 1111111111110010
          • 00111111 11111111 1111111111111100
  • 哈希码 hashCode
    • 简介
      • hashCode 默认为JDK根据对象生成的地址
    • 区别
      • hashCode 相同,对象的值不一定相同
      • equal 相同,对象的值一定相同
      • 先比较 hashCode，不相同肯定不相同，再比较 equal ，相同则一定相同
    • 思考
      • a="a" ACI 为 97
      • Integer b = new Integer(97)
      • a.hashCode b.hashCode
• 实现
  • 1.7是数组+链表
  • 1.8是数组+链表+红黑树
    • 节点>=8转化为红黑树
    • 节点<6转化为链表
    • 红黑树
      • 特征
        • 比平衡二叉树多了颜色
        • 每个节点不是红色就是黑色
        • 根节点都是黑色
        • 新增节点默认红色，如果产生红色相连，变色或者旋转
      • 变换规则
      • 为什么不用其他树
        • 二叉搜索树
          • 没有平衡值，第一次添加的节点作为根节点，如果接下来添加的节点都比根节点大，会形成链表
        • AVL缺点
          • 查询快，插入删除慢
• 实现
  • 阈(yu)值
    • 作用
      • 扩容，节点数量>阈值(加载因子*数组长度)(12>=16*0.75）
    • 数值
      • 0.75
        • 综合时间复杂度和空间复杂度
      • <0.75
        • 内存充足，空间换时间
      • >1
        • 空间利用率高，哈希碰撞多，时间换空间
  • 数组初始化大小
    • 必须是2^n
      • 因为必须保证 2^n-1为01111
      • 如果为14，在做 & 运算的时候，hashCode 的最后一位，不管是 0 还是1，&0 都为 0，易造成冲突
      • 所以必须让结果取决于 hashCode 的二进制，所以必须是2^n
      • hashCode 01101
      • 2^n-1 01110
  • 扩容
    • 容量扩为原来两倍，对每个节点重新计算index值
• 区别
  • JDK7
    • 数组+链表
    • 头插法
    • 死循环Bug
  • JDK8
    • 数组+链表+红黑树
    • 尾插法
    • Node 封装键值对
    • 长度大于8转化为红黑树，时间复杂度为logn
• 优化
  • 哈希冲突
    • 开放地址法
      • 发生冲突时，如果 hash 表未被装满，所以还有坑位，那就可以把 key 放到冲突位置后面的空位上面，缺点是查找和扩容。
      • 发生冲突，地址+1
    • 再哈希法
      • 冲突时，再计算另一个 hash 值，直到冲突不发生，增加了计算时间，如果不考虑时间成本，对查询元素的要求极高，就可以考虑。
    • 链地址法
      • HashMap 采取的方法，用一个链表存储相同 hash 值的数据。
  • 获取元素
    • 链表
    • 红黑树
  • 扩容优化
    • 提前设置初始容量 （初始容量 = 预知数据量/加载因子)减少resize操作，提高效率。
    • 扩容 16*0.75 = 12 初始容量 = 预知数据量/加载因子 16 = 12/0.75
  • 技巧
    • (n-1)&num
      • n对num取模，n为2^n
    • 1>>4=16
• 问题
  • 1、HashMap 的初始容量是多少？
    • 答：16，底层是 1<< 4，左移 4 位，表示 2 的 4 次方。
  • 2、HashMap 底层如何解决 Hash 冲突问题？
    • 答：1.7 使用链表，1.8 使用链表 + 红黑树
  • 3、HashMap 是否线程安全
    • 答：不是线程安全
  • 4、HashMap 是否支持 key 为空对象？
    • 答：支持，放在数组为 0 的位置或者第一个链表。 HahTable 对象的 key、value 值都不可为null。
  • 5、HashMap 1.7 扩容存在哪些问题？
    • 1、在 JDK7，链表使用头插法，在多线程情况下，存在死循环问题。每次在数组扩容的时候，数组长度发生了变化，需要重新计算 index。把原来的table复制到新的table里面，因为 table是全局的，多线程情况下，会产生两个 new Table，赋值的时候，修改了原来 table 的共享的next，T1 线程扩容完后，改变原来 table B.next =A，A.next =B。JDK1.8 已经解决该问题。
    • 2、线程不安全问题。
    • 3、链表过长导致效率过低。
  • 6、加载因子为什么为 0.75 不是其他
    • 加载因子越大，index 下标冲突越大，但是空间利用很高； 加载因子越小，index 下标冲突越小，空间利用率不是很高； 下标冲突大，查询成本高，反之非常低； 所以必须在时间和空间之间做一个均衡。
  • 7、put 方法如何实现？
    • 1.对 key 求 hash 值，然后再计算下标 2.如果没有碰撞，直接放入数组中 3.如果碰撞了，放到链表中 4.如果节点已经存在，就替换旧值 5.如果链表长度超过阈值，转换成红黑树 6.如果同满了(容量*加载因子),就resize
  • 8、index 冲突和 hash 冲突区别？
    • index：对象不同，底层二进制运算产生相同 index，h&(length-1)必须是奇数 ； hash：对象不同，hashCode 相同
  • 9、HashMap 链表是单向还是双向
    • 答：单向
  • 10、链表长度过长会有什么问题
    • 答：效率降低，时间复杂度为O(N)
  • 11、HashMap 扩容多少倍
    • 2倍