Java集合HashMap——针对实习面试

Java集合Map
- HashMap的特性是什么？
- HashMap和Hashtable的区别？
- HashMap和HashSet的区别？
- HashMap和TreeMap的区别？
- 说说HashMap的底层实现
- 什么是hash冲突？有什么办法减少hash冲突？
- 为什么HashMap的容量总是2的幂次方？
- Map的get方法的时间复杂度是多少？

Java集合Map

在这里插入图片描述

HashMap的特性是什么？

HashMap 是 Java 中的一个核心类，它实现了 Map 接口，用于存储键值对（key-value pairs）。以下是 HashMap 的一些关键特性和行为：

基本特性

基于哈希表：
- HashMap 使用哈希表来存储数据，这使得它能够提供快速的查找、插入和删除操作。
键值对存储：
- HashMap 存储了键值对，其中键和值可以是任何对象。
键的唯一性：
- HashMap 不允许有重复的键，如果插入了相同的键，则新的值会替换旧的值。
允许空键和空值：
- HashMap 允许键为 null，也允许值为 null。
非线程安全：
- HashMap 不是线程安全的，这意味着在没有外部同步的情况下，多个线程同时修改 HashMap 可能会导致不可预知的结果。

动态扩容

动态扩容：
- 当 HashMap 中的元素数量超过负载因子（Load Factor）和当前容量的乘积时，HashMap 会进行扩容，通常是将容量增加到原来的两倍。
负载因子：
- HashMap 有一个负载因子，它是一个衡量哈希表满的程度的值。默认情况下，负载因子是 0.75，这意味着当哈希表的填充度达到 75% 时，HashMap 会进行扩容。

哈希冲突解决

哈希冲突解决：
- HashMap 使用链表来解决哈希冲突，当链表长度超过一定阈值（在 JDK 1.8 中是 8）时，链表会转换成红黑树，以提高搜索效率。

迭代顺序

迭代顺序：
- 在 JDK 1.8 及以后的版本中，HashMap 的迭代顺序是按照插入顺序来的，而在 JDK 1.7 及以前的版本中，迭代顺序是不确定的。

性能

快速失败的迭代器：
- HashMap 提供的迭代器是快速失败的，这意味着在迭代过程中，如果检测到 HashMap 发生了结构性修改（除了迭代器自身的 remove 方法），迭代器会立即抛出 ConcurrentModificationException。
性能：
- 在哈希函数分布均匀且没有太多哈希冲突的情况下，HashMap 提供了常数时间的性能（O(1)）来快速访问键值对。

容量和初始容量

初始容量：
- HashMap 有一个初始容量，如果不指定，那么默认的初始容量是 16。
容量总是2的幂：
- HashMap 的容量总是保持为2的幂，这是为了使得哈希值分布均匀，减少哈希冲突。

使用示例

HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);// 获取值
Integer value = map.get("two"); // 返回 2// 检查键是否存在
boolean containsKey = map.containsKey("three"); // 返回 true// 删除键值对
map.remove("one");// 遍历 HashMap
for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " = " + entry.getValue());
}

HashMap 是 Java 集合框架中非常灵活和高效的数据结构，适用于需要快速查找的场景。

HashMap和Hashtable的区别？

HashMap 和 Hashtable 都是 Java 中实现 Map 接口的类，用于存储键值对，但它们之间有几个关键的区别：

线程安全性：
- Hashtable 是线程安全的，它的方法内部进行了同步处理，适合在多线程环境下使用。
- HashMap 是非线程安全的，它在单线程环境下性能更优，但在多线程环境下需要外部同步。
对 null 的处理：
- Hashtable 不允许键（Key）或值（Value）为 null。
- HashMap 允许键或值为 null。
性能：
- 由于 HashMap 不需要进行同步，因此在单线程环境下它的性能通常优于 Hashtable。

由于 HashMap 提供了更好的性能和扩展性，并且在单线程环境下足够安全，因此在现代 Java 应用中，HashMap 通常比 Hashtable 更受欢迎。在需要线程安全的情况下，可以考虑使用 ConcurrentHashMap，它是 HashMap 的线程安全版本。

HashMap和HashSet的区别？

数据结构层面
- HashMap：
  - HashMap是基于哈希表（散列表）实现的Map接口。它存储的是键 - 值（key - value）对。例如，HashMap<String,Integer>可以用来存储学生姓名（作为键）和对应的成绩（作为值）。
  - 它内部通过一个数组（称为桶数组）来存储元素。当插入一个键值对时，先根据键的哈希值计算出它在数组中的存储位置（索引），如果这个位置已经有元素了（发生哈希冲突），就会使用链表或红黑树（当链表长度大于一定阈值时，为了提高查找效率，会将链表转换为红黑树）来存储多个具有相同哈希值的键值对。
- HashSet：
  - HashSet是基于哈希表实现的Set接口。它存储的是不重复的元素。例如，要存储一组学生的姓名，且姓名不能重复，就可以使用HashSet。
  - 它内部实际上是通过一个HashMap来实现的。HashSet中的元素被存储为HashMap的键，而值则是一个固定的虚拟值（在Java中通常是一个名为PRESENT的静态常量）。
功能特性方面
- 元素的访问方式：
  - HashMap：可以通过键来访问对应的值。例如，map.get(key)方法可以获取指定键对应的value。如果键不存在，会返回null（对于基本数据类型包装类的键，返回对应的默认值，如Integer类型返回null，int类型对应的默认值是0）。
  - HashSet：没有提供通过索引或者某个“键”来访问元素的方式。它主要用于检查元素是否存在于集合中，使用contains()方法来判断。例如，set.contains(element)返回一个布尔值，表示集合中是否包含指定的元素。
- 元素的重复性处理：
  - HashMap：键是不允许重复的，但是值可以重复。如果插入一个已经存在的键，新的值会覆盖旧的值。例如，map.put("key1", 1); map.put("key1", 2);此时，键"key1"对应的value为2。
  - HashSet：不允许有重复元素。在添加元素时，如果元素已经存在，添加操作会被忽略。例如，HashSet<String> set = new HashSet<>(); set.add("apple"); set.add("apple");最终集合中只有一个"apple"元素。

遍历方式的差异

HashMap：

可以通过遍历键值对集合（entrySet()方法）来获取键和值。例如：

HashMap<String,Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println("键: " + entry.getKey() + ", 值: " + entry.getValue());
}

也可以只遍历键集合（keySet()方法）或者值集合（values()方法）。

HashSet：

只能遍历元素集合本身。例如：

HashSet<String> set = new HashSet<>();
set.add("a");
set.add("b");
for (String element : set) {System.out.println(element);
}

HashMap和TreeMap的区别？

底层数据结构
- HashMap：
  - 底层是哈希表（数组+链表/红黑树）结构。当我们向HashMap中添加元素时，首先会根据键（key）的哈希值来确定元素在数组中的存储位置。
  - 例如，假设哈希函数为hash(key)，计算得到的哈希值为h，存储元素的数组为table，那么元素会尝试存储在table[h]这个位置。如果table[h]已经有元素存在（这种情况称为哈希冲突），就会将新元素以链表的形式连接在table[h]后面。在Java 8中，当链表的长度大于8且数组长度大于等于64时，链表会转换为红黑树，以提高查找效率。
- TreeMap：
  - 底层是红黑树结构。红黑树是一种自平衡的二叉查找树，它保证了树的高度在最坏情况下也能维持在对数级别，从而保证了查找、插入和删除操作的时间复杂度为 $O (l o g n)$ 。
  - 每个节点都包含一个键 - 值对，并且树中的键是按照一定的顺序排列的。例如，如果键是整数类型，那么会按照整数的大小顺序来构建红黑树；如果键是字符串类型，会按照字典序来排列。
元素存储顺序
- HashMap：
  - 不保证元素的存储顺序。因为它是基于哈希值来存储元素的，所以元素的顺序可能会因为哈希函数的实现、元素的添加和删除顺序等因素而发生变化。
  - 例如，连续两次添加相同的键 - 值对集合到HashMap中，它们在内部存储的顺序可能是不同的。这是因为在不同的运行环境或者JVM实现中，哈希函数的计算结果可能会有微小的差异。
- TreeMap：
  - 元素是按照键的顺序存储的。这个顺序可以是键的自然顺序（如果键实现了Comparable接口），也可以是通过自定义的比较器（Comparator）来确定的顺序。
  - 例如，对于一个TreeMap<String, Integer>，如果按照字符串的自然顺序，键为“apple”的元素会排在键为“banana”的元素之前；如果定义了一个比较器，按照字符串长度来比较，那么键为“a”的元素可能会排在键为“apple”的元素之前。
性能特点
- HashMap：
  - 在理想情况下（即没有哈希冲突或者哈希冲突很少），插入、删除和查找操作的时间复杂度可以接近 $O (1)$ 。这是因为通过哈希值可以直接定位到元素在数组中的大致位置，减少了搜索的范围。
  - 但是，在最坏的情况下（例如，所有元素的哈希值都相同，导致哈希冲突严重，形成一个很长的链表），时间复杂度会退化为 $O (n)$ 。不过这种情况在实际应用中很少出现，只要哈希函数设计合理，就能保证较好的性能。
- TreeMap：
  - 插入、删除和查找操作的时间复杂度始终为 $O (l o g n)$ 。因为红黑树的高度是维持在对数级别，每次操作都需要沿着树的路径进行比较和调整。
  - 相比于HashMap，TreeMap的性能在数据量较小或者操作不频繁时可能差异不大，但在数据量较大且对性能要求较高的情况下，HashMap通常会有更好的性能表现，尤其是在插入和查找操作方面。
适用场景
- HashMap：
  - 适用于需要快速插入、删除和查找键 - 值对的场景，并且对元素的存储顺序没有要求。例如，在缓存系统中，用于存储缓存数据的键 - 值对，方便快速获取缓存中的数据。
- TreeMap：
  - 适用于需要对键进行排序并且按照顺序遍历键 - 值对的场景。例如，在实现一个排行榜系统时，键可以是玩家的排名分数，值可以是玩家的信息，通过TreeMap可以方便地按照分数高低来排列玩家信息。

说说HashMap的底层实现

数据结构基础
- HashMap底层主要是基于数组和链表（在Java 8之后，当链表长度大于8且数组长度大于等于64时，链表会转换为红黑树）来实现的。
- 数组是存储元素的主体结构，它提供了快速访问的能力。每个数组元素被称为“桶（bucket）”。例如，假设定义了一个HashMap<String, Integer>，这个数组的每个元素（桶）可能存储一个或多个键值对（Entry）。
- 链表（或红黑树）用于处理哈希冲突。哈希冲突是指不同的键经过哈希函数计算后得到相同的数组索引。当发生哈希冲突时，新的键值对会以链表（或红黑树）的形式添加到对应的桶中。
哈希函数与索引计算
- HashMap使用键的哈希值来确定键值对在数组中的存储位置。哈希函数会将键对象转换为一个整数（哈希值）。例如，在Java中，Object类有一个hashCode()方法，它是获取哈希值的基础。
- 计算索引的方法通常是将哈希值与数组长度进行取模运算（index = hashCode(key) % arrayLength）。这样可以保证索引值在数组的范围之内。不过，在实际的Java HashMap实现中，为了优化性能和减少哈希冲突，会采用更复杂的位运算来计算索引。
- 例如，对于一个容量为16的HashMap，一个键的哈希值为20，通过20 & (16 - 1)（位运算等价于取模运算）得到索引为4，那么这个键值对就会尝试存储在数组的第4个位置（索引从0开始计数）。
put操作实现
- 当执行put(key, value)操作时，首先会计算键key的哈希值和对应的数组索引。
- 如果该索引位置的桶为空，那么就直接将键值对放入这个桶中。
- 如果桶不为空，说明发生了哈希冲突。此时会遍历链表（或红黑树）来查找是否已经存在相同的键。如果找到相同的键，就更新对应的value；如果没有找到，就将新的键值对添加到链表（或红黑树）的末尾。
- 在Java 8中，如果链表的长度大于8且数组长度大于等于64，就会将链表转换为红黑树，以提高后续查找操作的效率。转换过程涉及到复杂的红黑树构建和节点调整操作。
get操作实现
- 执行get(key)操作时，同样先计算键key的哈希值和对应的数组索引。
- 然后在该索引位置的桶中查找键。如果是链表，就逐个遍历链表节点，比较键是否相同；如果是红黑树，就利用红黑树的查找算法来寻找键。
- 一旦找到匹配的键，就返回对应的value；如果没有找到，就返回null。
扩容机制
- HashMap有一个负载因子（默认为0.75），当HashMap中元素的数量超过数组容量乘以负载因子时，就会触发扩容。
- 扩容操作会创建一个新的、更大的数组（通常是原来数组容量的2倍），然后将旧数组中的所有键值对重新计算哈希值和索引，并将它们放入新数组中。
- 这个过程比较复杂，因为涉及到大量的元素重新分配和可能的哈希冲突重新处理，但它确保了HashMap在元素增多时仍然能够保持较好的性能。例如，当一个HashMap初始容量为16，负载因子为0.75，当元素数量达到12时，就会触发扩容，新的容量将变为32。

什么是hash冲突？有什么办法减少hash冲突？

什么是hash冲突
- 定义：在哈希表（例如HashMap）中，hash冲突（也称为哈希碰撞）是指不同的键（key）经过哈希函数计算后得到相同的哈希值（hash value），从而导致这些键在哈希表中对应的存储位置（索引）相同的现象。
- 示例：假设哈希函数是简单地将键的字符编码相加后对哈希表长度取模（这只是一个简单示例，实际的哈希函数更复杂）。有两个键“abc”和“cba”，它们字符编码相加后的结果可能相同，当对哈希表长度取模后，可能会得到相同的索引，这就产生了哈希冲突。
减少hash冲突的方法
- 优化哈希函数
  - 均匀分布：设计一个能够使键的哈希值在哈希表的地址空间中尽可能均匀分布的哈希函数。例如，Java中的String类的hashCode函数，它通过一个复杂的算法来计算字符串的哈希值，使得不同的字符串有较大概率得到不同的哈希值。
  - 对于整数键，可以采用简单的取模运算（例如hash(key)=key % tableLength），但这种方法可能会导致哈希冲突，更好的方法是采用位运算等复杂操作。例如，MurmurHash是一种非加密型哈希函数，它能够快速生成高质量的哈希值，使哈希值分布更加均匀。
- 适当调整哈希表容量
  - 初始容量选择：在创建哈希表时，合理选择初始容量。例如，在使用Java的HashMap时，如果预先知道大概要存储的元素数量，可以通过构造函数指定一个合适的初始容量。如果初始容量过小，容易导致负载因子过高，增加哈希冲突的概率；如果初始容量过大，会浪费存储空间。
  - 动态扩容：当哈希表的负载因子（元素数量与哈希表容量之比）达到一定阈值时，对哈希表进行扩容。例如，HashMap默认的负载因子是0.75，当元素数量超过容量乘以0.75时，会触发扩容。扩容后的哈希表容量通常是原来的2倍，这样可以使更多的键有新的存储位置，减少哈希冲突。
- 使用开放定址法或再哈希法（辅助哈希函数）等冲突解决策略（较复杂，实际应用相对少）
  - 开放定址法：当发生哈希冲突时，使用某种探测策略在哈希表中寻找下一个可用的存储位置。例如，线性探测法是指当发生冲突时，顺序地查找下一个空闲的存储位置。假设哈希表索引为i的位置发生冲突，就依次检查i + 1、i + 2等位置，直到找到空闲位置。不过这种方法容易导致聚集现象，即连续的存储位置被占用，增加后续冲突的概率。
  - 再哈希法：当发生哈希冲突时，使用另一个哈希函数来重新计算哈希值，以确定新的存储位置。例如，有主哈希函数h1(key)和辅助哈希函数h2(key)，当h1(key)发生冲突时，使用h2(key)来寻找新的位置。这种方法的难点在于设计合适的辅助哈希函数，并且计算成本相对较高。

为什么HashMap的容量总是2的幂次方？

高效的索引计算
- HashMap通过计算键（key）的哈希值来确定元素在数组中的存储位置（索引）。当容量为2的幂次方时，可以使用位运算（&）来代替取模（%）运算，提高计算效率。
- 例如，假设数组容量为 $2^n$ ，计算索引的公式为index = hashCode(key) & (2^n - 1)。这与index = hashCode(key) % 2^n是等价的，但位运算的速度比取模运算快很多。因为计算机在处理位运算时，底层的硬件实现更简单直接，而取模运算涉及到除法操作，相对复杂。
- 以容量为16（ $2^4$ ）为例， $16 - 1 = 15$ ，二进制表示为1111。当一个键的哈希值与1111进行位与运算时，实际上就是取哈希值的低4位作为索引，这样可以快速地得到索引值，并且保证索引在数组范围之内。
减少哈希冲突
- 2的幂次方的容量有助于使哈希值在数组中更均匀地分布。因为哈希函数计算出的哈希值的二进制位在与容量 - 1进行位与运算时，会有更好的随机性。
- 假设哈希函数产生的哈希值是比较均匀分布的，那么使用2的幂次方的容量可以让这些哈希值在数组的各个位置都有比较均匀的分布机会。相比之下，如果容量不是2的幂次方，例如容量为10，那么在计算索引时，哈希值的不同二进制位组合与10取模后的结果可能会导致某些索引位置更容易被命中，从而增加哈希冲突的概率。
方便扩容操作
- HashMap在扩容时，容量会变为原来的2倍。由于初始容量是2的幂次方，扩容后的容量依然是2的幂次方。
- 这种扩容方式使得元素在重新计算索引时，只需要考虑哈希值的高位增加的部分。例如，从容量为16扩容到32，原来哈希值的低4位用于计算在16容量下的索引，扩容后，哈希值的低5位用于计算在32容量下的索引，这样可以相对高效地重新分配元素，减少重新计算哈希值带来的性能损耗。

Map的get方法的时间复杂度是多少？

对于HashMap（理想情况）
- 在理想情况下，也就是没有或者很少出现哈希冲突时，HashMap的get方法的时间复杂度接近 $O (1)$ 。
- 这是因为HashMap是基于哈希表实现的，其内部通过一个数组（桶数组）来存储元素。当调用get方法时，它首先会根据键（key）的哈希值计算出该键在数组中的存储位置（索引）。例如，通过index = hash(key) % arrayLength（实际Java中会使用更高效的位运算）这种方式来计算索引。
- 然后直接访问这个索引位置对应的元素。如果这个位置正好存储了要查找的键值对，那么就可以立即返回对应的value，所以这种情况下查找速度非常快，时间复杂度接近常数级别。
对于HashMap（最坏情况）
- 在最坏的情况下，例如所有的键经过哈希函数计算后都得到相同的索引（这是一种极端情况，实际中很少出现，除非哈希函数设计得非常差），此时HashMap的get方法的时间复杂度会退化为 $O (n)$ 。
- 因为当发生这种情况时，所有的键值对会存储在同一个桶中，形成一个很长的链表（在Java 8之前）或者红黑树（在Java 8之后，当链表长度达到一定阈值会转换为红黑树）。当调用get方法时，就需要遍历这个链表或者红黑树来查找键，平均需要遍历 $n /2$ 个元素，所以时间复杂度为 $O (n)$ 。
对于TreeMap
- TreeMap的get方法时间复杂度是 $O (l o g n)$ 。
- TreeMap是基于红黑树实现的。红黑树是一种自平衡的二叉查找树，在树中查找一个元素时，每次比较都会排除掉一半的树节点。例如，从根节点开始比较键的大小，如果要查找的键比根节点的键大，就往树的右子树查找；如果比根节点的键小，就往树的左子树查找。
- 由于红黑树的高度始终保持在 $O (l o g n)$ 级别（ $n$ 是树中的节点数量），所以在TreeMap中查找一个键的时间复杂度是 $O (l o g n)$ 。