黑龙江电商网站建设,wordpress 水果主题,2022年进口博览会上海,河北住房和城乡建设厅网站6Java 集合#xff0c;也叫做容器#xff0c;主要是由两大接口派生而来#xff1a;一个是 Collection 接口#xff0c;主要用于存放单一元素#xff1b;另一个是 Map 接口#xff0c;主要用于存放键值对。对于 Collection 接口#xff0c;其下又有三个主要的子接口#…Java 集合也叫做容器主要是由两大接口派生而来一个是 Collection 接口主要用于存放单一元素另一个是 Map 接口主要用于存放键值对。对于 Collection 接口其下又有三个主要的子接口List、Set、Queue。
目录
Java 集合框架
1List、Set、Queue、Map的区别是什么
List
Set
Queue
Map
2集合的底层数据结构都是什么
List
Set
Queue
Map
* 拓展为什么将插入链表的方式进行更改
3如何选用集合
4为什么要使用集合
5ArrayList 和 Vector 的区别
6ArrayList 和 LinkedList
7双向链表和双向循环链表1.6 1.7 LinkedList
8RandomAccess 接口
9ArrayList 的扩容机制是怎么样的
10comparable 和 Comparator 的区别
11无序性和不可重复性的含义是什么
无序性
不可重复性
12HashSet、LinkedHashSet、TreeSet三者有何异同
13Queue 和 Deque 有什么区别
14ArrayDeque 和 LinkedList 的区别是什么
15你知道 PriorityQueue 吗
16HashMap 和 Hashtable 的区别是什么
为什么 HashMap 的长度为什么需要是2的幂次方
17HashMap 和 HashSet 有什么区别
18HashMap 和 TreeMap 有什么区别
19HashSet 如何检查重复
20HashMap 的底层实现
1.8之前
1.8之后
21HashMap 多线程操作导致死循环问题
22HashMap 有哪几种常见的遍历方式
23ConcurrentHashMap 和 Hashtable 的区别是什么
ConcurrentHashMap
Hashtable
24ConcurrentHashMap 线程安全的具体实现方法 / 底层具体实现
1.8 之前
1.8 之后 Java 集合框架
列举主要继承和派生关系并未全部列出 1List、Set、Queue、Map的区别是什么
List
有序的可重复的。类似于数组
Set
无序的、不可重复的。类似于集合数学上
Queue
队列一般是FIFO。
Map
key-value 键值对存储。key 无序的不可重复的value 无序的可重复的。每个 key 最多映射到一个 value 上。 2集合的底层数据结构都是什么
List
1、ArrayList底层是数组 Object[]
2、LinkedList底层是双向链表1.6之前是循环链表1.7之后取消循环
3、Vector底层是数组 Object[] Set
1、HashSet无序、唯一基于 HashMap 实现底层通过 HashMap 保存数据
2、LinkedHashSetHashSet 的子类内部通过 LinkedHashMap 实现。
3、TreeSet有序、唯一红黑树自平衡的二叉排序树 Queue
1、ArrayQueue底层是数组 Object[] 双指针
2、PriorityQueue优先队列底层是数组 Object[] 来实现二叉堆 Map
1、HashMap
1.8 之前是数组 链表通过“拉链法”解决哈希冲突拉链法即创建一个链表数组当发生哈希冲突的时候直接将其加入链表即可。在1.8之前将元素插入链表使用的是头插法。
1.8之后使用数组 链表 红黑树当链表长度大于一个阈值默认为8将链表转换为红黑树之前会进行判断如果数组长度小于64会优先对数组进行扩容如果长度大于64则进行转换时将链表转换为红黑树以减小搜索时间。在1.8之后将元素插入链表使用的是尾插法。 2、Hashtable数组 链表
3、LinkedHashMap
LinkedHashMap 继承 HashMap它的底层仍然是基于拉链式散列结构即由数组和链表或红⿊树组成。另外LinkedHashMap 在上面结构的基础上增加了一条双向链表使得上面的结构可以保持键值对插入的顺序。同时通过对链表进行相应的操作实现了访问顺序相关逻辑。 每当有新键值对节点插入新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上这样一个双向链表就建立起来了。 * 拓展为什么将插入链表的方式进行更改
答1、扩容会导致链表的顺序被反转
2、头插法可能导致链表环形问题这个问题会导致 CPU 使用率 100% 或者死循环问题。多线程情况下 3如何选用集合
我们主要根据集合的特点进行选择
比如我们需要键值对进行存储选用的肯定是 Map 接口下的集合。需要排序的时候选用 TreeMap不需要排序的时候选 HashMap保证线程安全使用 ConcurrentHashMap。
比如我们只需要存放值的之后选择 Collection 接口下的集合需要保证元素唯一的时候选择 Set下的 TreeSet 或 HashSet不要则选择 List 下的 ArrayList 或者 LinkedList。 4为什么要使用集合
当我们需要保存一组类型相同的数据的时候我们选用数组进行存储
而在实际开发过程中我们需要存储的数据类型往往是多样的所以就出现了“集合”它可以存储不同类型的数据。
而且数组在声明之后长度不可变这在开发中非常不方便因为有些时候你不知道你需要存储多少数据而使用集合基本不存在这样的问题它的存储非常灵活它可以存储不同类型不同数量的对象并且可以保存 key - value 关系的数据。 5ArrayList 和 Vector 的区别
ArrayList 是 List 的主要实现类它的底层是数组 Object[]适合于频繁的查找工作但是线程不安全性能更好。在扩容的时候容量变为原来的1.5倍。
Vector 是 List 的古老实现类它的底层是数组 Object[]线程安全性能较低。在扩容时容量变为原来的2倍。
更现代的线程安全 List 实现类CopyOnWriteArrayList需要线程安全的时候用这个 6ArrayList 和 LinkedList
1、线程安全它们都是不同步的也就是都不是线程安全的。
2、底层数据结构ArrayList 底层是数组LinkedList 底层是双向链表。1.6之前是循环链表
3、插入和删除
ArrayList 默认插入到尾部时间复杂度是O(1)如果插入到位置 i 时间复杂度是O(n-i)因为需要移动位置
LinkedList 可以在头尾进行插入和删除此时时间复杂度是O(1)如果需要在指定位置 i 进行插入和删除时间复杂度为O(n)因为要先遍历寻找到位置 i 再进行操作。
4、快速随机访问ArrayList 支持LinkedList 不支持。
5、内存空间占用ArrayList 空间浪费在尾部预留的空间LinkedList 空间浪费在每个元素耗费更多空间。 项目中一般不会用到 LinkedList它的作者 Joshua Bloch 自己说从来不会使用 LinkedList。 - - 7双向链表和双向循环链表1.6 1.7 LinkedList 它们的区别就在于双向循环链表的头节点的 prev 指向尾节点而其尾节点的 next 指向头节点。双向链表头节点的 prev 指向 null尾结点的 next 指向 null。 8RandomAccess 接口
该接口为空它存在的意义就是标识实现这个接口的类有快速随机访问的能力。
例如ArrayList 底层实现了 RandomAccess 接口而 LinkedList 没有实现关键在于它们的底层数据结构不同。ArrayList 本身就可以实现快速随机访问因为其底层是一个 Object 数组。而不是因为其实现了 RandomAccess 。 9ArrayList 的扩容机制是怎么样的
ArrayList 的无参构造方法创建 ArrayList的时候实际上初始化赋值了一个空数组只有当向其中添加元素的时候才会分配空间。
ArrayList 每次扩容后容量会变为原来的1.5倍左右 int new old (old 1);
详见 黑马程序员 10comparable 和 Comparator 的区别
comparable 接口出自 java.lang 包它有一个 compareTo(Object obj) 方法用来排序。
Comparator 接口出自 java.util 包它有一个 compare(Object obj1, Object obj2) 方法用来排序。 当需要对集合进行自定义排序的时候例如对 song 对象 歌名 / 歌手 顺序进行排序的时候我们可以通过重写 comparable 的 compareTo 方法和 使用自制的 Comparator 方法或者以两个 Comparator 来实现排序这种方法代表我们只能使用两个参数版的 Collection.sort()。 定制排序的编写方法
1、comparable对于没有实现 Comparable 接口的类必须实现其才能通过重写 compareTo 方法进行排序 重写方法 2、 Comparator 定制排序 11无序性和不可重复性的含义是什么
无序性
无序性不等于随机性无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加而是根据数据的哈希值进行添加的。
不可重复性
是指添加的元素按照 equals() 进行判断的时候返回值为false。 12HashSet、LinkedHashSet、TreeSet三者有何异同
它们是 Set 接口的三个实现类它们都能保证元素唯一且都不是线程安全的。
它们的区别在于底层的数据结构不同。HashSet 的底层数据结构为 HashMapLinkedHashSet 的底层是 HashMap 和 链表取出元素的顺序满足 FIFOTreeSet 的底层数据结构为红黑树排序的方法有自然排序和定制排序。 13Queue 和 Deque 有什么区别
Queue 是单端队列只能从队尾进行数据的添加队首进行数据的删除。一般满足 FIFO。
Queue 拓展了 Collection 接口根据 因为容量不足而导致的数据操作失败一类方法在失败后会抛出异常一类方法在失败后会返回特殊值。 Deque 拓展了 Queue它是一个双端队列可以从队尾队首任意一端进行数据的添加和删除同样根据数据操作失败后的处理分为两类方法。 Deque 还有 push() 和 pop() 方法可以用来模拟栈。 14ArrayDeque 和 LinkedList 的区别是什么
ArrayDeque 和 LinkedList 都实现了 Deque 接口它们都具有队列的功能。 15你知道 PriorityQueue 吗
PriorityQueue 在 JDK1.5 中被引入它与 Queue 的区别在于队列是 FIFO 的而优先队列先出队的元素是优先级最高的元素。
要点
1、PriorityQueue 利用二叉堆的数据结构进行实现底层使用可变长的数据来存储数据。
2、PriorityQueue 的时间复杂度为 O(logn)即堆排序的时间复杂度。
3、PriorityQueue 不是线程安全的且不能存储 null 和 non-comparable 对象。
4、PriorityQueue 默认是最小堆但可以接收一个 Comparator 参数来自定义排序方法优先级大小。
PriorityQueue 在面试中经常出现于手撕算法中尤其是堆排序、求第K大数等等需要熟练掌握。 16HashMap 和 Hashtable 的区别是什么
1、HashMap 不是线程安全的Hashtable 是线程安全的。
2、HashMap 效率高于 Hashtable因为线程安全问题。
3、HashMap 可以存储 null key 和 null valueHashtable 不支持存储 null key 和 null value。
4、HashMap 默认容量为11每次扩充变成 2n1; Hashtable 默认大小为 16每次扩充变成 2n。
HashMap 如果给定容量它会初始化为 2 的幂次大小Hashtable 会直接使用你给定的大小。
5、HashMap 底层数据结构使用的是数组、链表和红黑树Hashtable 未使用红黑树。 * HashMap 中使用 2 的幂作为哈希表的大小代码。 这里做一下讲解
我们希望使用 2 的幂大小在二进制看来实际上就是使得其最高位的下一位变为1其余都为0除了本身就是 2 的幂大小的数这就是为什么 n 需要先减1
那么我们的做法是这样的
1、第1次将该数右移1位与原数做或运算这样就会有2位变成1
2、第2次将该数右移2位与原数做或运算这样就会有4位变成1
3、第3次将该数右移4位与原数做或运算这样就会有8位变成1
4、第4次将该数右移8位与原数做或运算这样就会有16位变成1
2、第5次将该数右移16位与原数做或运算这样就会有32位变成1
这样就可以保证一个 int 类型的数在 1 之后一定是 2 的幂次大小因为二进制数字如果都是1的话那么他加一后就是首位为1其他位都是0这个数字肯定是 2 的幂次方。
某次过程 当某个数较小的时候后面会有一些多余的运算但效率影响很小。 为什么 HashMap 的长度为什么需要是2的幂次方
为了能让hashMap存取高效尽量减少碰撞也就是要尽量把数据分配均匀。在插入数据之前做取模运算得到的余数就是将要存放的数据在哈希表中对应的下标。在HashMap中这个下标的取值算法是(n - 1) hash n是哈希表的长度。 17HashMap 和 HashSet 有什么区别 18HashMap 和 TreeMap 有什么区别
HashMap 和 TreeMap 都继承自 AbstractMap但是 TreeMap 还实现了 NavigableMap 和 SortedMap 接口。
Navigable 接口让 TreeMap 有了对集合内元素进行搜索的能力
SortedMap 接口让 TreeMap 有了对 key 进行排序的能力默认升序。 Lambda 表达式实现自定义排序 综上TreeMap 相比 HashMap 有了对集合内元素搜索的能力和按照 key 进行排序的能力。 19HashSet 如何检查重复
当把对象加入到 HashSet 中时首先会计算对象的 hashcode 是否存在相同值如果不存在则加入如果存在相同的 hashcode则使用 equals 方法判断它们是否真的一致如果相同HashSet就不会让加入操作成功。 20HashMap 的底层实现
1.8之前
HashMap 底层是 数组和链表 结合在一起实现。
HashMap 通过 key 的 hashcode 经过扰动函数后得到 hash 值再通过 (n - 1) hash 得到 value 需要插入的位置。如果当前位置存在元素的话则比较它们是否相同。如果不同则使用拉链法解决冲突如果相同的话直接进行覆盖。
* 扰动函数
扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法的原因是防止一些实现比较差的 hashcode() 方法产生影响减小碰撞概率。 1.8之后
当链表长度大于阈值默认为8将链表转换为红黑树之前对数组的长度进行判断如果数组长度小于 64 先进行扩容大于 64 才进行红黑树转换时将链表转换为红黑树减少搜索时间。
为什么不使用二叉搜索树
原因二叉搜索树在某种情况下会退化成线性结构而红黑树是一个平衡的二叉搜索树可以避免这种情况。 21HashMap 多线程操作导致死循环问题
这个问题就是前面说的那个 头插法 导致的死循环问题。
在 1.8 之后得到了解决 22HashMap 有哪几种常见的遍历方式
HashMap 有七种遍历方式 1、使用迭代器IteratorEntrySet 的方式进行遍历
public class EntrySet {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);IteratorMap.EntryInteger, String iterator map.entrySet().iterator();while(iterator.hasNext()){Map.EntryInteger, String entry iterator.next();System.out.println(entry.getKey());System.out.println(entry.getValue());}}
} 2、使用迭代器IteratorKeySet 的方式进行遍历
public class KeySet {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);IteratorInteger iterator map.keySet().iterator();while(iterator.hasNext()){Integer key iterator.next();System.out.println(key);System.out.println(map.get(key));}}
} 3、使用 For Each EntrySet 的方式进行遍历
public class foreachEntrySet {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);for(Map.EntryInteger,String entry : map.entrySet()){System.out.println(entry.getKey());System.out.println(entry.getValue());}}
} 4、使用 For Each KeySet 的方式进行遍历
public class foreachKeySet {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);for(Integer key : map.keySet()){System.out.println(key);System.out.println(map.get(key));}}
} 5、使用 Lambda 表达式的方式进行遍历
public class lambda {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);map.forEach((key, value) -{System.out.println(key);System.out.println(value);});}
} 6、使用 Streams API 单线程的方式进行遍历
public class streams1 {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);map.entrySet().stream().forEach((entry) - {System.out.println(entry.getKey());System.out.println(entry.getValue());});}
} 7、使用 Streams API 多线程的方式进行遍历。
public class streams {public static void main(String[] args) {MapInteger, String map new HashMap();map.put(1, Java);map.put(2, JDK);map.put(3, Spring Framework);map.put(4, MyBatis framework);map.entrySet().parallelStream().forEach((entry) - {System.out.println(entry.getKey());System.out.println(entry.getValue());});}
} 性能
可以看出 EntrySet 的执行完成时间最短性能最好然后是 stream 和 keySet性能最差的是 lambda表达式。
结论entrySet 的性能比 keySet 的性能要高出一倍之多所以我们应该尽量使用 entrySet 来进行Map 集合的遍历。 23ConcurrentHashMap 和 Hashtable 的区别是什么
它们都是线程安全的但是在实现线程安全的方式不同。
实现线程安全的方式
ConcurrentHashMap
1.7 的时候ConcurrentHashMap 对整个桶数组进行了分割分段Segment分段锁每一把锁只锁容器内其中一部分数据多线程访问不同数据段内的数据的时候不存在冲突可以提高并发访问率。 1.8 的时候ConcurrentHashMap 摒弃了 Segment转而使用 Node数组 链表 红黑树的数据结构进行实现并发控制使用 synchronized 和 CAS 进行操作。整个就是 HashMap 进行优化且线程安全的升级版本。 Hashtable
也是使用 synchronized 来保证线程安全效率非常低下。当一个线程访问同步方法是另一个线程也访问该方法另一个线程可能进入阻塞或者轮询这会导致竞争越来越激烈效率越来越低。 24ConcurrentHashMap 线程安全的具体实现方法 / 底层具体实现
1.8 之前 首先将数据分为 segment 的段进行存储给每一段数据都配一把锁当其中一个线程占用锁访问一段数据的时候其他段的数据可以被访问。
数据结构Segment 数组 和 HashEntry 数组
Segment 集成了 ReentrantLock所以 Segment 是一种可重入锁。HashEntry 用于存储键值对数据。 一个 ConcurrentHashMap 包含一个 Segment 数组该数组默认大小为 16也就是默认最高可并发线程数为 16并发写。
Segment 的结构和 HashMap 类似是一种由数组和链表结构一个 Segment 包含一个 HashEntry 数组每个 HashEntry 数组保存链表元素。每个 Segment 守护对应的 HashEntry 数组。这也就是说对 HashEntry 数组内的元素进行修改的时候首先获得对应的 Segment 的锁。 1.8 之后 ConcurrentHashMap 取消了 Segment 分段锁采用 Node CAS synchronized 来保证并发安全数据结构和 HashMap 1.8 的结构类似。Java 8 中锁的粒度更细synchronized 只锁定当前链表或红黑树的首节点这样只要 hash 不冲突就不会发生并发就不会影响其他 Node 的读写效率大幅提升。
