Java 中的索引映射（或允许负数的平凡哈希）

索引映射，也称为简单哈希，是一种将数组元素映射到新数组索引的技术。这可用于有效地执行查找重复项或计算数组中元素出现次数等操作。索引映射的一种常见实现是使用一个数组，其中索引对应于原始数组的元素，而值表示每个元素的出现次数。这种方法效率很高，因为通过索引访问数组中的元素需要恒定的时间。

但是，当数组的元素可能为负数时，索引映射方法会变得更具挑战性。在这种情况下，我们需要确保负索引被映射到新数组中的正索引。一种实现此目的的方法是向索引添加一个固定的偏移值。例如，如果数组包含负值且最小值为 -10，我们可以将 10 加到每个索引上，以获得从 0 到 (max-min)+10 的有效索引范围。

处理简单哈希中的负值

使用布尔数组

在 Java 中处理索引映射或简单哈希中的负数时，我们可以使用偏移值将可能输入值的范围移至从零开始。这可以通过查找输入数组中的最小负值并将其绝对值添加到所有元素来实现。

例如，考虑输入数组 {-3, -1, 2, 5, -4}。此数组中的最小负值为 -4。将 -4 的绝对值（即 4）添加到数组中的所有元素会得到 {1, 3, 6, 9, 0}。我们现在可以创建一个大小为 10（数组中的最大值加 1）的索引映射数组，并使用此偏移值 4 将输入数组中的值映射到映射数组中的索引。

当访问映射数组中的元素时，我们可以简单地减去偏移值来检索原始值。例如，如果我们想检索索引 2 处的值（对应于原始值 2），我们将访问索引 6 处的映射数组（2 + 4），然后减去偏移值 4 以获得原始值 2。

总之，在 Java 中处理索引映射或简单哈希中的负数时，我们可以使用偏移值将可能输入值的范围移至从零开始，然后在从映射数组中检索原始值时减去此偏移值。

a) 初始化一个所有值都设置为零的哈希矩阵。

b) 遍历给定数组。

1. 如果元素为非负数，则将矩阵中对应的哈希值设置为 1，位于 [ele][0]。
2. 但是，如果元素为负数，则取其绝对值，并将对应的哈希值设置为 1，位于 [ele][1]。

c) 搜索数组中的特定元素

1. 检查给定元素 X 是否为非负数。
2. 如果 X 为非负数，请检查 [X][0] 处的值是否为 1。
3. 如果为 1，则表示该元素存在于数组中。
4. 否则，它不存在。

d) 但是，如果 X 为负数

1. 取 X 的绝对值。
2. 检查 [X][1] 处的值是否为 1。
3. 如果为 1，则表示该元素存在于数组中。
4. 否则，它不存在。

实施

文件名： IndexMapping.java

输出

Present

解释

此 Java 程序实现了直接索引映射，允许负数。该程序初始化一个所有值都设置为 false 的哈希矩阵。然后，它遍历给定数组，检查每个元素是负数还是非负数。如果元素为非负数，则将矩阵中对应的哈希值设置为 true，位于 [ele][0]。但是，如果元素为负数，则取元素的绝对值，并将对应的哈希值设置为 true，位于 [ele][1]。为了搜索数组中的特定元素，程序会检查给定元素 X 是非负数还是负数。如果 X 为非负数，它会检查 [X][0] 处的值是否为 true。如果为 true，则表示该元素存在于数组中，否则不存在。同样，如果 X 为负数，它会取 X 的绝对值并检查 [X][1] 处的值是否为 true。

复杂度分析

将元素插入哈希矩阵的时间复杂度为 O(n)，其中 n 是给定数组中的元素数量。在哈希矩阵中搜索元素的时间复杂度为 O(1)，因为我们直接使用元素的索引来访问矩阵。因此，算法的总体插入时间复杂度为 O(n)，搜索时间复杂度为 O(1)。

算法的空间复杂度为 O(MAX+1)，即哈希矩阵的大小。但是，由于矩阵的大小固定为 1001，因此空间复杂度可以视为常数。

总之，算法的插入时间复杂度为 O(n)，搜索时间复杂度为 O(1)，空间复杂度为 O(1)。

使用取模运算符

要实现 Java 中的简单哈希，可以使用内置的取模运算符 (%) 来计算给定键的哈希码。

文件名： TrivialHashing.java

输出

12 is not present in the hash table.

解释： 上面的 Java 程序实现了索引映射（或简单哈希）技术来在哈希表中插入和搜索元素。该程序将哈希表初始化为所有元素都设置为 -1，并使用一个哈希函数，该函数通过取元素与表大小的模来将元素映射到数组索引。为了处理负键，哈希函数使用额外的步骤，将取模运算的结果加上表大小，然后再次取模，以确保结果始终为非负数。insert() 函数通过查找空槽（使用线性探测）来在哈希表中插入元素，而 search() 函数通过探测直到找到元素或遇到空槽来在哈希表中搜索元素。main() 函数通过插入包含负键和正键的数组并搜索键 12 来测试程序。

复杂度分析

简单哈希算法的时间复杂度取决于键的分布和哈希表的大小。在最坏的情况下，当所有键都发生冲突时，插入和搜索操作的时间复杂度都将是 O(n)，其中 n 是哈希表的大小。但是，如果键集分布良好，则这两个操作的预期时间复杂度将是 O(1)，因为大多数冲突将通过线性探测来解决。就空间复杂度而言，哈希表需要 O(n) 的空间，其中 n 是表的大小。在此实现中，表大小固定为 20，这是一个相对较小的值，因此只要输入分布良好，该算法很可能会表现良好。

简单哈希的性能考量

简单哈希是 Java 中一种简单高效的数据存储和检索方法，但我们还需要考虑一些性能因素。

一个主要的考虑因素是数组的大小。如果数组太大，将会有很多冲突，导致检索时间变慢。另一方面，如果数组太小，将会有很多浪费的空间，导致内存使用量增加。

另一个考虑因素是数据元素的分布。如果数据元素分布不均匀，将会有很多冲突，导致检索时间变慢。例如，如果我们想存储学生的成绩，而所有学生的学号都是 10 的倍数，那么将会有很多冲突，导致检索时间变慢。

1. 冲突：简单哈希容易发生冲突，即不同的键可能映射到同一个哈希值。这可能导致性能下降和查找时间增加。为减轻这种情况，可以使用链式法或开放寻址法等技术。
2. 分布：键的分布会影响简单哈希的性能。如果键分布不均匀，某些哈希值可能会比其他哈希值更频繁地被访问，导致冲突增加和查找时间变慢。为解决此问题，可以使用通用哈希等技术。
3. 表大小：哈希表的大小会影响简单哈希的性能。过小的表可能会导致高冲突率，而过大的表可能会导致内存浪费。根据预期的键数量选择合适的表大小可以提高性能。
4. 键大小：键的大小也会影响简单哈希的性能。如果键较小，取模运算的开销可能会增加，导致查找时间变慢。可以使用较小的哈希函数或不同的哈希方法等技术来解决此问题。
5. 负载因子：负载因子是键的数量与哈希表大小的比率。根据预期的键数量选择合适的负载因子可以提高性能。高负载因子可能导致冲突增加和查找时间变慢，而低负载因子可能导致内存浪费。
6. 重新哈希：随着键的数量增加，可能需要重新哈希表以提高性能。重新哈希涉及创建一个更大的表并将键移动到新位置。这可能是一项开销很大的操作，但可能需要随着时间的推移来维持良好的性能。
7. 安全性：简单哈希不安全，容易受到生日攻击和哈希泛洪攻击。如果安全性是一个问题，应使用更安全的哈希方法，如 SHA-2 或 SHA-3。