java--HashMap数据结构( 二 ) _数组

map.put("美团","小美");
系统将调用”美团”这个key的()方法得到其值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀， Hash碰撞的概率就越小， map的存取效率就会越高。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
在理解Hash和扩容流程之前，我们得先了解下的几个字段。从的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：
首先， Node[] table的初始化长度(默认值是16) ， Load 为负载因子(默认值是0.75) ，是所能容纳的最大数据量的Node(键值对)个数。=* Load。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
结合负载因子的定义公式可知，就是在此Load 和(数组长度)对应下允许的最大元素数目，超过这个数目就重新(扩容) ，扩容后的容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子的值，这个值可以大于1 。
size这个字段其实很好理解，就是中实际存在的键值对数量。注意和table的长度、容纳最大键值对数量的区别。而字段主要用来记录内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
在中，哈希桶数组table的长度大小必须为2的n次方(一定是合数) ，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考，初始化桶大小为11 ，就是桶大小设计为素数的应用（扩容后不能保证还是素数）。采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，定位哈希桶索引位置时，也加入了高位参与运算的过程。
这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高的性能，其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论，想了解更多红黑树数据结构的工作原理可以参考。