1.List

ArrayList：

• 底层实现是一个数组，
• 默认大小 10，满了以后会扩容，扩容系数是1.5
• 查询复杂度0(1)

底层是数组:

• 支持随机访问（顺序访问：需要从第一个数据依次访问；随机访问：通过索引直接访问数据）
• 数组在内存中是一块连续的区域，等于知道了每一个数据的内存地址
• 使用数组的时候需要提前申请一块连续的内存空间，这样容易导致内存浪费
• 插入的时候需要将插入位置后的数据整体往后移动，删除的时候需要删除位置后面的数据整体往前移动，增删效率很差

总结：数组可能浪费内存空间，查找效率快，但是插入删除效率慢

LinkedList：

• 底层是双向链表，
• 链表不需要一块连续的内存空间，每一个数据都保存了下一个数据的内存地址
• 双向链表的好处是不用扩容，可以一直追加，
• 坏处是我要寻找第n个元素的时候他的时间复杂度是O(n)，因为他要从第一个元素遍历到第n个元素

底层是链表：

• 链表不需要连续的内存空间，只是在相邻的节点记录了地址，插入和删除的时候只需要修改对应节点的地址，其他节点不需要改动
• 链表只能支持顺序访问

总结：链表不会浪费内空间，插入删除快，查找慢

2.Map

HashMap:

• 底层实现同样是个数组，
• 数组的大小必须是2的幂次方倍，原因是他在取hash下标的时候，用了size-1&当前hash值的操作，所以他必须是2的幂次方倍(下面源码部分有详细讲——————–)
• 数组每个元素是一个链表，因为HashMap在进行存储的时候，如果出现了下标一样，也就是Hash冲突，这样如果是一个链表的话，我就可以往后面追加，
• JDK8之后，链表追加到一定长度会变成红黑树，这个时候会考察红黑树是什么（后续补充——————-）

底层不是单一的数据结构：
数组+链表的结构，图中每一个结构代表一个键值对，


key是一个对象，而数组是通过int角标取值，为了方便查找，对key进行hash()得到一个int值，
将这个key对应的键值对对象存到数组对应的hash值的位置，
以后查找的时候就只需要对key进行hash()然后找到数组对应的位置

hash()碰撞？

如果hash()后对应的索引有值了，而且key不相等，就会通过链表方式叠加起来。

内存占用问题：hash()的取值范围多大？

数组是需要提前申请内存空间的，int的范围是-2147483648~2147483647，很小的数据不可能也存这么大的空间，可以限制范围在0-999，对hash()的结果对1000取模。这样不同的hash()值也会存到相同的数组节点中，所以为了方便查找，可以把哈希值也存到链表结构中，因为两个哈希值比较比两个对象比较要方便得多。

jdk1.7的源码关键点：

构造方法入手，再看put方法（主要），再看get方法（就是put的一部分）
1.entry结构，跟图上对应起来了

2.初始是16，数组长度是与数据接近的2的幂次方，然后临界值是0.75，数据超过75%，也就是12的时候就发生第一次扩容
3.HashMap支持null，会存到索引为0的位置，因为null对象不能hash()
4.modCount，遍历的时候会记录数量，如果迭代器遍历的时候数量发生改变，说明有多个线程操作HashMap，会主动抛出异常
5.为什么HashMap长度要是2的整数次幂？

因为哈希过程中巧妙地运用与运算取模

6.HashMap是不是直接使用的hash()?
h，jvm没有设置的话，直接为0，if不走
0异或等于hash()，异或就是00、11->0，10、01->1
后面的位移是二次hash，让更多的hash为参与到最终有效范围的结果运算，以此减少产生碰撞的几率。

7.找到要存的数组角标地址后，会遍历链表，看是否已有元素，判断的优先级：先看hash值是否一样，再判断key的地址值或key是否相等。有的话直接改值，没有就添加新的元素。

8.添加新元素
先判断要不要扩容：数量超过临界条件，而且要存的地方已经有值了

添加元素：把新的元素放在了头部

9.达到扩容条件

传入数组长度两倍的值

如果就数组长度达到上限（2的30次方），就会把阈值设为int最大值
没有就传入两倍大小的数组，第二个参数代表是否需要重新hash，默认为false

用保存的hash值重新计算节点后，头插法插到新数组中，链表中的数据有部分被反转了

jdk1.8的源码关键点：

1.hash更简单了

2.resize变复杂了，扩容和初始化都在一块，转移也在扩容里面
3.1.8链表节点用的是尾插法
4.除了链表节点， 多了一种红黑树节点，

5.分析put过程

6.链表长度超过8的时候，树化的过程（未完）


7.resize()扩容的过程（未完）

LinkedHashMap：

• 底层实现和HashMap几乎是一模一样的，
• 只不过LinkedHashMap在每一个链表元素加了一个指针，指向下一个插入的元素（——-）
• 这样就相当于给HashMap增加了一个链表，链表维系了数据插入的顺序
• 可以在遍历的时候，按照数据插入的顺序遍历每个元素

TreeMap：

• 底层用红黑树实现的
• 特点是按照Key进行排序

HashTable：

• HashTable是线程安全的，HashMap是线程不安全的
• 线程安全的实现：
• 在被线程操作的时候，尤其是写操作的时候，会将整个存储结构锁住，然后导致其他存储结构无法被其他线程操作，等这个写线程操作完以后，其他线程才可以操作

ConcurrentHashMap：

• HashTable锁住整个数据结构的代价是比较大的，ConcurrentHashMap是对HashTable的改进。
• 他是只锁住这个桶，就是数组中单个元素的链表

3.Set

HashSet，TreeSet都是基于HashMap，TreeMap，LinkedHashMap实现的，只不过只用了Map的key，value设为null了，所以set没什么技术含量

课1：www.bilibili.com/video/BV15J…
课2：ke.qq.com/webcourse/i…