章
目
录
1. 介绍
HashMap,作为Java集合框架的一部分,用于快速和高效地存储和检索键值对。在要存储在HashMap中的键值对(也称为条目)中,键必须是唯一的对象,而值可以重复。
键用于执行快速查找。当检索值时,我们必须传递相关的键。如果在HashMap中找到键,它将返回值,否则返回null。
HashMap<String, String> map = new HashMap<>();
map.put("+1", "USA");
map.put("+91", "India");
map.get("+1"); //返回 "USA"
map.get("+2"); // 返回null
请注意,HashMap是一个无序集合,不保证键值对的插入顺序。在调整大小操作期间,内部顺序可能会更改。
此外,HashMap不提供线程安全性,因此在并发程序中使用它可能会导致存储在HashMap中的键值对的不一致状态。
2.创建HashMap
2.1. 使用默认构造函数
我们可以根据需求使用不同的方式创建HashMap。例如,我们可以创建一个最初不包含键值对的空HashMap。稍后,我们可以向这个空HashMap中添加键值对。
HashMap<String, String> map = new HashMap<>();
此外,我们可以在本文稍后讨论的性能原因下指定初始加载容量和加载因子。请注意,初始容量必须是2的幂,加载因子应在0和1之间。
HashMap<String, String> map = new HashMap<>(64, 0.90f);
2.2. 使用复制构造函数
或者,我们还可以使用现有映射初始化HashMap。在以下代码中,映射中的条目将被复制到copiedMap中。
HashMap<String, String> copiedMap = new HashMap<>(map);
我们可以修改映射中的条目,而不会影响另一个映射中的条目。请注意,在复制条目后,来自两个映射的键和值对象引用内存中的相同对象。因此,重要的是要理解对值对象进行更改会反映在两个映射中。
HashMap<Integer, Item> map = new HashMap<>();
map.put(1, new Item(1, "Name"));
// 带有复制条目的新Map
HashMap<Integer, Item> copiedMap = new HashMap<>(map);
// 更改一个映射中的值对象
copiedMap.get(1).setName("Modified Name");
// 更改在两个map中都可见
System.out.println(map.get(1)); // Item(id=1, name=Modified Name)
System.out.println(copiedMap.get(1)); // Item(id=1, name=Modified Name)
3. 常见HashMap操作
让我们探讨在任何应用程序中执行的HashMap条目的常见操作。
3.1. 添加键值对(put)
HashMap.put()方法存储指定的值并将其与指定的键关联。如果映射先前包含键的映射,则旧值将替换为新值。
HashMap<String, String> hashmap = new HashMap<>();
hashmap.put("+1", "USA"); // 存储
hashmap.put("+1", "United States"); // 用 United States覆盖USA
hashmap.get("+1"); //返回 United States
3.2. 按键检索值(get)
HashMap.get()方法返回指定键映射到的值,如果映射不包含键的映射,则返回null。
hashmap.put("+1", "USA");
hashmap.get("+1"); // 返回USA
hashmap.get("+2"); // 返回null
如果应用程序允许我们将null值放入映射中,那么我们可以使用containsKey()方法来验证键是否不存在或映射的值是否为null。
3.3. 按键删除条目(remove)
HashMap.remove()方法删除指定键的键值对。
hashmap.remove("+1");
3.4. 检查键/值是否存在(containsKey,containsValue)
containsKey()方法返回true,如果哈希映射包含指定键的映射。否则,它返回false。
hashmap.put("+1", "USA");
hashmap.containsKey("+1"); //返回true
hashmap.containsKey("+2"); //返回false
类似地,containsValue()方法返回true,如果哈希映射包含一个或多个具有指定值的键值对。否则,它返回false。
hashmap.put("+1", "USA");
hashmap.containsValue("USA"); //返回 true
hashmap.containsValue("Canada"); //返回 false
3.5. 遍历HashMap
我们可以使用从以下方法返回的不同集合视图来遍历HashMap的键、值或条目:
- keySet() 以迭代键并访问值
- entrySet() 以迭代键值对
for (String key : hashmap.keySet()) {
System.out.println("Key: " + key);
System.out.println("Value: " + hashmap.get(key));
}
for (Map.Entry<String, String> entry : hashmap.entrySet()) {
System.out.println("Key: " + entry.getKey());
System.out.println("Value: " + entry.getValue());
}
我们还可以使用forEach()方法以更清晰的方式迭代条目。
hashmap.forEach((key, value) -> System.out.println(key + ": " + value));
3.6. 使用Java 8流与HashMap
Java Stream API提供了一种简洁的方式以流畅的方式处理对象集合。我们可以主要使用HashMap类的流来将现有流收集到HashMap中。
为了将流元素收集到HashMap中,我们可以使用Stream.collect()方法以及Collectors.toMap()收集器。
Stream<Item> stream = Stream.of(new Item(1, "Item 1"), new Item(2, "Item 2"));
Map<Long, String> itemMap = stream.collect(
Collectors.toMap(Item::getId, Item::getName, (oldValue, newValue) -> oldValue, HashMap::new)
);
System.out.println(itemMap); // {1=Item 1, 2=Item 2}
只需提一下,我们可以使用Stream API对映射条目进行排序并将它们存储在另一个保持插入顺序的映射中,例如LinkedHashMap。
LinkedHashMap<Long, String> sortedMap = stream.entrySet().stream()
.sorted(Map.Entry.comparingByKey())
.collect(
Collectors.toMap(Map.Entry::getKey,
Map.Entry::getValue,
(oldValue, newValue) -> oldValue,
LinkedHashMap::new)
);
4. Java中的HashMap实现
尽管不强制要求了解HashMap类的内部工作方式以有效地使用它,但了解“HashMap如何工作”将扩展您在这个主题以及Map数据结构的整体理解方面的知识。
HashMap在内部使用HashTable来存储条目。HashTable将键值对存储在基于数组的结构中,并使用哈希函数将键映射到数组中的特定索引。数组也被称为桶数组。
自Java 8以来,桶被实现为一个链表。通过使用链表,我们可以在单个桶中存储多个条目。为了提高性能,当节点数达到阈值时(默认值为8),链表将转换为RedBlack树。当节点数降至阈值以下(默认值为6)时,树将转换回链表。
您可以阅读本文以深入了解HashMap的内部实现。
5.HashMap 性能和优化
在大多数实际应用中,我们通常只会在 HashMap 中存储很少的条目(也许少于 100)。在这种情况下,任何性能优化都对性能影响不大,通常不需要。
在其他情况下,当我们希望在 HashMap 中存储数百万个条目时,我们应该进行以下的审查。
5.1. 时间复杂度分析
在插入、删除和检索操作期间,HashMap 操作的复杂度通常是平均恒定的(O(1))。请注意,复杂度高度依赖于分布均匀的哈希函数和适当的加载因子。
在最坏的情况下,由于哈希冲突,所有键最终都会结束在相同的桶中,导致桶形成链表或树,从而导致线性时间复杂度(O(n))。
- 平均情况:O(1)
- 最佳情况:O(1)
- 最坏情况:O(n)
5.2. 减少冲突和调整大小开销
如上所述,创建一个可以将键均匀分布在可用桶中的好哈希函数非常重要,以减少冲突的可能性。
内置 Java 类型(如 String、Integer、Long 等)的默认 hashCode() 函数在大多数情况下都做得很好。因此,强烈建议在 HashMap 中使用 Java 字符串或包装类作为键。
如果我们需要创建自定义键类,下面的指南将有助于我们设计一个良好的自定义键用于 HashMap。
例如,在以下的 Account 类中,我们已重写了 hashCode 和 equals 方法,并仅使用账户号来验证 Account 实例的唯一性。账户类的所有其他可能属性都可以在运行时更改。
public class Account {
private int accountNumber;
private String holderName;
//constructors, setters, getters
//Depends only on account number
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + accountNumber;
return result;
}
//Compare only account numbers
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Account other = (Account) obj;
if (accountNumber != other.accountNumber)
return false;
return true;
}
}
您可以根据自己的要求更改上述的实现。
5.3. 内存效率和垃圾回收
通常,内存效率是根据预期的要存储的条目数来设置适当的初始容量和加载因子的结果。这有助于减少调整大小操作的次数,从而减小 put() 操作期间的临时内存开销。
估算理想的初始容量很重要,因为过高估计会导致浪费内存,而过低估计会导致增加调整大小操作的次数。
为了进一步避免内存问题,在不再需要时应适当清除条目。删除不必要的条目或清空 HashMap 可以帮助释放内存。
在某些情况下,存储为键或值的对象可能具有 finalizer。这种对象具有更复杂的生命周期,可能会影响垃圾回收的效率。
6.常见陷阱及如何避免
6.1. ConcurrentModificationException
ConcurrentModificationException 在集合在迭代时同时进行修改时发生。在 HashMap 的情况下,如果我们在迭代时使用其集合视图(keySet、valueSet、entrySet)并在迭代期间修改 HashMap,将会导致 ConcurrentModificationException。
for (Map.Entry<String, Integer> entry : nameMap.entrySet()) {
if (entry.getKey().startsWith("Temp-")) {
nameMap.remove(entry.getKey()); // 抛出ConcurrentModificationException
}
}
在这种情况下,可以使用迭代器进行迭代和修改集合。
Iterator<Entry<String, Integer>> iterator = nameMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if (entry.getKey().equals("Temp-")) {
iterator.remove(); //安全移除元素
}
}
6.2. 使用可变键
这也是经常出现的常见问题。非常重要的是要理解作为键使用的对象的哈希码不应更改,否则以前存储的条目将丢失,从而导致内存泄漏。
User user = new User(1, "Name");
map.put(user, new Account(...));
user.setname("New Name"); //它会更改hashcode
//返回null并导致内存泄漏,因为Account对象不可访问
map.get(user);
为了防止这种泄漏,我们应该使用不可变对象作为 Map 键。不可变对象一旦创建,就不能更改,因此其哈希码也永远不会更改。出于这个原因,Java 包装类和字符串最适合用作 Map 键。
map.put(user.getId(), new Account(...)); //用户id无法更改
7.HashMap
的变种和替代品 HashMap 是一个通用类,不适用于特定情况,比如排序和排序。在这种情况下,我们应该考虑使用为特定目的创建的其他 Map 类。
7.1. 使用 LinkedHashMap
保持插入顺序 LinkedHashMap 以添加顺序存储条目。因此,它提供可预测的迭代顺序。请注意,如果将键重新插入映射,插入顺序不受影响。
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("key1", "value1");
linkedHashMap.put("key2", "value2");
7.2. 使用 TreeMap
对键进行排序 如果我们想要按键对 Map 条目进行排序,可以使用 TreeMap。TreeMap 根据其键的自然排序或在映射创建时提供的比较器进行排序。
请注意,保持排序顺序会增加插入和调整大小操作的额外成本。
Map<String, String> treeMap = new TreeMap<>();
TreeMap<Integer, String> reversedMap = new TreeMap<>(Collections.reverseOrder());
7.3. 使用 ConcurrentHashMap
进行线程安全 ConcurrentHashMap 与 HashMap 类非常相似,不同之处在于 ConcurrentHashMap 提供了内部维护的并发性。这意味着在多线程应用程序中访问其键-值对时,无需使用同步块。
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
7.4. 使用 WeakHashMap
实现内存效率 如果无法跟踪添加到 Map 中的条目,应考虑使用 WeakHashMap。在 WeakHashMap 中,当其键不再在普通使用中时,条目将自动被移除。
此类主要用于具有 equals() 方法使用 == 运算符测试对象身份的键对象。一旦这样的键被丢弃,就再也无法重新创建它,因此不可能在 WeakHashMap 中查找该键。
Map<String, String> weakMap = new WeakHashMap<>();
7.5. 在不同 Map 类型之间进行互操作和转换
我们可以使用 Map 构造函数从现有的 HashMap 创建另一个 Map 类型的实例。每个 Map 类都包含一个接受另一个 Map 类型的构造函数,用指定映射的条目初始化当前映射。
在以下示例中,我们正在使用现有的 HashMap 存储的条目创建 ConcurrentHashMap。这种技术可用于任何类型的 Map 转换。
HashMap<String, String> hashMap = new HashMap<>();
//添加几个条目
//使用HashMap中的条目创建ConcurrentHashMap
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>(hashMap);
8.HashMap 的真实应用场景
由于其高效的键值对存储和检索,HashMap 在各种真实场景中被广泛使用。让我们看一下一些流行的用途:
8.1. 使用 HashMap 进行缓存
HashMap 用于在小型应用程序中实现临时缓存机制,其中配置和使用全功能缓存解决方案将过度。
它还有助于通过减少与缓存系统或数据库的额外交互来提高性能。对于小型数据集,它也可以替代内存数据库。
8.2. 频率计数和单词出现
HashMap 可以用于计算数据集中项目或元素的出现次数,这使它在与频率分析相关的工作中非常有价值。这在自然语言处理和文本处理中非常有帮助。
String[] items = {"apple", "banana", "orange", "apple", "grape", "banana", "apple"};
HashMap<String, Integer> itemOccurrences = new HashMap<>();
for (String item : items) {
itemOccurrences.put(item, itemOccurrences.getOrDefault(item, 0) + 1);
}
System.out.println(itemOccurrences); // {banana=2, orange=1, apple=3, grape=1}
8.3. 图算法
在图算法(如图遍历和最短路径算法)中,HashMap 通常用于存储图节点及其属性。它还可以高效地表示邻接表表示法。
使用 HashMap 使这些算法高效且易于实现。
9.结论
- HashMap 类是 Java 集合的重要组成部分,用于许多关键设计中。最后,总结一下本文中学到的内容:
- HashMap 存储键值对(也称为条目)。 HashMap 不能包含重复的键。
- HashMap 允许多个 null 值,但只允许一个 null 键。
- HashMap 是无序集合,不保证元素的特定顺序。
- HashMap 不是线程安全的。您必须显式同步对 HashMap 的并发修改。或者您可以使用 Collections.synchronizedMap(hashMap) 来获得 HashMap 的同步版本。
- 只能使用相关联的键检索值。
- HashMap 只存储对象引用。因此,请使用包装类或字符串来创建 Map 键。
- HashMap 实现了 Cloneable 和 Serializable 接口。