Collection集合

List集合

ArrayList是动态数组，底层实现是一个Object数组。当使用无参构造器ArrayList()时，初始容量elementData为0。第一次扩容时容量+10。之后再次需要扩容时，扩为原容量的1.5倍。当使用有参构造器时，初始初始容量为传进去参数的容量大小。需要扩容时，扩为原容量的1.5倍。

ArrayList的最大容量
    根据ArrayList源码，ArrayList的最大容量为Integer.MAX_VALUE - 8也就是2147483639。为什么不是Integer.MAX_VALUE呢？因为有些虚拟机在数组中保留一些header words，所以预留了8来防止越界

LinkedList

LinkedList是java实现的双向队列，他有三个成员变量。LinkedList因为是链表引起增加和删除操作速度快于ArrayList，修改和查询慢于ArrayList。

 Node(根据索引查找节点)
LinkList的Node()方法是根据索引查找节点。Node()是LinkedList里面最重要的方法，增删改查都需要用到这个方法。这个Node()并不是傻傻的从头到尾遍历一遍。他是先判断索引的大小，如果索引大于size/2 (用的还是位运算),那就从尾向前遍历。如果索引小于size/2，那就从头到尾遍历。
 

indexOf(根据节点值查找索引)

这个就真的是傻傻的从头到尾遍历了

Set
HashSet
当我们new了一个HashSet然后点进他的构造器，我们就会惊讶的发现HashSet的底层实现是HashMap。而当我们传入一个集合时，HashMap的初始容量是max(集合容量/0.75+1,16)。
HashSet的实际数据存在Node里面的key。Node中的value使用了一个静态变量PERSENT占坑

详情见：
————————————————
版权声明：本文为CSDN博主「OldZhangYH」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40679774/article/details/123229719

jdk8 HashMap底层原理

HashMap作为Map的主要实现类,jdk1.2出现，线程不安全，效率高，可以存储null的key和value，jdk7中其底层结构只有：数组+链表，jdk8中其底层结构：数组+链表+红黑树，关于jdk8的

HashMap属性ruxia：
1）DEFAULT_INITIAL_CAPACITY: HashMap的默认容量：16（初始值和为存入元素时可以为0）
2）DEFAULT_LOAD_FACTOR： Hash默认的加载因子：0.75
3）TREEIFY_THRESHOLD： 当链表中数据大于改默认值，则转换为红黑树，值为8
4）MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量：64
5）threshold:扩容的临界值，等于容量 * 填充因子：16 * 0.75 =12

获得hash索引后，根据hash索引将数据插入Map中。

如果那个位置无元素那就直接放入
如果那个位置有元素，那就比较是否相同。（判断是否是同一个对象且equals()，（不同类的equals是不同的。具体得看是怎么重写的）为否）

•  相同就直接放弃
•  不同就继续对比这个位置的链表中的元素，直到链表末尾都不同就放在最后。
  
  元素添加到链表后，如果长度大于等于8。
• 数组长度大于等于64，树化该位置的链表
• 否则就扩容数组。

而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

​

 详情可见：http://t.csdn.cn/VUVLx

http://t.csdn.cn/v5Gaf