java进阶(29)--HashMap集合
一、HashMap简介
1、HashMap底层是哈希表结构，类似字典，初始化如下：
2、哈希表结构：
是一个数组+单向链表的结构体
数组：查询效率较高，随机增删效率很低
单向链表：在随机增删方面效率较高，查询方面效率很低
哈希表将以上两种数据结构融合在一起，充分发挥它们各自的优点。
3、HashMap集合底层是数组，Node<k,v>[]tables;
hash为哈希值，是HashCode方法执行的结果，通过哈希算法可以转换为数组的下标；
key，value为Map的key与value，next为下一个内存地址
4、map.put(k,v)的实现原理
k，v封装到Node对象内，底层调用hashCode()方法得出hash值，通过哈希算法/哈希函数，将hash值转换成数组下标。
如果下标对应的位置上面没有元素，Node添加到位置上；
如果下标对应的位置上有链表，拿k与链表每个节点k进行equals，如所有equals方法都false，新节点将添加到尾部；
如果有一个euals返回true，那么这个节点的value值将会覆盖
5、map.get(k)的实现原理
调用k的hashCode()方法得出哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置，位置上什么都没有话，返回null；
如果这个位置上有单向链表，那么会拿着参数k和单向链表上每个节点的k进行equals，如果所有的equals返回false，囊二get方法返回null。
主要其中某一个节点的k和参数k equals返回true，那么此时这个节点的value就是我们要找的value，既为get方法的最终返回value
6、HashMap的key部分元素需要重写equals方法hashCode方法。也就是hashSet集合中的元素需要重写equals方法hashCode方法。
7、HashMap使用不当时会发生性能问题：
假设所有的hashCode方法返回值都相等，那么底层会变成单向链表，即散列分布不均匀。
什么是散列分布均匀：100个元素，10个单向链表，每个单向链表中包含10个节点。
假设所有的hashCode方法返回均不一样，那么底层会变成数组，即散列分布不均匀。
散列分布均匀需要重写hashCode方法有一定的技巧
8、HashMap集合底层数组达到75%容量时，数组是开始扩容，默认数组容量为16，初始化容量必须是2的倍数，为达到散列分布均匀，且可以提高hashMap集合存取效率。
9、HashMap元素存取什么时候不需要执行equals方法：k.hashCode方法返回的哈希值的数组下标位置为null的时候，equals不再需要执行。
10、HashMap JDK8改进：
如果哈希表的单向链表中元素>8，单向链表会变成红黑树，当红黑树上节点数量<6，会重新把红黑数变成单向链表
11、哈希表数据结构注意事项：
如果o1与o2的hash值相同，一定在同一个单向链表上，
如果o1与o2的hash值不同，但由于哈希算法执行结束后转换的数组下标可能相同，此时会发生“哈希碰撞”
二、实例说明：
1、测试HashMap元素特点：key为integer，它的hashCode与equals均已经被重写
2、遍历Map集合-元素将被无须取出
3、重写quals与hashCode方法
未重写hashCode与equals
重写hashCode与equals后
4、HashMap的key与value可以为空吗，
HashMap可以，Hashtable不行