java行列基础知识



目录

数组和集合的区别

Java中的集合

线程安全的集合

java.util.concurrent 包

Collections和Collection的区别

集合遍历的方法

list的几种实现

把ArrayList变成线程安全有哪些方法

为什么ArrayList不是线程安全的

ArrayList的扩容机制

CopyonWriteArraylist是如何实现线程安全

HashMap实现原理

哈希冲突解决方法

HashMap是线程安全的吗？

hashmap的put过程

HashMap的put(key,val)和get(key)过程

hashmap 调用get方法一定安全吗？

为啥String适合做Key呢？

为什么HashMap要用红黑树

HashMap   key可以为null吗？

重写HashMap的equal和hashcode方法需要注意什么？

HashMap在多线程下可能会出现的问题？

HashMap的扩容机制

Hashmap和Hashtable有什么不一样的

ConcurrentHashMap怎么实现

已经用了synchronized，为什么还要用CAS呢

Set集合有什么特点？如何实现key无重复的？

有序的Set是什么

数组和集合的区别

• 数组是固定长度的数据结构，而集合是动态长度的数据结构
• 数组可以包含基本数据类型和对象，而集合只能包含对象。
• 数组可以直接访问元素，而集合需要通过迭代器或其他方法访问元素。

Java中的集合

List是有序的Collection，用户能根据索引访问List中元素。常用的实现List的类有LinkedList，ArrayList，Vector，Stack。

• ArrayList是容量可变的非线程安全的列表，其底层使用数组实现。当几何扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。
• LinkedList本质是一个双向链表，其插入和删除速度更快，但随机访问速度更慢。
• Vector - 是一个动态数组，支持同步操作，适合多线程环境。

Set不允许存在重复的元素。常用的实现有HashSet，LinkedHashSet和TreeSet。

• HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。
• LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
• TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Map 是一个键值对集合。Key 无序，唯一；Value 不要求有序，允许重复。Map 没有继承于 Collection 接口。主要实现有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap 

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• HashTable：数组+链表组成的，线程安全的哈希表
• TreeMap：红黑树（自平衡的排序二叉树）
• ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

线程安全的集合

Vector：线程安全的动态数组，其内部方法基本都经过synchronized修饰

Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值

java.util.concurrent 包

• ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在JDK1.7，ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在JDK 1.8 ，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
• ConcurrentSkipListMap：实现了一个基于SkipList（跳表）算法的可排序的并发集合，SkipList是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的“跳跃”链接来实现高效查找。

• ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现。
• CopyOnWriteArraySet：是线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过“散列表”实现的，而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。

• CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作（add，set等）都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。

• ConcurrentLinkedQueue：是一个适用于高并发场景下的队列，它通过无锁的方式(CAS)，实现了高并发状态下的高性能。通常，ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。
• BlockingQueue：BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。

• LinkedBlockingDeque：是一个线程安全的双端队列实现。LinkedBlockingDeque 没有进行读写锁的分离，因此同一时间只能有一个线程对其进行操作
• ConcurrentLinkedDeque：ConcurrentLinkedDeque是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque是一个合适的选择

Collections和Collection的区别

Collections 是Java提供的一个工具类，位于java.util包中。类中的方法包括排序、查找、替换、反转、随机化等等。

Collection是Java集合框架中的一个接口

集合遍历的方法

• 普通 for 循环。

• 增强 for 循环

• Iterator 迭代器java行列基础知识：特别适用于需要删除元素的情况。

• ListIterator 列表迭代器： ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。

• 使用 forEach 方法： Java 8引入了 forEach 方法

• Stream API

list的几种实现

Vector 是 Java 早期提供的线程安全的动态数组，Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。

ArrayList 应用动态数组实现，它本身不是线程安全的，Vector 在扩容时会提高 1 倍，而 ArrayList 则是增加 50%。适用于需要频繁访问集合元素的场景。

LinkedList 是 Java 提供的双向链表，也不是线程安全的。适用于频繁进行插入和删除操作的场景。

把ArrayList变成线程安全有哪些方法

• 使用Collections类的synchronizedList方法将ArrayList包装成线程安全的List：

• 使用CopyOnWriteArrayList类代替ArrayList，它是一个线程安全的List实现：

• 使用Vector类代替ArrayList，Vector是线程安全的List实现：

为什么ArrayList不是线程安全的

在高并发添加数据下，ArrayList会暴露三个问题;

• 部分值为null（我们并没有add null进去）   //线程2也来执行了，又把数组下标索引为9的位置set了一遍，这时候两个先后进行size++，导致下标索引10的地方就为null
• 索引越界异常   //这时候线程2再进来size就是10，数组的大小只有10，而你要设置下标索引为10的就会越界
• size与我们add的数量不符   //线程1和线程2拿到一样的size值加完了同时覆盖，就会导致一次没有加上

ArrayList的扩容机制

• 计算新的容量：一般情况下，新的容量会扩大为原容量的1.5倍（在JDK 10之后，扩容策略做了调整），然后检查是否超过了最大容量限制。
• 创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。
• 将元素复制：将原来数组中的元素逐个复制到新数组中。
• 更新引用：将ArrayList内部指向原数组的引用指向新数组。
• 完成扩容：扩容完成后，可以继续添加新元素。

为了减少扩容带来的性能损耗，可以在初始化ArrayList时预分配足够大的容量，避免频繁触发扩容操作。之所以扩容是 1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

CopyonWriteArraylist是如何实现线程安全

使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

在写入操作时，加了一把互斥锁ReentrantLock以保证线程安全。

写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度+1后就得到了一个新数组，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址

读是没有加锁的，所以读是一直都能读

HashMap实现原理

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上

在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换使用红黑树，查找时间复杂度O（log n），但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

哈希冲突解决方法

• 链接法：用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
• 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，常见的开放寻址方法包括线性探测、二次探测和双重散列。
• 再哈希法（Rehashing）：使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
• 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap是线程安全的吗？

• JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。

• JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。

• 多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。

• ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Segment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题

hashmap的put过程

第一步：根据要添加的键的哈希码计算在数组中的位置

第二步：检查该位置是否为空，如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数（modCount）加1，以便在进行迭代时发现并发修改。

第三步：如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。

第四步：如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键，

如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
• 如果没有找到相同的键，则将新的键值对添加到链表的头部。

如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
• 如果没有找到相同的键，则将新的键值对添加到红黑树中。

第五步：检查链表长度是否达到阈值（默认为8）：且HashMap的数组长度大于等于64，则会将链表转换为红黑树

第六步：检查负载因子是否超过阈值（默认为0.75）大于阈值，则需要进行扩容操作。

第七步：扩容操作：

• 创建一个新的两倍大小的数组。
• 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
• 更新HashMap的数组引用和阈值参数

HashMap的put(key,val)和get(key)过程

• 存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
• 获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

hashmap 调用get方法一定安全吗？

空指针异常（NullPointerException）：如果你尝试用  作为键调用  方法，而  没有被初始化（即为 ），那么会抛出空指针异常。

在一个线程中调用  方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出 

为啥String适合做Key呢？

因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性

为什么HashMap要用红黑树

平衡二叉树追求的是一种 “完全平衡” 状态

红黑树追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。

HashMap   key可以为null吗？

当key为空时，直接另key的哈希值为0

null作为key只能有一个，null作为value可以有多个；

重写HashMap的equal和hashcode方法需要注意什么？

• 如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
• 如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true

会先通过hashCode进行比较，相同的情况下再通过equals进行比较。

equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等

重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，导致出现覆盖存储的数据的问题

HashMap在多线程下可能会出现的问题？

• JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

• 多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

HashMap的扩容机制

在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

而在 JDK 1.8 中

• 第1步是对哈希表长度的扩展（2倍）
• 第2步是将旧哈希表中的数据放到新的哈希表中。

在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

Hashmap和Hashtable有什么不一样的

• HashMap线程不安全，效率高一点，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
• HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。底层数据结构为数组+链表。

ConcurrentHashMap怎么实现

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先判断容器是否为空：

• 如果为空则使用 volatile 加 CAS （乐观锁） 来初始化
• 如果容器不为空，则根据存储的元素计算该位置是否为空。
  • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
  • 如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小，发生冲突和加锁的频率降低，并发操作的性能就提高了

已经用了synchronized，为什么还要用CAS呢

使用synchronized，还是使用CAS，主要是根据锁竞争程度来判断的

如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值

线程竞争比较强烈，使用synchronized来处理hash碰撞比CAS效率要高

Set集合有什么特点？如何实现key无重复的？

• set集合特点：Set集合中的元素是唯一的，不会出现重复的元素。
• set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复。当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

有序的Set是什么

• 有序的 Set 是TreeSet和LinkedHashSet。TreeSet是基于红黑树实现。LinkedHashSet是基于双重链表和哈希表的结合来实现元素的有序存储
• 记录插入顺序的集合通常指的是LinkedHashSet

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/26335.html