数据结构

重要参数

• **容量（**capacity）： HashMap中数组的长度
  • 容量范围：必须是2的幂 & <最大容量（2的30次方）
  • 初始容量 = 哈希表创建时的容量
  • 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  • 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
    static final int MAXIMUM_CAPACITY = 1 << 30;
• 负载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
  • 默认加载因子 = 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
• 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）

源码分析

构造函数

put方法解析

1. 若哈希表未初始化（即 table为空) 则使用 构造函数时设置的阈值(即初始容量) 初始化 数组table
2. 判断key是否为空值null，
   • 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0] 本质：key = Null时，hash值 = 0，故存放到table[0]中）
   • 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）
   • 判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
     • 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
     • 若该key不存在，则将“key-value”添加到table中

• HashMap的键key 可为null（区别于 HashTable的key 不可为null）
• HashMap的键key 可为null且只能为1个，但值value可为null且为多个

初始化哈希表

将传入的容量大小转化为：>传入容量大小的最小的2的幂，容量超过了最大值，初始化容量设置为最大值 ；否则，设置为：>传入容量大小的最小的2的次幂

如何计算hashTable中的索引

• 计算hashCode
• 二次扰动：位运算和异或运算处理hashCode => h
• index = h & (length-1)

为什么不直接采用经过hashCode（）处理的哈希码 作为 存储数组table的下标位置？

结论：容易出现 哈希码 与 数组大小范围不匹配的情况，即 计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置

为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突。

为什么数组的长度要求为2的n次幂

数组长度减1的结果二进制形式为 011111…形式 首位为0 后面均为1
保证 index = h&(n-1) 的结果的奇偶性由 h本身的奇偶性决定，最后一位为0，则存储位肯定是偶数增大了冲突的概率

键值对的添加/替换流程

• 添加使用的数组头插法，新添加的节点总是放在数组的头位置
• 替换发现key相等只用找到key对应的节点把value覆盖掉就行

扩容机制

put方法时判断数组实际大小大于扩容阈值，保存旧数组创建两倍当前容量的数组，遍历旧数组的每个数据，重新根据hash函数计算，将旧数组上的每个数据逐个转移到新数组中，重新计算新数组的阈值，扩容结束。

##1.7和1.8的区别