散列

散列非常高效。使用哈希来搜索、插入和删除元素需要 O(1) 时间。在平衡良好的搜索树中，可以在 O(log n) 时间内找到一个元素。有没有更有效的方法来搜索容器中的元素？本章介绍一种称为散列的技术。您可以使用哈希来实现映射或集合，以在 O(1) 时间内搜索、插入和删除元素。

什么是哈希？

哈希使用哈希函数将键映射到索引。在介绍哈希之前，我们先回顾一下map，它是一种利用哈希实现的数据结构。回想一下，map（在本节中介绍）是一个存储条目的容器对象。每个条目包含两部分：键和值。该键也称为搜索键，用于搜索相应的值。例如，字典可以存储在映射中，其中单词是键，单词的定义是值。

映射也称为字典、哈希表或关联数组。

Java Collections Framework 定义了用于建模地图的 java.util.Map 接口。三个具体实现是 java.util.HashMap、java.util.LinkedHashMap 和 java.util.TreeMap。 java.util.HashMap 使用哈希实现，java.util.LinkedHashMap 使用 LinkedList 实现，java.util.TreeMap 使用红色实现-黑树。

如果你知道数组中某个元素的索引，则可以使用该索引在 O(1) 时间内检索该元素。那么这是否意味着我们可以将值存储在数组中并使用键作为索引来查找值？答案是肯定的——如果您可以将键映射到索引。存储值的数组称为哈希表。将键映射到哈希表中索引的函数称为哈希函数。如下图所示，哈希函数从键获取索引，并使用该索引检索键的值。 散列是一种使用从键获得的索引来检索值而不执行搜索的技术。

如何设计一个从键生成索引的哈希函数？理想情况下，我们希望设计一个函数，将每个搜索键映射到哈希表中的不同索引。这样的函数称为完美哈希函数。然而，很难找到完美的哈希函数。当两个或多个键映射到相同的哈希值时，我们说发生了碰撞。尽管有多种方法可以处理冲突（本章稍后将对此进行讨论），但最好首先避免冲突。因此，您应该设计一个快速且易于计算的哈希函数，以最大限度地减少冲突。

以上是散列的详细内容。更多信息请关注PHP中文网其他相关文章！