Java中的集合

Java中的集合（Collections）是Java中一个重要的部分，用于存储一组对象。Java中的集合框架为数据的处理提供了统一的视图，对数据的存储和访问实现了标准化。

其中常用的有List，Set，Map这三类。List、Set都是继承自Collection接口，而Map为单独的接口以下是一些常用的实现类

List（列表）

List是Collection的子接口，允许有重复元素，可以插入多个null元素，是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序，常用的实现类有ArrayList、LinkedList

ArrayList

ArrayList是Java集合框架中常用的数据结构，继承自AbstractList，实现了List接口。

ArrayList底层实现是Object数组，允许插入的元素重复，插入的元素是有序的，动态扩容，非线程安全，基于动态数组的数据结构，擅长随机访问(或者说查询速度快)，但是增删速度慢

LinkedList

它也实现了List接口，它是一种双向链表，每个节点都包含了数据和两个指针，一个指向前一个节点，一个指向后一个节点。允许插入的元素重复，插入的元素是有序的，动态扩容，非线程安全，擅长增删操作。但在查找元素的时候，每次都需要从头节点或尾节点开始遍历链表，因此它的查询效率不如ArrayList.

Set（散列表）

Set是Collection的子接口，它不允许出现重复元素，且元素都是唯一的，只允许存储一个null元素，此外还有它是无序容器（这里的无序是指存入元素的先后顺序与输出元素的先后顺序不一致）。

Set在Java中常见的实现类有HashSet、TreeSet。

HashSet

它实现了Set接口，并且继承了AbstractSet类。HashSet的构造函数有两个，一个是默认的构造函数，另一个是传入容量的构造函数。它是基于哈希表实现的，不包含重复的元素，并且元素的顺序是不确定的。它只允许存储一个null元素,且非线程安全的。

HashSet是基于哈希表实现的，因为它使用了哈希表来存储元素。在HashSet中，每个元素都有一个哈希码，哈希码是通过元素的hashCode()方法计算出来的，不同的元素的哈希码通常是不同的。当元素被添加到HashSet中时，HashSet会使用元素的哈希码来确定元素在哈希表中的位置，然后将元素添加到这个位置。当元素被查找时，HashSet也会使用元素的哈希码来确定元素在哈希表中的位置，然后从这个位置开始查找元素。由于哈希表的查找操作的时间复杂度是O(1)，所以HashSet的查找操作也非常高效。

注意：HashSet的hashCode()方法被重写了，重写后，计算的值是元素本身的值。且equals()也被重写了。

HashSet的使用场景：

1. 存储大量数据，且数据不重复。
2. 不关心元素的顺序。
3. 需要快速判断元素是否存在的场景。

TreeSet

TreeSet是一个有序的集合，基于红黑树实现。其中不包含重复的元素，且元素按照升序排列，默认是按照自然顺序排列，也就是说TreeSet中的对象元素需要实现Comparable接口。TreeSet类中跟HashSet类一样也没有get()方法来获取指定位置的元素，所以也只能通过迭代器方法来获取。

TreeSet虽然是有序的，但是并没有具体的索引，当插入一个新的数据元素的时候，TreeSet中原有的数据元素可能需要重新排序，所以TreeSet插入和删除数据元素的效率较低。当我们使用TreeSet存储自定义类时，需要在自定义类中重写compareTo方法，以提供对比方式，否则TreeSet不能对用户自定义的类型进行正确的树状排序。

Map（哈希表）

Map是一种依照键存储元素的容器，在Map中键可以是任意类型的对象。Map中不能有重复的键，每个键都有一个对应的值。一个键（key）和它对应的值构成map集合中的一个元素。（jdk1.8之后 对remove方法 进行了优化 没有对应的键或者 对应的键值对 则直接返回 false）。

Map接口常用实现类有以下两个：HashMap和TreeMap。

HashMap

它基于哈希表（Hash table）实现。当HashMap中的元素数量达到一定的阈值（例如，桶的数量大于8,或者哈希表的大小达到64），它会把链表转化为红黑树以提高性能。所以，可以说HashMap的数据结构基础是哈希表，但在某些情况下，它可能会使用红黑树来优化性能。

HashMap查询数据时不受元素数量的影响，是查询效率最高的数据结构。在添加元素的时候，会比较键值对的key值，如果两个key相等，则替换value值，否则进行添加。

TreeMap

TreeMap通过红黑树数据结构来维护键值对的顺序，因此它能够保证键值对按照键的自然顺序或自定义顺序排列，而且可以快速地进行插入、查找和删除等操作

对于放入其中的元素，是按照k键——排序，自然升序。如果作为键的元素（类） 要实现排序的话 跟TreeSet类似 需要实现Comparable 接口 并重写 CompareTo()方法，当然也需要重写equals(Object o)方法和hashCode()方法，以便TreeMap能够正确地判断两个键是否相等，以及正确地计算键的哈希值

一些问题

1-为什么数组查询快？为什么ArrayList 查询快？

即使我们对一个已经排好序的数组通过二分查找法进行查找，时间复杂度也为O(logn)。我们更准确的说法是，数组通过角标进行随机访问的时间复杂度为O(1)。那么接下来进入我们要探讨的

为什么数组能支持随机访问呢？换而言之，为什么数组能直接通过角标访问元素

1.数组占用的内存空间是连续的

2.数组中都为同一类型的元素

连续的内存空间跟相同类型的元素这两大利器决定了数组随机访问的特性。另外还需要补充的是，因为数组在内存空间中是连续的，所以CPU在读取时，可以对数组进行“预读”。什么是预读呢？CPU在从内存中加载数据时，会先把读取到的数组加载到CPU的缓存中。而CPU每次从内存中读取数据，并不是只读取那个特定的要访问的地址，而是读取一个数据块，并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取，这样就实现了比直接访问内存更高效的访问机制（这样做的原因是因为，CPU处理数据的速度高于从内存中读取数据的速度）。

有的同学可以理解“空间连续”这个原因，但是不理解“同一类型的元素”？

如果数组中可以存储不同类型的元素，那么每个元素的大小和内存布局都是不同的，就无法保证它们占用的内存空间是连续的。

因此，在Java中，为了保证数组中的元素的内存布局是连续的，我们必须将其限制为只能存储相同类型的元素。

如果您需要存储不同类型的元素，可以使用Java中的其他数据结构，例如HashMap。这些数据结构可以动态地调整其大小，并且可以存储不同类型的元素。但是，它们通常比数组具有更大的开销和较慢的访问速度。

2-hashCode()方法

在Java中，如果没有被重写，那么默认的hashCode()计算的是该对象的内存地址。这意味着，每次创建一个对象时，其hashCode()都会返回一个新的内存地址。

通常来说，被重写后，hashCode()计算的则是该对象的本身的值。Set和Map集合都使用了重写后的hashCode()方法来比较和存储对象。在Set集合中，每个元素都有一个唯一的哈希码，如果两个元素的哈希码相同，那么它们将被视为相等的元素。在Map集合中，键的哈希码被用来确定键值对在内存中的位置.

3-equals()跟“==”的区别跟作用

equals()：没被重写的情况下，equals方法用来比较两个对象的引用地址是否相等。因为在Object中没有属性，所以就只比较了两个引用指向的对象是否相等。

而被重写后，一般用来比较对象本身的值是否相同。

"=="： 这是Java中的相等运算符，用于比较两个对象的引用是否相等。

对于基本类型（如int、double、char等）来说，"=="操作符比较的是它们的值是否相同。对于对象来说，"=="操作符比较的是它们的引用是否相同。

默认情况下，equals()方法的行为与"=="相同。在String类中，equals()方法被重写为比较两个字符串的内容是否相同。

4-为什么重写了equals方法后,也要重写hashCode方法?

当equals方法被重写时，需要同时重写hashCode方法。因为——Map和Set等集合是依据hashCode和equals判断对象是否重复。

在使用哈希表等数据结构时，判断两个对象是否相等通常是先比较它们的哈希码，如果哈希码不同，说明这两个对象肯定不相等；如果哈希码相同，再调用equals()方法来进行深度比较。

如果重写了equals方法，而没有重写hashCode，会出现equals相等的对象，hashcode不相等的情况，则在集合中将会存储两个值相等的对象，重写hashCode方法就是为了避免这种情况的出现。

• 对象作为Map的Key：只重写equals时 key会重复
• 对象使用Set去重时：只重写equals无法去重

此外，equals相等，hashcode一定相等；hashcode相等，equals不一定相等。

Map是一个键值对的集合，它允许使用键来访问值。在Map中，键是唯一的，不能有重复。这个唯一性的判断就是通过hashCode()和equals()方法来实现的。当你试图将一个键值对添加到Map中时，它会首先调用键的hashCode()方法来得到一个哈希码，然后根据这个哈希码来决定将这个键值对放在哪个桶（bucket）里。接着，Map会查看这个桶里是否已经有其他键值对存在。如果有，那么就会调用键的equals()方法来比较这个新的键和旧的键是否相等。如果它们相等，那么就会覆盖旧的键值对，否则就会添加新的键值对。

Set是一个值的集合，它不允许有重复的值。这个唯一性的判断也是通过hashCode()和equals()方法来实现的。当你试图将一个元素添加到Set中时，它会首先调用这个元素的hashCode()方法来得到一个哈希码，然后根据这个哈希码来决定将这个元素放在哪个桶里。接着，Set会查看这个桶里是否已经有其他元素存在。如果有，那么就会调用元素的equals()方法来比较这个新的元素和旧的元素是否相等。如果它们相等，那么就会忽略这个重复的元素，否则就会添加新的元素。

总的来说，无论是Map还是Set，它们都使用hashCode()方法来初步判断对象是否重复，然后使用equals()方法来做最终的判断。这是因为在大多数情况下，计算哈希码比比较对象的内容要快得多。这也是要同时重写hashCode()的原因之一。