物流信息平台网站建设,wordpress 主题 结构,网页做成软件,潜江seoJava 集合概览
Java 集合#xff0c;也叫作容器#xff0c;主要是由两大接口派生而来#xff1a;一个是 Collection接口#xff0c;主要用于存放单一元素#xff1b;另一个是 Map 接口#xff0c;主要用于存放键值对。对于Collection 接口#xff0c;下面又有三个主要的…Java 集合概览
Java 集合也叫作容器主要是由两大接口派生而来一个是 Collection接口主要用于存放单一元素另一个是 Map 接口主要用于存放键值对。对于Collection 接口下面又有三个主要的子接口List、Set 、 Queue 图中只列举了主要的继承派生关系并没有列举所有关系。比方省略了AbstractList, NavigableSet等抽象类以及其他的一些辅助类如想深入了解可自行查看源码 List, Set, Queue, Map 四者的区别 List(对付顺序的好帮手): 存储的元素是有序的、可重复的 Set(注重独一无二的性质): 存储的元素不可重复的 Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序存储的元素是有序的、可重复的 Map(用 key 来搜索的专家): 使用键值对key-value存储类似于数学上的函数 yf(x)x 代表 keyy 代表 valuekey 是无序的、不可重复的value 是无序的、可重复的每个键最多映射到一个值
集合框架底层数据结构总结
List ArrayListObject[] 数组。详细可以查看ArrayList 源码分析 VectorObject[] 数组 LinkedList双向链表(JDK1.6 之前为循环链表JDK1.7 取消了循环)。详细可以查看LinkedList 源码分析
Set HashSet(无序唯一): 基于 HashMap 实现的底层采用 HashMap 来保存元素 LinkedHashSet: LinkedHashSet 是 HashSet 的子类并且其内部是通过 LinkedHashMap 来实现的 TreeSet(有序唯一): 红黑树(自平衡的排序二叉树)
Queue PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看PriorityQueue 源码分析 DelayQueue:PriorityQueue。详细可以查看DelayQueue 源码分析 ArrayDeque: 可扩容动态双向数组
Map HashMapJDK1.8 之前 HashMap 由数组链表组成的数组是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的“拉链法”解决冲突。JDK1.8 以后在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为 8将链表转换成红黑树前会判断如果当前数组的长度小于 64那么会选择先进行数组扩容而不是转换为红黑树时将链表转化为红黑树以减少搜索时间。详细可以查看HashMap 源码分析 LinkedHashMapLinkedHashMap 继承自 HashMap所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外LinkedHashMap 在上面结构的基础上增加了一条双向链表使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作实现了访问顺序相关逻辑。详细可以查看LinkedHashMap 源码分析 Hashtable数组链表组成的数组是 Hashtable 的主体链表则是主要为了解决哈希冲突而存在的 TreeMap红黑树自平衡的排序二叉树
如何选用集合
当我们需要存储一组类型相同的数据时数组是最常用且最基本的容器之一。但是使用数组存储对象存在一些不足之处因为在实际开发中存储的数据类型多种多样且数量不确定。这时Java 集合就派上用场了。与数组相比Java 集合提供了更灵活、更有效的方法来存储多个数据对象。Java 集合框架中的各种集合类和接口可以存储不同类型和数量的对象同时还具有多样化的操作方式。相较于数组Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等。总的来说Java 集合提高了数据的存储和处理灵活性可以更好地适应现代软件开发中多样化的数据需求并支持高质量的代码编写
List
ArrayList 和 Array数组的区别
ArrayList 内部基于动态数组实现比 Array静态数组 使用起来更加灵活 ArrayList会根据实际存储的元素动态地扩容或缩容而 Array 被创建之后就不能改变它的长度了 ArrayList 允许你使用泛型来确保类型安全Array 则不可以 ArrayList 中只能存储对象。对于基本类型数据需要使用其对应的包装类如 Integer、Double 等。Array 可以直接存储基本类型数据也可以存储对象 ArrayList 支持插入、删除、遍历等常见操作并且提供了丰富的 API 操作方法比如 add()、remove()等。Array 只是一个固定长度的数组只能按照下标访问其中的元素不具备动态添加、删除元素的能力 ArrayList创建时不需要指定大小而Array创建时必须指定大小
ArrayList 和 Vector 的区别?了解即可 ArrayList 是 List 的主要实现类底层使用 Object[]存储适用于频繁的查找工作线程不安全 Vector 是 List 的古老实现类底层使用Object[] 存储线程安全
Vector 和 Stack 的区别?了解即可 Vector 和 Stack 两者都是线程安全的都是使用 synchronized 关键字进行同步处理 Stack 继承自 Vector是一个后进先出的栈而 Vector 是一个列表 随着 Java 并发编程的发展Vector 和 Stack 已经被淘汰推荐使用并发集合类例如 ConcurrentHashMap、CopyOnWriteArrayList 等或者手动实现线程安全的方法来提供安全的多线程操作支持 ArrayList 可以添加 null 值吗
ArrayList 中可以存储任何类型的对象包括 null 值。不过不建议向ArrayList 中添加 null 值 null 值无意义会让代码难以维护比如忘记做判空处理就会导致空指针异常
ArrayListString listOfStrings new ArrayList();
listOfStrings.add(null);
listOfStrings.add(java);
System.out.println(listOfStrings);
输出
[null, java]
ArrayList 插入和删除元素的时间复杂度
对于插入 头部插入由于需要将所有元素都依次向后移动一个位置因此时间复杂度是 O(n) 尾部插入当 ArrayList 的容量未达到极限时往列表末尾插入元素的时间复杂度是 O(1)因为它只需要在数组末尾添加一个元素即可当容量已达到极限并且需要扩容时则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中然后再执行 O(1) 的操作添加元素 指定位置插入需要将目标位置之后的所有元素都向后移动一个位置然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素因此时间复杂度为 O(n)
对于删除 头部删除由于需要将所有元素依次向前移动一个位置因此时间复杂度是 O(n) 尾部删除当删除的元素位于列表末尾时时间复杂度为 O(1) 指定位置删除需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置因此需要移动平均 n/2 个元素时间复杂度为 O(n)
举例
// ArrayList的底层数组大小为10此时存储了7个元素
------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | |
------------------------------0 1 2 3 4 5 6 7 8 9
// 在索引为1的位置插入一个元素8该元素后面的所有元素都要向右移动一位
------------------------------
| 1 | 8 | 2 | 3 | 4 | 5 | 6 | 7 | | |
------------------------------0 1 2 3 4 5 6 7 8 9
// 删除索引为1的位置的元素该元素后面的所有元素都要向左移动一位
------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | |
------------------------------0 1 2 3 4 5 6 7 8 9
LinkedList 插入和删除元素的时间复杂度 头部插入/删除只需要修改头结点的指针即可完成插入/删除操作因此时间复杂度为 O(1) 尾部插入/删除只需要修改尾结点的指针即可完成插入/删除操作因此时间复杂度为 O(1) 指定位置插入/删除需要先移动到指定位置再修改指定节点的指针完成插入/删除不过由于有头尾指针可以从较近的指针出发因此需要遍历平均 n/4 个元素时间复杂度为 O(n)
假如我们要删除节点 9 的话需要先遍历链表找到该节点。然后再执行相应节点指针指向的更改 LinkedList 为什么不能实现 RandomAccess 接口
RandomAccess 是一个标记接口用来表明实现该接口的类支持随机访问即可以通过索引快速访问元素。由于 LinkedList 底层数据结构是链表内存地址不连续只能通过指针来定位不支持随机快速访问所以不能实现 RandomAccess 接口
ArrayList 与 LinkedList 区别 是否保证线程安全 ArrayList 和 LinkedList 都是不同步的也就是不保证线程安全 底层数据结构 ArrayList 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构JDK1.6 之前为循环链表JDK1.7 取消了循环。注意双向链表和双向循环链表的区别下面有介绍到 插入和删除是否受元素位置的影响 ArrayList 采用数组存储所以插入和删除元素的时间复杂度受元素位置的影响。 比如执行add(E e)方法的时候 ArrayList 会默认在将指定的元素追加到此列表的末尾这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话add(int index, E element)时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作 LinkedList 采用链表存储所以在头尾插入或者删除元素不受元素位置的影响add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()时间复杂度为 O(1)如果是要在指定位置 i 插入和删除元素的话add(int index, E element)remove(Object o),remove(int index) 时间复杂度为 O(n) 因为需要先移动到指定位置再插入和删除 是否支持快速随机访问 LinkedList 不支持高效的随机元素访问底层是链表结构只支持使用指针访问而 ArrayList实现了 RandomAccess 接口 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法) 内存空间占用 ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间因为要存放直接后继和直接前驱以及数据
我们在项目中一般是不会使用到 LinkedList 的需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替并且性能通常会更好就连 LinkedList 的作者约书亚 · 布洛克Josh Bloch自己都说从来不会使用 LinkedList 不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)其他情况增删元素的平均时间复杂度都是 O(n)
双向链表和双向循环链表
双向链表 包含两个指针一个 prev 指向前一个节点一个 next 指向后一个节点 双向循环链表 最后一个节点的 next 指向 head而 head 的 prev 指向最后一个节点构成一个环 RandomAccess 接口
public interface RandomAccess {
}
查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以在我看来 RandomAccess 接口不过是一个标识罢了。标识什么 标识实现这个接口的类具有随机访问功能。
在 binarySearch() 方法中它要判断传入的 list 是否 RandomAccess 的实例如果是调用indexedBinarySearch()方法如果不是那么调用iteratorBinarySearch()方法 public static Tint binarySearch(List? extends Comparable? super T list, T key) {if (list instanceof RandomAccess || list.size()BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list, key);elsereturn Collections.iteratorBinarySearch(list, key);}
ArrayList 实现了 RandomAccess 接口 而 LinkedList 没有实现。为什么呢我觉得还是和底层数据结构有关ArrayList 底层是数组而 LinkedList 底层是链表。数组天然支持随机访问时间复杂度为 O(1)所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素时间复杂度为 O(n)所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口就表明了他具有快速随机访问功能 RandomAccess 接口只是标识并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能
