数据结构之数组和单链表

问题：HashMap如何组织数据达到 快速索引的目的的？

数据结构-数组

数组是一块连续的内存，存放着共同特性的内容，因为是连续的，直接通过下标索引快速定位。

image.png

◆优点：连续的内存，通过下标可以快速寻址；
◆缺点：插入节点困难；

数据结构-单链表

单链表由一个数据和指针组成的一个节点。Head头部，tail单链表的尾部

image.png

◆优点：插入和删除数据方便 。
◆缺点：查询效率低；（查找需要遍历这个列表）

数据结构-HashMap

1.插入数据 pos(位置) = key%size (数据除长度求余，这个余数就是数据的位置)
2.计算求余之后，相同的位置值用单链表来扩展。冲突前数据100指针指向冲突后数据200
3.查找值时直接定位位置0，找到了100，不对。继续找下一个节点200,比较到200存在，就返回...但是，当单链表长度过长，产生了on，遍历费时
4.HashMap在JDK1.8之后引入了红黑树（特殊的二叉树）。二叉树的查询效率是树的深度。红黑树解决了当单链表过长时，将单链表转化为红黑树，提高查询性能。

image.png

引入红黑树后的结构：

image.png

1.插入数据 pos(位置) = key%size (数据除长度求余，这个余数就是数据的位置)
2.计算求余之后，相同的位置值用单链表来扩展。冲突前数据指针指向冲突后数据
3.查找值时直接定位位置0，找到了100，不对。继续找下一个节点200,比较到200存在，就返回...但是，当单链表长度过长，产生了on，遍历费时
4.HashMap在JDK1.8之后引入了红黑树（特殊的二叉树）。二叉树的查询效率是树的深度。红黑树解决了当单链表过长时，（当链表长度超过阈值（8））时，将单链表转化为红黑树，提高查询性能。

问题:HashMap 初始容量为什么是2的倍数？

(1)取决于操作系统，他在申请内存的时候往往是2的倍数，申请2的倍数避免了内存碎片
(2)计算器擅长移位操作，采用移位效率更高。
(3)避免hash值的冲突
源码分析

image.png
image.png

一.Hashmap 的数据结构包括了初始数组、链表、红黑树；

二.HashMap 数组容量 2 的倍数的好处：
1 提高运算速度；
2 增加散列度，降低冲突；
3 减少内存碎片

三.hash 函数与 pos 定位：hashcode的高 16 位与低 16 位进行异或求模，增加了散列度，降低了冲突

四.插入冲突：通过单链表解決沖突，如果链表长度超过（TREEFY THRESHOLD=8），进行单链表和红黑树的转换以提高查询速度

五.扩容：扩容的条件：实际节点数大于等于容量的四分之三；
扩容后数据排布：要么是原下标的位置；要么是原下标+原容量的位置

六.序列化：只存储了数组的容量、实际节点数量和各个节点的 key、value值

参考文章：
https://blog.csdn.net/hefenglian/article/details/79763634
http://www.cnblogs.com/shsxt/p/7822868.html
http://www.cnblogs.com/chengxiao/p/6059914.html