目录
一、预备知识
时间复杂度
时间复杂度用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着输入 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。渐进时间复杂度用大写O来表示，所以也被称为大 O表示法。
常用的时间复杂度比较:
O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)
从左到右，算法执行效率逐渐下降,
了解更多：
当前存放三个人记录的数组就是散列表，我们定义的规则就是散列函数，根据散列函数进行映射的过程叫做散列过程。
如果又来一个人叫周日，根据我们的规则，周日也要落在1的位置上，此时就产生了冲突。这里我们使用单独链表法处理，把周天放在索引为一的位置和赵四构成链表（新元素是放在链表前端还是后端完全是取决于怎么方便）。
散列表查找是就是先找到桶的位置，再遍历查找需要的数据。如果散列函数设计的不好，所有的元素都落在一个桶里那效率就特别低，和单链表随机访问没什么区别。
基本位运算
运算符 计算方式 与 & 只有两个数同一位都是1才会返回1 或 l 两个数同一位只要存在一个1就是1 异或 ^ 两个数同一位不能相同才为1 左移 << 所有位置左移，低位补0 右移 >> 正数：所有位置右移，高位补0
负数：写出补码（符号位不变，其余位置取反，然后加1），所有位置右移高位补1，然后再获取原码（符号位不变，其余位置取反，然后加1）无符号右移 >> 无论正负高位补0 了解更多：
jdk8
速度
查询与修改
先用散列函数对键进行散列，没有冲突的情况下查询是下标查询，时间复杂度是 O(1),速度很快。
存在哈希冲突的情况，需要对链表/红黑树进行遍历，equals比对查询。
性能上，考虑是链表/红黑树上的元素越是越好，越均匀越好；此外HashMap主干未必越长越好，会有用不到的桶浪费空间。
增加与删除
由于查询速度快，而桶里用链表/红黑树实现，所以添加和删除效率也很高。HashMap会在size超过阀值后进行调整大下(resize)，所以根据具体情况提前给HashMap一个合适的初始长度是个不错的习惯。
三、源码分析
基本常量
// 默认初始长度，即主干数组的长度，如果创建对象时没有给长度，默认是16 // 在明确知道元素个数的情况下，初始化时建议可以把容量设置成expectedSize / 0.75F + 1.0F (guava) static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量,HashMap最大容量是2^30 // 因为int范围是-2^31——2^31-1,但32位2进制最高位是符号位，所以最大是2^30 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子，默认是0.75，创建对象时可以自定义 // 可以用于计算扩容阀值transient Node<K,V>[] table; static final float DEFAULT_LOAD_FACTOR = 0.75f; // 树化阀值 // 当某一个桶中链表长度超过8时会转化为红黑树 static final int TREEIFY_THRESHOLD = 8; // 去树化阀值 // 当一个桶里红黑树总结点数小于6时，会转化为链表 static final int UNTREEIFY_THRESHOLD = 6; // 最小树化容量 // 树化的另一个条件，只有主干数组长度大于64才进行树化 static final int MIN_TREEIFY_CAPACITY = 64;CAPACITY是 HashMap容量(主干数组长度)，size是键值对个数
