存储数据结构之HashMap

文章目录

1、HashMap为什么产生？2、在构造HashMap过程中会产生哪些问题？2.1、初始化数组长度应该为多少？2.2、如何确定键值对在数组中的存储位置？2.3、产生hash冲突如何解决？2.4、当链表长度过大会引发什么问题？2.5、为什么是8时变为红黑树？2.6、何时扩容，何如扩容，为什么？ 3、ConcurrentHashMap为何产生

1、HashMap为什么产生？

问题 在大数据背景下，如何设计出查增数据速度快的数据结构，且需要存储键值对？ 解决思路： 1、数组具有查找快速的特点，能存储键值对 2、链表具有增删快速的特点 结论： 此时HashMap应运而生，具有上述两点特性，在jdk8中hashmap是数组+链表+红黑树的数据结构

2、在构造HashMap过程中会产生哪些问题？

2.1、初始化数组长度应该为多少？

应该为2^n，为了与hash函数结果值运算，运算结果与hash函数值无关，从而确定下标位置

2.2、如何确定键值对在数组中的存储位置？

采用hash函数方法，对键进行hash运算，得出一个整数，但这个整数并不能对应数组的下标，为了解决下标，需要对这个整数进行与运算（&）,异或运算数是数组长度减一，是为了符合数组下标。

2.3、产生hash冲突如何解决？

当两个不同键的hash结果值相同即为hash冲突，产生的下标也必然相同，此时hashmap解决的方法是链地址法，将产生有相同下标的节点放在相同下标节点的后边形成链表,在发生冲突之前需要将高16位与低16位进行异或，降低冲突的概率，最后再进行下标的运算

2.4、当链表长度过大会引发什么问题？

会导致查找速度变慢，失去此种数据结构的意义，如何解决？，当链表长度大于8时变成红黑树，当从红黑树移除节点至六个节点时变成链表

2.5、为什么是8时变为红黑树？

此时联系到最佳时间复杂度，经过数学验证得出节点为八时为最优时间复杂度，六节点同理可得

2.6、何时扩容，何如扩容，为什么？

当数组填充为75%为需要扩容，75%如何得来？根据链表，红黑树，数组的综合最优时间复杂度。扩容过程是根据类型进行数据迁移，若是数组上，则直接迁移到新数组上，索引位置的保证是根据新总数组减一与hash值进行异或

3、ConcurrentHashMap为何产生

问题需求: 多线程同时操作hashmap,如何保证安全? 思路： 加锁 Java5提供了ConcurrentHashMap，它是HashTable的替代，HashTable锁住整个表，不利于显示出多线程的工作效率。ConcurrentHashMap解决了这个问题，对hash表实现了分段锁，每个段只能有一个线程操作，其他段可以有其他线程操作