八. 对比Vector，ArrayList, LinkedList有何区别？
8.1 典型回答
三者都是实现集合框架中的List,即有序集合，都按照位置进行定位，添加或者删除的操作，都提供迭代器进行遍历内容，由于具体的设计，在行为，性能，线程安全方面又有些不同。
8.1.1 Vector：
是Java早期提供的线程安全的动 态数组，如果不需要线程安全，不建议使用，同步需要进行额外开销，Vector内部使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并且拷贝原有的数组数据
8.1.2 ArrayList ：
是应用更加广泛的动态数组实现，本身不是线程安全的，性能好很多。
ArrayList可以根据需要调整容量，vector在扩容的时候会提高一倍，ArrayList则是增加50%
8.1.3 LinkedList
Java 提供的双向链表，不需要进行上面两种进行调整容量，也不是线程安全的。
8.2 考察点分析：
8.2.1 不同容器类型适合的场景
8.2.1.1 Vector和ArrayList
动态数组，内部元素以数组形式顺序存储，适合随机访问的场合，除了尾部插入和删除元素，往往会性能会相对较差，比如我们中间位置插入一个元素，需要移动后续所有元素。
8.2.1.2 LinkedList
进行节点插入，删除高效很多，但是随机访问性能则比动态数组慢。
8.3 小结：
Vector、ArrayList、LinkedList均为线型的数据结构，但是从实现方式与应用场景中又存在差
别。
8.3.1 底层实现方式
ArrayList内部用数组来实现；LinkedList内部采用双向链表实现；Vector内部用数组实现。
8.3.2 读写机制
ArrayList在执行插入元素是超过当前数组预定义的最大值时，数组需要扩容，扩容过程需要
调用底层System.arraycopy()方法进行大量的数组复制操作；在删除元素时并不会减少数组的
容量（如果需要缩小数组容量，可以调用trimToSize()方法）；在查找元素时要遍历数组，对
于非null的元素采取equals的方式寻找。
LinkedList在插入元素时，须创建一个新的Entry对象，并更新相应元素的前后元素的引用；
在查找元素时，需遍历链表；在删除元素时，要遍历链表，找到要删除的元素，然后从链表
上将此元素删除即可。
Vector与ArrayList仅在插入元素时容量扩充机制不一致。对于Vector，默认创建一个大小为10
的Object数组，并将capacityIncrement设置为0；当插入元素数组大小不够时，如果capacityI
ncrement大于0，则将Object数组的大小扩大为现有size+capacityIncrement；如果capacityIn
crement<=0,则将Object数组的大小扩大为现有大小的2倍。
8.3.3 读写效率
ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此，对其进行
插入和删除速度较慢，但检索速度很快。
LinkedList由于基于链表方式存放数据，增加和删除元素的速度较快，但是检索速度较慢。
8.3.4 线程安全性
ArrayList、LinkedList为非线程安全；Vector是基于synchronized实现的线程安全的ArrayList。
需要注意的是：单线程应尽量使用ArrayList，Vector因为同步会有性能损耗；即使在多线程环境下，我们可以利用Collections这个类中为我们提供的synchronizedList(List list)方法返回一
个线程安全的同步列表对象。
九. 对比Hashtable，HashMap，TreeMap
Map是广义Java集合框架中的另外一部分，HashMap作为框架中使用频率最高的类型之一。
9.1 典型回答
9.1.1 Hashtable，HashMap，TreeMap
常见的Map实现，以键值对的形式存储和操作数据的容器类型。
9.1.1.1 Hashtable
早期Java类库提供的一个哈希表实现，本身是同步的，不支持null键和值，由于同步导致的性能开销，很少被推荐使用。
9.1.1.1.1详细解析：
它是同步的，也就是说它的方法都是线程安全的，可以在多线程环境下使用。
然而，由于同步操作需要获取锁、释放锁，这会引入额外的性能开销。在高并发的场景下，这种同步机制可能成为瓶颈，影响性能。因此，在现代的Java开发中，很少推荐使用Hashtable。
除了性能开销外，Hashtable还有其他一些限制。首先，Hashtable不支持null键和null值，如果尝试将null作为键或值进行插入，会抛出NullPointerException异常。其次，Hashtable的扩容机制比较低效，当元素数量增加时，需要重新分配更大的内部数组，导致性能下降。
相比之下，Java提供了更好的替代方案，例如HashMap和ConcurrentHashMap。HashMap是非线程安全的，在单线程环境下性能更好，而ConcurrentHashMap则是线程安全的，并且在高并发环境下有更好的性能表现。
总结起来，由于同步导致的性能开销和其他一些限制，Hashtable在现代的Java开发中很少被推荐使用。应该优先考虑使用HashMap或ConcurrentHashMap来满足哈希表的需求。
9.1.2 HashMap:
不是同步的，支持null键和值，通常情况下，HashMap进行put或者get操作，可以达到常数时间的性能，所以是绝大部分利用键值对存取场景的首选。
如实现一个用户ID和用户信息对应的运行时存储结构
9.1.2.1详细解释：
因为HashMap内部通过哈希函数将键映射到数组中的位置，从而快速定位到对应的键值对。只有在哈希冲突发生时，才会涉及到链表或红黑树的查找操作，但其平均时间复杂度仍然是常数级别。
因为HashMap的高效性能和灵活性，它成为了绝大部分利用键值对存取场景的首选数据结构。无论是普通的单线程环境还是多线程环境下，在合适的使用方式下，HashMap都能提供高效的存取操作。
需要注意的是，HashMap不是线程安全的，如果在多线程环境下同时对HashMap进行修改操作，可能会导致数据不一致的问题。如果需要在多线程环境下使用哈希表，并保证线程安全，可以考虑使用ConcurrentHashMap或其他线程安全的数据结构。
9.1.2.2 哈希冲突：
9.1.2.2.1 红黑树和链表查询例子解析：
当哈希冲突发生时，HashMap内部会使用链表或红黑树来解决。在链表过长（达到一定阈值）时，会将链表转换为红黑树来提高查询效率。
假设我们有以下键值对需要插入到HashMap中：
{ "apple": 1, "banana": 2, "cat": 3, "dog": 4, "elephant": 5, "fruit": 6 }
通过哈希函数，这些键值对被映射到了数组的同一个位置，即发生了哈希冲突。在初始情况下，该位置形成了一个链表：
-> ("apple", 1) -> ("banana", 2) -> ("cat", 3) -> ("dog", 4) -> ("elephant", 5) -> ("fruit", 6)
假设我们要获取键为"dog"的值。HashMap会先计算出"dog"的哈希值，然后根据哈希值找到相应的数组位置。因为发生了哈希冲突，HashMap会遍历链表，逐个比较键的值。
在这个例子中，HashMap会依次比较"apple"、"banana"、"cat"和"dog"。最终发现了键为"dog"的键值对，并返回其对应的值4。
然而，随着键值对的增加，链表可能会变得很长，导致查找效率下降。为了解决这个问题，当链表长度达到一定阈值时（默认为8），HashMap会将链表转换为红黑树。
例如，当链表长度达到8时，原来的链表会被转化为红黑树结构：
"fruit" / "elephant" / \ "dog" "cat" / \ "banana" "apple"
通过使用红黑树，HashMap可以以更高效的方式进行查找操作。红黑树的平均查找时间复杂度是O(log n)，相比于链表的线性查找时间复杂度O(n)，能够更快地定位到目标键值对。
9.1.3 TreeMap：
是基于红黑树的一种提供顺序访问的Map，和HashMap不一样，它的get，put，remove等操作，具体属性由Comparator来决定，或者根据键的自然顺序来判断。
9.1.3.1 详细解释：
创建一个TreeMap来存储学生信息，其中键为学生的年龄，值为学生的姓名。首先，我们定义一个实现了Comparator接口的自定义比较器AgeComparator，用于确定键的顺序。
import java.util.Comparator; import java.util.TreeMap; class AgeComparator implements Comparator<Integer> { public int compare(Integer age1, Integer age2) { return age1.compareTo(age2); } } public class Example { public static void main(String[] args) { TreeMap<Integer, String> treeMap = new TreeMap<>(new AgeComparator()); // 添加学生信息 treeMap.put(20, "Alice"); treeMap.put(18, "Bob"); treeMap.put(22, "Charlie"); // 获取学生信息 System.out.println(treeMap.get(18)); // 输出: Bob // 删除学生信息 treeMap.remove(20); // 遍历学生信息 for (Integer age : treeMap.keySet()) { String name = treeMap.get(age); System.out.println("Age: " + age + ", Name: " + name); } } }
上面的代码中，我们通过传入自定义的比较器AgeComparator来创建TreeMap对象。这个比较器决定了键的排序顺序，即按照学生的年龄进行排序。
我们通过put方法向TreeMap中添加学生信息，其中键为学生的年龄，值为学生的姓名。在这个例子中，我们添加了三个学生信息。
接下来，我们可以使用get方法根据键获取对应的值，例如获取年龄为18的学生的姓名，将返回"Bob"。
然后，我们使用remove方法删除年龄为20的学生的信息。
最后，我们使用keySet方法获取TreeMap中所有键的集合，并遍历输出每个键和对应的值，按照年龄的顺序（由比较器决定）输出学生信息。
通过使用TreeMap，我们可以实现对键值对的有序访问，而不是像HashMap那样无序访问。这在需要按照键的顺序进行操作的场景中非常有用，例如按照年龄范围查找学生，或者按照年龄排序输出学生信息等。
9.1.4 小结：
大部分使用 Map 的场景，通常就是放入、访问或者删除，而对顺序没有特别要求，
HashMap 在这种情况下基本是最好的选择。HashMap 的性能表现非常依赖于哈希码的有效性，掌握 hashCode 和 equals 的一些基本约定。
9.1.4.1 hashCode 和 equals 的一些基本约定：
1 . 如果两个对象通过equals方法比较相等（即具有相同的内容），那么它们的hashCode值必须相等。
- 这条约定保证了在哈希表等依赖hashCode的数据结构中，相等的对象能够被正确地定位和访问。
2. 如果重写了equals方法，那么必须同时重写hashCode方法。
- 这是由于Object类中的hashCode方法是基于对象的内存地址计算出来的，与内容无关。而equals方法是用于比较对象的内容是否相等。如果只重写了equals方法而不重写hashCode方法，就会违反前面提到的第一条约定，导致在使用散列集合（如HashMap、HashSet）时无法正确查找和删除对象。
3. hashCode方法需要保持一致性。
- 根据这条约定，如果一个对象在运行过程中的状态发生变化，但是其equals方法依然认为两个对象是相等的，那么它们的hashCode方法应该返回相同的值。这是为了保证对象在散列集合中的一致性，使得对象能够在整个生命周期内被正确地操作。
9.1.4.1.1 详细解释：
9.1.4.1.1.1 hashCode和equals的一致性约定：
class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null || getClass() != obj.getClass()) { return false; } Person person = (Person) obj; return age == person.age && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(name, age); } } public class Example { public static void main(String[] args) { Person person1 = new Person("Alice", 25); Person person2 = new Person("Alice", 25); System.out.println(person1.equals(person2)); // 输出: true System.out.println(person1.hashCode() == person2.hashCode()); // 输出: true person1.setAge(30); System.out.println(person1.equals(person2)); // 输出: true System.out.println(person1.hashCode() == person2.hashCode()); // 输出: true } }
9.1.4.1.1 详细解释：
9.1.4.1.1.1 hashCode和equals的一致性约定：
class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null || getClass() != obj.getClass()) { return false; } Person person = (Person) obj; return age == person.age && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(name, age); } } public class Example { public static void main(String[] args) { Person person1 = new Person("Alice", 25); Person person2 = new Person("Alice", 25); System.out.println(person1.equals(person2)); // 输出: true System.out.println(person1.hashCode() == person2.hashCode()); // 输出: true person1.setAge(30); System.out.println(person1.equals(person2)); // 输出: true System.out.println(person1.hashCode() == person2.hashCode()); // 输出: true } }
上面的例子中，我们自定义了Person类，并重写了equals和hashCode方法。equals方法比较了两个Person对象的name和age属性是否相等，hashCode方法根据name和age计算出哈希码。
在创建person1和person2时，它们的name和age属性都是相同的，因此equals方法会返回true，hashCode方法计算出的哈希码也会相等。
接着，我们修改了person1的age属性为30，但是equals方法仍然判断person1和person2是相等的。根据前面提到的一致性约定，即使对象状态发生变化，但equals方法认为两个对象是相等的，它们的hashCode方法返回的哈希码仍然要保持一致。
因此，在输出中我们可以看到无论是equals方法还是hashCode方法的比较结果，都符合我们对hashCode和equals的基本约定。
9.1.4.1.1.2 hashCode的重要性例子：
确保相等的对象在使用依赖于hashCode的数据结构（如哈希表、散列集合等）时，能够被正确地定位和访问。
在Java中，当我们将对象插入到使用散列的数据结构中（例如HashMap或HashSet），首先会根据对象的hashCode值来确定对象在内部数据结构中的位置。然后，如果存在多个对象具有相同的hashCode值，那么再通过equals方法进行进一步的比较以区分它们。
详细解释：
class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null || getClass() != obj.getClass()) { return false; } Person person = (Person) obj; return age == person.age && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(name, age); } } public class Example { public static void main(String[] args) { Person person1 = new Person("Alice", 25); Person person2 = new Person("Alice", 25); System.out.println(person1.equals(person2)); // 输出: true System.out.println(person1.hashCode() == person2.hashCode()); // 输出: true Map<Person, String> map = new HashMap<>(); map.put(person1, "Value 1"); System.out.println(map.get(person1)); // 输出: Value 1 System.out.println(map.get(person2)); // 输出: Value 1 } }
创建了两个Person对象person1和person2，它们的name和age属性都是相同的，因此equals方法返回true。
接着，我们将person1作为键插入到HashMap中，并将对应的值设置为"Value 1"。然后，我们通过person1和person2分别作为键去获取对应的值。
根据hashCode的约定，在将person1插入HashMap时，首先会计算person1的hashCode值，并根据该值确定person1在底层数据结构中的位置。当我们使用person2作为键去获取值时，HashMap会再次计算person2的hashCode值，并找到与person2具有相同hashCode值的位置。
由于person1和person2的hashCode值相等，并且equals方法返回true，HashMap能够正确地定位到已经插入的person1，并返回"Value 1"。
说明了如果两个对象通过equals方法比较相等，那么它们的hashCode值必须相等的重要性。只有同时满足这两个条件，才能保证在依赖hashCode的数据结构中正确地定位和访问相等的对象。
9.1.4.1.1.3 map.get(person1)源码：
map.get(person1)的内部代码是HashMap类中的get方法。下面是简化的HashMap的get方法的伪代码，用于说明其大致逻辑：
public V get(Object key) { // 1. 计算键的哈希码 int hashCode = key.hashCode(); // 2. 根据哈希码找到对应的桶（数组索引） int index = hashCode & (table.length - 1); // 3. 在桶中查找匹配的键值对 Entry<K, V> entry = table[index]; while (entry != null) { if (entry.hashCode == hashCode && Objects.equals(entry.key, key)) { return entry.value; } entry = entry.next; } // 4. 没有找到匹配的键值对，返回null return null; }
9.1.4.1.1.4 解释equals代码：
@Override public boolean equals(Object obj) { // 1. 检查是否是同一个对象 if (this == obj) { return true; } // 2. 检查传入的对象是否为空或者类型不匹配 if (obj == null || getClass() != obj.getClass()) { return false; } // 3. 将传入的对象强制转换为Person类型，并进行属性值的比较 Person person = (Person) obj; return age == person.age && Objects.equals(name, person.name); }
- 首先，检查当前对象和传入的对象是否是同一个实例（即内存地址是否相同）。如果是同一个对象，则直接返回true，表示它们相等。
- 如果传入的对象为空（null）或者传入的对象的类型与当前对象的类型不匹配，即getClass()返回的类不相同，那么它们不可能相等，直接返回false。
- 将传入的对象强制转换为Person类型，并进行属性值的比较。在这里，通过==比较age属性的值是否相等，使用Objects.equals方法比较name属性的值是否相等。
- age的比较使用==运算符比较原始数据类型int，判断它们的值是否相等。
- name的比较使用Objects.equals方法，该方法会先检查两个参数是否为null，然后再调用name对象的equals方法进行比较。这是为了避免NullPointerException错误。
如果age和name都相等，则返回true，表示两个Person对象相等；否则返回false，表示它们不相等。
这段代码通过对两个Person对象的属性值进行比较，判断它们是否相等。这里使用了引用类型的Objects.equals方法来比较name属性，保证了在name为null时不会抛出NullPointerException异常。同时，还对传入的对象进行了类型检查，确保传入的对象与当前对象具有相同的类型。
9.1.4.1.1.5 getClass() != obj.getClass()
是用来检查传入的对象 obj 是否和当前对象具有相同的类型。
具体解释如下：
getClass()方法是 Java 中的一个非常基础的方法，它返回当前对象所属的类的运行时类型。obj.getClass()则是获取对象obj所属的类的运行时类型。getClass() != obj.getClass()用于比较当前对象和传入的对象obj的类型是否相同。如果类型不相同，则返回false表示两个对象的类型不匹配，也即它们不可能相等。
这里的目的是避免出现类型不匹配的情况。当两个对象具有不同的类型时，它们在属性以及行为上可能会存在差异，因此无法简单地进行比较。所以，在执行进一步的属性值比较之前，首先要确保传入的对象 obj 和当前对象具有相同的类型，才能保证后续的属性值比较是有意义且准确的。
总结来说，getClass() != obj.getClass() 的作用是检查当前对象和传入的对象是否具有相同的运行时类型，以确保后续的属性值比较是有效的。
Person person = (Person) obj; return age == person.age && Objects.equals(name, person.name);
9.1.4.1.1.6 通过==比较age属性的值是否相等，使用Objects.equals方法比较name属性的值是否相等。 这里为什么比较方法不一样？
在代码中通过 == 比较 age 属性的值是否相等，使用 Objects.equals 方法比较 name 属性的值是否相等，是因为 age 和 name 是不同的数据类型。
- age 是一个基本数据类型（例如 int、double 等），使用 == 运算符可以直接比较它们的值是否相等。因为基本数据类型的值是直接存储在变量中的，所以它们可以通过比较数值来判断是否相等。
- name 是一个引用类型（例如字符串 String），它是一个对象，在内存中存储的是对象的引用地址。因此，我们不能简单地使用 == 运算符来比较两个字符串对象的内容是否相等，因为这只会比较对象的引用地址是否相同。而我们通常更关心的是字符串的内容是否相等。
为了比较引用类型的属性值是否相等，我们需要使用 equals 方法进行内容比较。Objects.equals 是 Java 提供的工具类 java.util.Objects 中的方法，用于比较两个对象的内容是否相等。它会先检查两个参数是否为 null，然后再调用对象的 equals 方法进行比较。在 String 类中，equals 方法已经被重写，用于比较字符串的内容是否相等。
9.1.4.2 针对有序 Map ：
虽然 LinkedHashMap 和 TreeMap 都可以保证某种顺序，但二者还是非常不同的。
9.1.4.2.1 LinkedHashMap 示例：
假设我们有一个 LinkedHashMap 存储了学生的姓名和对应的成绩，按照插入顺序进行迭代时，可以保证元素的顺序与插入的顺序一致。
import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapExample { public static void main(String[] args) { // 创建一个按插入顺序排序的 LinkedHashMap Map<String, Integer> studentGrades = new LinkedHashMap<>(); // 添加学生姓名和对应成绩 studentGrades.put("Alice", 90); studentGrades.put("Bob", 85); studentGrades.put("Charlie", 80); // 迭代输出学生姓名和对应成绩 for (Map.Entry<String, Integer> entry : studentGrades.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }
输出：
1. Alice: 90 2. Bob: 85 3. Charlie: 80
9.1.4.2.2 TreeMap 示例：
TreeMap 是基于红黑树的实现，它可以保持键的自然顺序或者指定的比较器顺序。下面的示例展示了如何使用自然顺序来排序存储的整数：
import java.util.Map; import java.util.TreeMap; public class TreeMapExample { public static void main(String[] args) { // 创建一个按键的自然顺序排序的 TreeMap Map<Integer, String> numbers = new TreeMap<>(); // 添加键值对 numbers.put(3, "Three"); numbers.put(1, "One"); numbers.put(2, "Two"); // 迭代输出键值对 for (Map.Entry<Integer, String> entry : numbers.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }
输出：
1. 1: One 2. 2: Two 3. 3: Three
TreeMap 会根据键的自然顺序（数字的大小）进行排序。而对于 LinkedHashMap 来说，它保持了元素的插入顺序。
9.1.4.2.3 小结：
LinkedHashMap 和 TreeMap 的不同点主要体现在以下几个方面：
- 内部实现：
- LinkedHashMap 使用哈希表和双向链表的结合来维护元素的插入顺序。它使用哈希表来支持快速的查找操作，并使用双向链表来保持元素的插入顺序。
- TreeMap 基于红黑树实现，它通过对键进行排序来维护元素的顺序。
- 排序方式：
- LinkedHashMap 保持元素的插入顺序，当按照插入顺序迭代时，元素会按照被插入的顺序输出。
- TreeMap 可以根据键的自然顺序或者自定义比较器来进行排序。当按照键的顺序迭代时，元素会按照键的排序顺序输出。
性能：
- LinkedHashMap 在常见操作（插入、删除、查找）的时间复杂度为 O(1)，因为它使用了哈希表进行快速查找。但是它相对于 HashMap 稍微增加了一些额外的开销来维护双向链表。
- TreeMap 在常见操作的时间复杂度为 O(logN)，因为它基于红黑树实现，红黑树的平衡性保证了较高的性能。
- 适用场景：
- LinkedHashMap 适用于需要保持元素插入顺序的场景，尤其是在需要实现 LRU（最近最少使用）缓存淘汰算法时。
- TreeMap 适用于需要按照键的顺序进行遍历或查找的场景，尤其是在需要范围查询的情况下。
总结起来，LinkedHashMap 适用于维护插入顺序的需求，而 TreeMap 则适用于基于排序的需求。它们的内部实现和性能特点不同，因此在选择使用时需要根据具体的场景和需求进行选择。
