JavaSE从零开始到精通(九) - 双列集合

 1.前言

Java 中的双列集合主要指的是可以存储键值对的集合类型，其中最常用的包括 Map 接口及其实现类。这些集合允许你以键值对的形式存储和管理数据，提供了便捷的按键访问值的方式。

2. HashMap 

HashMap 是基于哈希表实现的 Map 接口的类，允许存储键值对，支持 null 键和 null 值。它提供了 O(1) 时间复杂度的插入、删除和查找操作，但不保证映射顺序。

由键决定：无序、不重复、无索引。

底层数据结构: 数组 + 链表 / 红黑树（JDK8+）其中一个链表超过8，并且数组长度不低于64转换为红黑树。通过哈希函数将键映射到数组索引，解决哈希冲突的链表或红黑树存储。初始容量是16，扩容因子是0.75。扩容扩大两倍(持续保持2^n次方的容量)。

多个输入对应相同输出：hash冲突。

为什么要转换成红黑树？

HashMap变红黑树主要用于防患于未然，防止有些人造一些恶劣数据。正常存20万个单词都不会有链表超过8。

为什么hash表的容量是2^n次方?

1.能使用2^n

对于程序来说涉及位运算符相对来说都是高效的，因为计算机底层是以二进制存储的，二进制是天然的位运算符操作容器。 

2.高低位异或计算hash值

因为二进制和容器容量正好对应，只需要看后几位，高位根本用不上。2^n次方看后n位。

低位相同的哈希码，在高位不同的情况下，会产生hash冲突。通过高16位和低16位异或运算能够让存入的位置由高位的参与决定。

负载因子的概念

负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75 时，系统会将哈希表扩容至原先的 2 倍。

容易想到，哈希表容量 𝑛 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

HashSet 的加载因子被设置为 0.75 是为了在空间利用率和性能之间取得平衡。这个值能够使得哈希表在大多数情况下既能够有效地利用内存，又能够保持较好的查询性能，是经过权衡和实验确定的合理选择。

// 创建一个HashMap
Map<String, Integer> hashMap = new HashMap<>();// 添加键值对
hashMap.put("apple", 1);
hashMap.put("banana", 2);// 获取值
int value = hashMap.get("apple");
System.out.println(value); // 输出: 1

3. LinkedHashMap:

• LinkedHashMap 继承自 HashMap，保留了元素插入顺序，即按照插入顺序迭代元素。可选择按访问顺序（LRU 缓存算法）排序。

• 由键决定：有序、不重复、无索引。

  底层数据结构: 哈希表 + 双向链表。双向链表维护插入顺序或访问顺序。

 

与HashMap不同的是：存和取的顺序相同

原理：每个键值对元素之间又额外的多了一个双链表的机制记录存储的顺序。 

 在添加第一个元素的时候，会记录第一个元素的地址值，然后取的时候根据第一个元素的地址值找到头节点，依次进行取元素。

// 创建一个LinkedHashMap，保持插入顺序
Map<String, Integer> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);// 添加键值对
linkedHashMap.put("apple", 1);
linkedHashMap.put("banana", 2);// 获取值，更新访问顺序
int value = linkedHashMap.get("apple");
System.out.println(value); // 输出: 1

4. TreeMap:

• TreeMap 基于红黑树实现，可根据键的自然顺序或自定义比较器排序。元素有序存储，提供灵活的自定义排序功能。

  底层数据结构: 红黑树。自平衡二叉查找树，保证有序性。

 对于原理和TreeSet相似，在上一篇已经讲解过了，这里就不过多介绍了。

// 创建一个TreeMap，根据键的自然顺序排序
Map<String, Integer> treeMap = new TreeMap<>();// 添加键值对
treeMap.put("apple", 1);
treeMap.put("banana", 2);// 获取值
int value = treeMap.get("apple");
System.out.println(value); // 输出: 1

5. Hashtable:

• Hashtable 是早期的 Map 类，与 HashMap 类似但线程安全。由于同步开销大，推荐使用 ConcurrentHashMap 替代。

  底层数据结构: 数组 + 链表。通过哈希函数将键映射到数组索引，使用链表解决冲突。

// 创建一个Hashtable
Map<String, Integer> hashtable = new Hashtable<>();// 添加键值对
hashtable.put("apple", 1);
hashtable.put("banana", 2);// 获取值
int value = hashtable.get("apple");
System.out.println(value); // 输出: 1

面试题：谈谈HashMap和HashTable的区别

1. 线程安全方面
   1. HashTable是线程安全的(底层使用了全局同步锁)
   2. HashMap是线程不安全的，因此可以得出HashMap的性能比较好
2. 数据结构的实现

   1. java8以后HashMap使用数组+链表+红黑树组成(当节点高于7转换为红黑树)

   2. HashTable是数组+链表

3. 初始容量
   1. HashMap初始容量是16
   2. HashTable初始容量是11
4. hash算法
   1. HashMap的散列算法是对key的hashcode进行二次散列，从而避免key的分布不均匀影响性能。
   2. HashTable是hashcode对数组的长度取模

6. ConcurrentHashMap:

• ConcurrentHashMap 针对高并发设计，通过分段锁（Segmented lock）实现线程安全。性能优于 Hashtable，在多线程环境中使用较为合适。

  底层数据结构: 分段锁 + 数组 + 链表 / 红黑树（JDK8+）。每个段（Segment）独立锁定，允许多线程并发访问不同段的数据。

// 创建一个ConcurrentHashMap
Map<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();// 添加键值对
concurrentHashMap.put("apple", 1);
concurrentHashMap.put("banana", 2);// 获取值
int value = concurrentHashMap.get("apple");
System.out.println(value); // 输出: 1

这些双列集合类在不同的场景中提供了各自的优势，根据需求选择合适的实现类可以提高数据的管理效率和性能。

面试题：HashTable为什么会被ConcurrentHashMap替代

ConcurrentHashMap 可以替代 Hashtable 的几个主要原因包括：

1. 并发性能优化： ConcurrentHashMap 使用了分段锁（Segmented lock）或 CAS 操作来实现线程安全，而 Hashtable 使用了全局锁。这意味着 ConcurrentHashMap 在多线程并发访问时，可以支持更高的并发度，因为不同段（Segment）的数据可以并行操作，而 Hashtable 的所有操作都是同步的。

2. 更好的扩展性： ConcurrentHashMap 在设计上采用了分段锁策略，这样在多线程情况下，不同段的数据可以并行处理，从而减少了锁竞争，提高了并发访问效率。相比之下，Hashtable 的同步操作可能会导致线程争用，限制了扩展性和性能。

3. 更好的迭代性能： 在迭代时，ConcurrentHashMap 可以允许在不进行任何同步的情况下进行读取操作，而 Hashtable 则要求在整个表上进行锁定。这意味着在迭代期间，ConcurrentHashMap 的性能更好，因为它不会被其他线程的修改所阻塞。

4. 允许空键和空值： ConcurrentHashMap 允许 null 键和 null 值的存在，而 Hashtable 不允许。这在某些场景下可能更为灵活。

综上所述，ConcurrentHashMap 在设计和实现上优于 Hashtable，尤其是在高并发环境中能够提供更好的性能和扩展性，因此在大多数情况下推荐使用 ConcurrentHashMap 而不是 Hashtable。

 7. Peoperties

Properties 是 Java 中处理配置文件的一个常用类，它继承自 Hashtable<Object, Object>，也实现了 Map<Object, Object> 接口。主要用于存储键值对形式的配置信息，通常用于读取和写入属性文件（.properties 文件)。 

Properties 类在 Java 中广泛应用于配置文件的读写

使用load()方法从一个输入流中加载属性，或者使用store()方法将属性保存到输出流中。

主要特点和用途：

1. 存储键值对： Properties 对象存储的是字符串键和值的映射关系，键和值都必须是字符串类型。

2. 加载和存储属性文件： Properties 可以从文件中加载配置信息，也可以将配置信息写入文件。常见的配置文件格式是 .properties 文件，它采用 key=value 的格式存储配置信息。

3. 默认的读写方法： 提供了便捷的方法来加载和存储属性文件，如 load() 和 store() 方法。

4. 默认值支持： 可以设置默认值，当请求的属性不存在时，返回默认值。

5. 线程安全性： Properties 继承自 Hashtable，因此默认不是线程安全的。在多线程环境下，可以通过同步措施来保证线程安全。

基本操作示例：

创建和设置属性：

Properties prop = new Properties();
prop.setProperty("database.url", "jdbc:mysql://localhost:3306/mydatabase");
prop.setProperty("database.user", "username");
prop.setProperty("database.password", "password");

从文件加载属性： 

try (FileInputStream fis = new FileInputStream("config.properties")) {prop.load(fis);
} catch (IOException e) {e.printStackTrace();
}

 将属性存储到文件：

try (FileOutputStream fos = new FileOutputStream("config.properties")) {prop.store(fos, "Database Configuration");
} catch (IOException e) {e.printStackTrace();
}

 获取属性值：

String url = prop.getProperty("database.url");
String user = prop.getProperty("database.user", "defaultUser"); // 指定默认值
String password = prop.getProperty("database.password");

注意事项：

1. 字符编码：默认情况下，store() 方法使用 ISO 8859-1 编码，不支持 Unicode 字符。如果需要支持 Unicode，可以使用 Writer 参数的 store(Writer writer, String comments) 方法，并指定合适的字符编码。
2. 属性文件格式： .properties 文件使用简单的 key=value 格式存储数据，不支持复杂的数据结构或注释（可以用 # 开头注释）。
3. 默认值处理： 如果请求的属性不存在，getProperty(key) 方法返回 null；可以使用 getProperty(key, defaultValue) 指定默认值。

 8. 总结

        双列集合在软件开发中扮演关键角色，通过键值对的方式存储和管理数据，支持快速的插入、删除和查找操作，适用于各种应用场景，如配置管理、缓存实现和关联数据管理。Java中的Map接口及其实现类（如HashMap、TreeMap等）提供了多样化选择，开发人员可以根据需求选择最适合的实现以提高性能和效率。这些特性使得双列集合成为处理复杂数据结构和优化数据访问的重要工具。