Java集合

集合体系图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UERzyuov-1590064090593)(C:Users25220AppDataRoamingTyporatypora-user-imagesimage-20200521201714798.png)]

1.ArrayList底层实现

• 底层通过数组实现，通过无参构造实例化后，默认初始化数组长度为10
• 扩容：超过10个后，重新生成一个新的数组，为原来的1.5倍，将原来的数据复制到新数组后，再添加。
• 扩容数组调用的方法： Arrays.copyOf(objArr, objArr.length + 1)

2.LinkedList底层实现

• 由链表实现（每个节点=数据+指针），头节点不放数据
• header（头结点），size（节点的个数），每个节点对应一个Entry实例（previous，next，element）
• 不存在容量不足问题
• LinkedList底层的扩容函数,是将所有数据克隆到一个新的LinkedList中

3.HashMap底层实现

jdk1.7：

• key value形式，key可以为null

• 数组+链表

• 由hash表结构实现

• 负载因子：0.75

• 初始容量：16===2^4

• 为甚么会出现哈希碰撞：hash值最大为int的最大值，有限，所以总会有元素不同，hash值相同的情况

• set时，根据哈希算法算出存放的位置bucket（ h & (length-1)，尽量保证每个位置都存放数据，保证散列性），然后插入到链表的头结点（效率高，插入到尾节点的话需要遍历），然后把头结点移动到bucket位置（方便get，不然get的时候上下都得遍历）

• get时，根据hash值找到bucket，然后遍历链表通过key的equals找到指定的元素

• 扩容机制：超过超过阈值（数据存储的位置数量>集合容量*0.75）就会触发扩容，扩大两倍（保证散列性），需要重新使用hash算法，对所有元素重新进行存放，非常消耗性能。同时可能在扩容的过程会出现死锁问题（多线程环境下，因为采用的是头插入法，看图），在创建时尽量确定容量，避免扩容

• 为什么扩大两倍：0001 1111这个时候，原来的数据如果倒数第5位2进制为0，则在原位置不变，如果是1的话，那就会放到扩容的位置进行存储，保证了散列性

• 如果你自己初始化容量，底层会自动给你增加到2的整数倍，为了保证散列性

  

jdk1.8

• 数组+链表+红黑树
• 如果链表异常，那么查询还是很慢，所以一旦链表长度增加到8时，就会变成红黑树。当长度减少到6时，又会重新变成链表（不然插入数据太慢了），树形化的条件不是单纯的链表长度大于8，还得要求是容量不能小于64，否则会用扩容手段减少链表长度。
• 加红黑树的目的就是为了保证插入和查询速度的相对平衡
• 插入数据时插在尾节点，因为反正要遍历判断是否会变成红黑树，插到尾节点只是顺手的事
• 简化了hash算法
• （relize）扩容的逻辑改了，不会出现死锁（死循环的问题了），因为是从尾部插入，循环的时候不会出现问题
• hashMap最多存够存储多少键值对：数组下标是由Int表示的。所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂，也就是2^30,但是键值对可以存很多，因为有链表+红黑树在维护

4.HashMap为什么线程不安全

• jdk1.7:死循环（环形链）

• jdk1.8:put时数据覆盖

5.HashMap,conCurrentHashMap,hashTable的使用

• hashMap:线程不安全

• ConcurrentHashMap：线程安全，相比于HashTable同步性能更好，因为它仅仅根据同步级别对 map 的一部分进行上锁。

• hashTable:提供更强的线程安全性,但是性能不如ConcurrentHashMap

6.HashSet原理

底层通过HashMap来存储数据，可以进行去重，线程不安全

7.ArrayList与Vector

• ArrayList线程不安全
  HashSet原理

底层通过HashMap来存储数据，可以进行去重，线程不安全

7.ArrayList与Vector

• ArrayList线程不安全
• Vector线程安全，底层方法用Sychronized修饰的，性能不如ArrayList