笔记（三） - Java集合

Li_XiaoJin

发布于 2022-06-10 20:13:07

2630

发布于 2022-06-10 20:13:07

以下主要是关于Java集合的相关知识。

1.List, Set, Map 的区别

1、List、Set都是继承Collection接口；List有序且可以有重复元素；Set无序且不能有重复元素 2、List：一个有序集合，可以存储一组不唯一（可以有多个元素引用相同的对象）、有序的对象； 该集合用户可以精准控制每个元素的插入位置，可以通过索引访问元素，并且搜索列表的元素。

3、Set：不允许重复的集合，不会有多个元素引用相同的对象。（不包含重复元素）

4、Map：使用键值对存储，两个Key可以引用相同的对象，但Key不能重复。

2.ArrayList 与 LinkedList 的区别

1、是否保证线程安全：ArrayList 和 LinkedList 都不是同步的，不保证线程安全

2、底层数据结构：ArrayList底层使用的是数组，LinkedList底层使用的是双向链表数据结构

3、插入、删除是否受元素位置的影响：

（1）ArrayList采用的是数组结构，插入和删除的时间复杂度受元素位置的影响

（2）LinkedList采用链表存储，对于add(E e)方法插入时，删除元素的时间复杂度不受元素位置的影响，近似O(1)；如果需要在指定位置插入和删除元素的话，时间复杂度近似O(n)，因为需要移动到指定位置再插入；

4、是否支持快速随机访问：快速随机访问就是通过元素的序号快速获取元素的对象；LinkedList不支持高效的随机元素访问，ArrayList支持。

5、内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费体现在每个元素都需要消耗比ArrayList更多的空间（LinkedList需要存放直接后继和直接前驱以及对应的数据）

综上，ArrayList的查询速度较快，适合查询较多的场景；LinkedList插入、删除较快，适合用在需要频繁删除和插入的场景。（ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况）

关于 List，以前收藏了一篇文章，说得很好，很容易理解，值得一看https://lixj.fun/archives/2020-04-30-11-56-32/password

查看Java API文档，可以看到 ArrayList 实现了 RandomAccess 接口，而这个接口中没有定义任何方法，只是表示一个标识，表示它支持随机访问。RandomAccess 接口只是一个标识，并不是说 ArrayList 实现了 RandomAccess 接口才支持随机访问的。

查看API文档，可以看到，List实现使用的标记界面，表明它们支持快速（通常为恒定时间）随机访问。此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能

通过以上可以看，ArrayList支持随机访问，使用for循环比使用Iterator运行的更快。可以得出结论， 1）实现了 RandomAccess 接口的list：优先使用for循环，其次是foreach 2）未实现 RandomAccess 接口的list：优先选择Iterator遍历

foreach的底层也是通过Iterator实现的，对于size很大的数据，千万不要使用普通的for循环

  for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

  for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();

关于链表 (改天可以深入研究)双向链表：包含两个指针，一个prev指向前一个节点，一个next指向后一个节点

双向循环链表：最后一个节点的next指向head，head的prev指向最后一个节点，构成一个环

3. ArrayList 的扩容机制

这个问题需要分析源码，我另外写了个文章分析。点击阅读 ArrayList 的扩容机制

4.ArrayList 和 Vector 的区别

Vector类的所有方法都是同步的。可以由两个线程安全的访问一个Vector对象，但一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 ArrayList不是同步的，在不需要保证线程安全的情况时建议使用ArrayList

Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

5.HashMap 和 HashTable 的区别

1、是否线程安全：HashMap是非线程安全的，HashTable是线程安全的。HashTable内部方法基本都经过synchronized修饰，如果要保证线程安全，建议使用ConcurrentHashMap 2、HashTable基本被淘汰，不建议使用。HashMap比HashTable效率高。 3、HashMap中，null可以作为键，而且只能有一个键为null，可以有一个或多个键所对应的值为null。HashTable中只要有put的键值为null，就会抛出空指针异常。 4、jdk8后HashMap底层使用数据+链表+红黑树的结构

6.HashMap 和 HashSet 的区别

1、HashSet底层是基于HashMap实现的，除了clone(),writeObject(),readObject()是自己不得不实现外，其他都是直接调用HashMap的方法。 2、HashMap实现了Map接口，使用键值对存储，调用put()往map中添加元素，HashMap使用key计算hashcode 3、HashSet实现了Set接口，仅存储对象，调用add()向set中添加元素，HashSet使用成员对象来计算hashcode值，两个对象的hashcode可能会相等，通过equals来判断对象是否相等

7.HashMap 的底层实现

后面单独写个文章分析

8.HashMap 的长度为什么是2的幂次方

为了能让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀。

9.HashMap多线程操作导致死锁循环

主要原因是在并发情况下Rehash会造成元素之间会形成一个循环链表。并发环境下建议使用ConcurrentHashMap

10.ConcurrentHashMap 的底层实现

可以参考：https://www.cnblogs.com/chengxiao/p/6842045.html

11.ConcurrentHashMap 和 HashTable 的区别

1、底层数据结构：

（1）ConcurrentHashMap 在jdk1.7采用分段的数组+链表实现，jdk1.8采用和HashMap一样的结构，数据+链表/红黑树。

（2）HashTable采用的是数组+链表结构。

2、实现线程安全的方式：

（1）jdk1.7的ConcurrentHashMap对整个桶数组进行了分割分段（Segment），每把锁只锁容器中的一部分数据，多线程访问容器的不同数据段的数据，不会存在锁竞争，可以提高并发的效率

（2）jdk1.8时，不再使用Segment的概念，换为使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。

（3）HashTable使用同一把锁，通过使用synchronized来保证线程安全。对整个方法进行加锁，效率很低，当有一个线程访问同步方法时，如果有其他线程也访问同步方法，可能会进入阻塞状态或轮询状态。如使用put添加元素，另一个线程就不能put元素，也不能通过get获取元素，最后会导致竞争越来越激烈。

12.Comparable 和 Comparator 的区别

Comparable 接口出自java.lang包，有一个compareTo(Object obj)方法来实现排序 Comparable 接口出自java.util包，有一个compare(Object obj1, Object obj2)来实现排序 Comparator 可以自定义排序方法， Collection.sotr()