在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

kdn251/面试

菜单

哈希表

相关源文件

本页面详细介绍了哈希表，这是一种用于高效存储和检索键值对的基础数据结构。哈希表在插入、删除和查找操作上提供了平均恒定的时间复杂度，使其成为解决许多技术面试问题的必备工具。有关其他非线性数据结构的信息，请参阅树和图。

什么是哈希表？

哈希表（或哈希映射）是一种实现关联数组抽象数据类型的数据结构，它可以将键映射到值。哈希表使用散列函数来计算数组桶的索引，然后从中找到所需的值。

哈希表的主要特点是它们能够在平均情况下以恒定的时间执行查找、插入和删除操作，而无论数据集的大小如何。

来源： README.md161-174

哈希函数

散列函数将任意大小的输入数据转换为固定大小的值，称为哈希码或哈希值。理想的散列函数应

  1. 将键均匀地分布在数组中
  2. 计算效率高
  3. 最小化冲突（两个键映射到同一索引）

来源： README.md161-174

冲突解决

当两个不同的键散列到同一索引时，就会发生冲突。处理冲突主要有两种方法：

分离链表法（Separate Chaining）

在分离链表法中，哈希表的每个桶都包含一个链表，存储哈希到同一索引的所有元素。当发生冲突时，只需将元素添加到该索引桶的链表末尾。

开放寻址法（Open Addressing）

在开放寻址法中，当发生冲突时，算法会根据某种探测序列在数组中寻找下一个可用槽。常见的探测方法包括：

  • 线性探测：依次检查下一个槽
  • 二次探测：按二次间隔检查槽
  • 双重散列：使用第二个散列函数确定间隔

来源： README.md161-174

时间复杂度

哈希表提供了高效的性能特征：

操作平均情况最坏情况
访问不适用不适用
搜索O(1)O(n)
插入O(1)O(n)
删除O(1)O(n)

最坏情况发生在许多键散列到同一索引（导致大量冲突）或哈希表需要调整大小时。

来源： README.md161-174

Java 中的哈希表实现

Java 提供了几种内置的哈希表实现：

  1. HashMap：通用的实现，将键映射到值。
  2. HashSet：Set 接口的实现，底层由 HashMap 支持。
  3. LinkedHashMap：保留插入顺序的 HashMap。
  4. ConcurrentHashMap：用于并发访问的线程安全版本。

使用哈希表的示例问题

哈希表常用于高效解决各种算法问题。让我们从仓库中看一些例子：

1. 存在重复元素（Contains Duplicate）

这个问题询问数组中是否存在重复元素。使用哈希表可以提供 O(n) 的解决方案。

实现会维护一个 HashMap 来跟踪已见的元素。

company/airbnb/ContainsDuplicate.java4-17

来源： company/airbnb/ContainsDuplicate.java1-17 leetcode/hash-table/ContainsDuplicate.java1-17 company/palantir/ContainsDuplicate.java1-17 company/yahoo/ContainsDuplicate.java1-17

2. 字符串中的第一个唯一字符（First Unique Character in a String）

这个问题要求找出字符串中的第一个非重复字符。哈希表用于跟踪字符的频率和位置。

实现过程

leetcode/hash-table/FirstUniqueCharacterInAString.java13-33

来源： leetcode/hash-table/FirstUniqueCharacterInAString.java1-35 company/amazon/FirstUniqueCharacterInAString.java1-35 company/microsoft/FirstUniqueCharacterInAString.java1-35 company/google/FirstUniqueCharacterInAString.java1-35 company/bloomberg/FirstUniqueCharacterInAString.java1-35

使用哈希表的最佳实践

在使用哈希表时，请考虑以下几点：

  1. 选择合适的初始容量：太小会导致频繁调整大小；太大会浪费内存。
  2. 选择好的散列函数：确保均匀分布以最小化冲突。
  3. 考虑键的特性：对于自定义对象，请正确实现 hashCode() 和 equals() 方法。
  4. 注意内存使用：哈希表以空间换时间。
  5. 根据您的用例和预期数据选择正确的冲突解决策略。

何时使用哈希表

在以下情况，哈希表是理想的选择：

  1. 需要快速查找、插入和删除。
  2. 数据具有唯一的键。
  3. 内存使用不是关键问题。
  4. 不需要有序数据。

它们不太适合以下情况：

  1. 需要维护特定的元素顺序。
  2. 内存效率至关重要。
  3. 需要执行基于范围的搜索。

总结

哈希表是一种强大的数据结构，可为关键操作提供 O(1) 的平均时间复杂度。通过理解它们的原理和适用场景，您可以高效地解决许多技术面试问题。本仓库包含了在解决常见问题时使用哈希表的各种示例，为技术面试提供了宝贵的实践机会。

来源： README.md161-174