java基础-数据容器之Map-HashMap
数据容器
在程序代码中，用来暂时存储数据的“盒子”（容器），用于后续的逻辑处理。
为什么需要map?
map是数据容器中的一种数据结构，首先它是用来存储数据的；其次，与其它数据容器不同，它是一种可以通过业务数据来快速、精确检索另一个业务数据的数据结构。
map：是一种key-value的数据结构;key和value都是业务数据，value是最终的业务数据，key是专门用来快速定位value在map中的位置。
数组和List也可以通过下标精确定位到业务数据，但必须“记住”下标与业务数据的关系才能在下次使用时精确定位，否则仍然需要遍历所有数据。map自动维护了“下标（key）”与value的关系，且这个“下标”是一个可以人为记忆的值，而不是像0,1,2...这样干巴巴不利于记忆的数字。
为什么需要HashMap
HashMap实现了map接口，且key的定位是通过key的hashCode实现；hashCode是一种简单快速的实现方式，因此hashMap性能很高。 当需要存储key-value数据类型，又需要通过key高性能查询value时，可以使用map。
HashMap的数据结构
结构：数组 ＋ 链表(或红黑树－链表长度大于等于8时自动转化为红黑树)
原理：通过 “下标＝key.hashCode％容量 ”（这里为了简化原理，实际上是通过位运算实现，效果类似）计算出数组下标。
Ａ：HashMap主存储结构是一个容量默认为16的数组；（初始创建的HashMap数组长度为0，第一次存储数据时扩容为16；长度为2N次方－后面会说明原因）
Ｂ：HashMap最终存储的数据结构是一批实现了Map.Entry的Node对象
Ｃ：Node的数据结构为：
key:业务数据，为node数据指定其在数组中的下标位置，并用于后续精确检索当前node，这也是hashMap高性能的原因。
value：业务数据，真正用于业务计算的数据，最终的目标数据。它的存储与检索都通过key来实现（当然自己即可做为key也可做为value);
hash:key对应的hash值；hash值与map中数组容量计算出的下标越散列，数据的在数组中的分布越均匀，也越不容易冲突。
next：由于数组长度有限，通过不同key的hashCode计算的数组下标很可能冲突（两个不同key计算的下标为同一个数组位置），此时通过数组下的链表来实现。next指向下一个Node.
jdk8增加了：链表长度大于或等于8时，链表自动转化为红黑树。红黑树多次删除结节后，长度小于等于6时再次转化为链表。
原因：链表转化为红黑树的目的是防止链表过长，增大因遍而导致的性能下降。
扩展知识：红黑树－简化理解为：一个平衡二叉树（所谓平衡即多次操作后，树不会变成一个链表）
特点
A：key和value都可以为null
B：线程不安全
Ｃ：元素是无序的
Ｄ：与HashTable相比：除了 key/value可以为空、线程不安全，基本是一样。
扩容
Ａ：新创建的HashMap（默认构造器）时，数组为空
Ｂ：第一次put数据或非默认构造器创建时，数组进行第一次扩容（初始化）：创建一个默认容量(1<< 4= 16) 的数组
Ｃ：当多次put后，数组元素个数 > 数组容量 ＊ 加载因子 时，再次进行扩容：创建一个新的数组( old容量 << 1 即扩容1倍)，把源数据复制到新数组中
Ｄ：最大容量为Integer最大值
Ｆ：默认扩容因子：DEFAULT_LOAD_FACTOR = 0.75 ：结合时间和空间效率考虑得到的
容量
为什么容量是2的幂数？
HashMap是通过“位与”运算，而不是通过取模来计算下标（为了效率考虑）。如果是2 的幂数，那么容量的人进制则全为：1。key的hashCode与容量进行“与”时，计算的结果只与key的hashCode后几位有关。(且记：此处仅仅为演示，实际并不是直接使用key的源hashCode，而是通过hashCode高低位异或取得，具体查看源码)
如下：(length-1) & key.hashCode
发现：如果length不为2的幂，进行位运行计算下标时，碰撞的机率非常大，链表真的可能性变高。而2的幂，下标只与hashCode后几位相关，因此只要保证hashCode均匀即可。
操作过程
Ａ：put操作：
Ｂ：get操作
原理同put，先获取下标，定位到链表在数组中的位置，再循环链表或红黑树查找，通过equals()方法定位具体对象(key和value同时equals())。
存在问题
线程不安全