HashMap实现

概述

HashMap 实现提供了一个自定义的、教育性的哈希映射数据结构实现。与 Java 内置的 HashMap 不同，此实现进行了简化，以演示核心哈希映射概念，同时仍提供插入、删除和搜索等关键操作的功能。

来源： src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java3-10

架构

HashMap 实现由三个主要组件以分层结构组织而成：

组件说明

HashMap 类：管理桶数组并提供与哈希映射交互的公共 API 的主要容器。
LinkedList 类：一个嵌套的静态类，实现了链表用于分离链法冲突解决。
Node 类：一个嵌套的静态类，表示链表中的单个键值对。

来源

内部结构

HashMap 使用一个 LinkedList 对象数组（桶）来存储数据。当插入键值对时，键的哈希码决定它属于哪个桶。

来源： src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java11-28

哈希函数

HashMap 实现使用一个简单的哈希函数来确定桶的放置位置：

此函数

通过将 null 键放置在桶 0 中来处理 null 键
使用模运算将键分布到可用的桶中
通过将 hashSize 添加到负值来确保哈希码非负

来源： src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java37-43

核心操作

插入操作

insert 方法将键值对添加到 HashMap 中。

如果键已存在，则更新其值。否则，将新节点添加到桶的链表中。

来源

搜索操作

search 方法检索与键关联的值。

来源

删除操作

delete 方法从 HashMap 中移除键值对。

来源

其他操作

该实现还包括：

display()：将每个桶的内容打印到控制台。
clear()：通过重新初始化所有桶来移除所有条目。
size()：返回非空桶的数量。

来源

src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMap.java82-108

性能分析

操作的时间复杂度取决于哈希函数将键分布到桶中的效果。

操作	平均情况	最坏情况
插入	O(1)	O(n)
搜索	O(1)	O(n)
删除	O(1)	O(n)

最坏情况发生在所有键哈希到同一个桶时，导致所有操作退化为线性时间，因为它们必须遍历整个链表。

空间复杂度为 O(n + m)，其中 n 是键值对的数量，m 是桶的数量。

使用示例

测试用例中的基本使用模式：

来源： src/test/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapTest.java11-43

处理冲突

该实现使用分离链法处理哈希冲突，如测试中所示：

来源： src/test/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapTest.java69-79

边缘情况处理

该实现处理各种边缘情况：

边缘情况	行为
空键	存储在桶 0 中
空值	支持
重复键	更新现有值
不存在的键	搜索时返回 null
删除不存在的键	无影响

来源

与 Java 内置 HashMap 的比较

功能	自定义 HashMap	Java 内置 HashMap
实现	简单的分离链法和链表	使用链表进行分离链法，对于大型桶会转换为平衡树
动态调整大小	否	是（当负载因子超过阈值时进行重新哈希）
空键	支持	支持
空值	支持	支持
枚举	仅有 display 方法	键、值和条目的迭代器
大小	返回非空桶的数量	返回条目的总数
线程安全	非线程安全	非线程安全

局限性和潜在改进

固定大小：该实现不动态调整桶的大小，可能导致在条目很多时性能下降。
size 方法：返回桶的数量而不是条目的数量。
无迭代：没有方法可以迭代键、值或条目。
性能：没有针对大型冲突链进行优化。

潜在的改进包括基于负载因子动态调整大小、正确的尺寸计数以及键/值迭代器。