一、HashMap
数组+最简单的原理
[<张三，32岁>，<李四，54岁>] —>数组
对key计算出一个hash值，根据这个hash值对数组进行取模，也就是index,定位到数组里的元素中去
map.get(“张三“) —> hash值 —> 对数组长度进行取模 —> return array[1]
Array[1]= <李四，54岁>
二、jdk1.8中对hash算法和寻址算法
1、hash值进行右移 16位，把2进制往右边推16位，把高16位推到低16位上来，前面用0来补齐，然后原来的hash值 与 右移出来的hash值 进行异或 异或出来的hash值包含了高16位与低16位hash值得特征。使高低16位都参与了运算
异或出来的 hash值 就是一个32位的 int值
异或 两个一样 是0； 两个不一样 是1
如 1 0
1 1
0 1
数组—> hash值对数组长度取模，定位到数组的一个位置
2、优化地方，寻址算法优化
（n-1）& hash —> 数组里的一个位置
取模运算，他是性能比较差，为了优化这个数组寻址的过程
（n-1）& hash —>效果要跟hash对n取模，效果是一样的，但是与运算的性能要比hash对n取模要高很多
总结jdk1.8中对hash算法和寻址算法是如何优化的？
1、hash算法的优化：对每个hash值，在他的低16位中，让高低16位进行异或，让他的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一个位置。
2、寻址算法的优化：用与运算替代取模，提升性能。
三、解决hash冲突问题，链表+红黑树，O(n)和O(logn)
map.put 和 map.get —> hash算法优化（避免hash冲突），寻址性能优化
算出key 的hash值，到数组中寻址，找到一个位置，把key-value对放进数组，或从数组里取出来
两个key 多个key ，他们算出来的hash值，与n-1 ，与运算后，发现定位出来的数组的位置还是一样的，hash碰撞，hash冲突
会在这位置挂一个链表，这个链表里放入多个元素，让多个key-value 对，同时放在数组的一个位置离
get，如果定位到这个数组里发现这个位置挂了一个链表，此时遍历链表，找到你要的key-value对就可以了
假设这个链表很长，可能会导致遍历链表，性能会比较差 O(n)
优化，如果链表的长度达到了一定的长度之后，其实会把链表转换为红黑树，遍历一颗红黑树找到一个元素，此时O(logn)，性能会比链表高一些
