关于集合的底层数据结构

单列集合Collection分为list集合和set集合

list集合分为ArrayList和LinkedList

ArrayList--底层数据结构是数组

1.通过索引查询快

2.增删要重构索引,增删慢   

LinkedList--底层数据结构是链表

1.无索引查询慢

2.通过改变前节点的尾指针和后节点的前指针指向可快速增删,增删快

set集合(不可重复，没有索引，迭代器遍历)分为HashSet和TreeSet

HashSet存储数据原理-数组加链表/数组加红黑树,数组内存连续查询效率高，链表内存分散增删改效率高，哈希表的默认长度是16，超过这个长度时开始进行扩容(数组长度乘2),当链表节点个数大于8时链表会转化为红黑树,哈希表采用此种存储数据的形式极大的提高操作数据的效率

1.存储数据时会先操作(元素值作Key)key调用.hashcode（）方法得出hash值，然后再通过哈希算法转换成数组的一个下标，对应的就是在数组上的的存储位置。

2.如果该位置没有数据，则直接存储。如果该位置有数据，则会发生数据碰撞。数据碰撞的时候遍历该位置上链表中的所有数据，并且通过equals()方法来比对每个数据的key。如果key相同的话，会将链表上该位置的数据进行覆盖。如果key不相同的话，在JDK1.8之前是实行的头插法，数据存储在链表头部，1.8之后实行的是尾插法数据存储在链表尾部。

3.JDK1.8之后，当链表上的节点个数（数据个数）大于等于8时并且数组长度不小于64的时候，链表数据结构自动进行树化转化成红黑树，当链表上的数据小于等于6时，又会自动退化成链表,当链表上的数据大于64时会进行扩容

TreeSet存储数据原理-红黑树

红黑树是一种自平衡二叉查找树，它具有以下特点：

1.红黑树规则

每个节点要么是红色，要么是黑色。

根节点是黑色的。

所有叶子节点（NULL节点）是黑色的。

如果一个节点是红色的，那么它的子节点必须是黑色的。

从根节点到每个叶子节点的路径上，黑色节点的数量相同。

2.红黑树添加节点规则

红黑树添加节点默认是红色的，添加的是根节点自动变黑。添加的是非根节点位置看父节点，父黑，不操作，父红，叔红，父叔变黑，祖父变红，若祖父为根节点，变黑。添加的是非根节点位置看父节点，父黑，不操作，父红，叔黑，父变黑，祖父变红，以祖父为节点进行旋转平衡二叉树要通过选择保持平衡，增删效率低，红黑树不用通过大量的旋转来维持平衡，所以增加了增删效率

双列集合Map

1.HashMap存储数据原理-数组加链表/数组加红黑树

2.TreeMap存储数据原理-红黑树