51工具盒子JAVA数据结构总结
List数据结构
ArrayList
在超过initCapacity长度时，创建一个新的数据容器， 再执行arry copy 数据。相对来说读取快，因为有序。由于arry copy 机制导致插入删除慢
LinekArrayList
每个元素只记录当前的上一个元素和下一个元素指针。插入和删除快， 前提是知道要在哪个地方插入或者删除， 哨兵机制。相对来说插入快，因为无需执行arry copy ， 新插入或删除由于无序， 可直接往左右追加删除。读取较慢，因为无序，虽然有哨兵机制， 但速度上不如有序结构。
Map数据结构
HashMap：
首先对key进行hashCode获得一个int值， 为避免这个hash值重复， 通过异或操作符(^)将高16位与低16位进行混合, 以增加散列的随机性。之后对这个值进行%(求模运算)。hashMap本质上是： 数组 + 链表 + 树
-
hashMap如何解决hash冲突问题：
-
方案一： 当数组的槽位达到一定的阈值，增加槽位。
-
方案二： 当链表长度过长时，将链表转换为树
-
当已使用的槽位数量大于总槽位数量的75%，则会对槽位进行扩容。（Hash扩容）
-
为什么是8？当8个节点以二叉树来表示时， 刚好树的高度会大于等于3，因为2的三次方等于。如果树的高度过低， 则会造成链表的效率高于树的效率
-
当链表的长度大于等于8时， 则将链表结构转换成树形结构
-
如果put的key的hash值是一样的， 会调用equals进行比较， 如果一致， 则执行覆盖操作。如果不一致， 则往下创建链表， 下次再put这个值时， 就可以在链表上找到槽位。
-
由于上方的操作引发效率过慢问题， 则引出两种解决方案
-
<br/>
LinekHashMap
依靠插入链表法，利用空间换算时间。 是基于hashMap的基础上, 增加了一张有链表。这个链表记录了数据的存储位置， 在遍历时， 最终依靠这张链表来完成有序获取的操作
Set数据结构：
所有的set其实都是基于Map的key机制来实现不重复机制
HashSet
也是基于hashMap内的key结构。 当往容器中加入一项数据时， 会将当前元素本身作为key放到hashMap内，而hashMap又会将该元素进行hash运算和key比较，从而保证了元素的唯一性。
LinekHashSet
是基于LinekHashMap内的key结构，同上。
TreeSet
基于treeMap
补充1-异或操作符
异或操作符（^）是一种位运算符， 用于执行异或（XOR）操作。异或操作是指对两个二进制的相应位不同则结果为1， 否则为0。异或操作的规则如下
-
如果对应位上的比特位相同（都为0或者都为1），则结果为0
-
如果对应位上的比特位不同（1一个为1， 另一个为0）， 则结果为1
例如
1010
^ 1100
------
0110
# 以hashMap为列, hashMap中会对key进行hash并对值进行^16运算
# 假设获取到的值为: 12345678
0000 1011 1100 1100 0001 0010 0110
# 将该证书分为高低16位:
# 高16位
0000 1011 1100 1100
# 低16位
0001 0010 0110
# 按照异或操作的规则, 则计算出的值为
0001 1001 1010 1100
