我最近几次遇到了这些术语,但我很困惑它们是如何工作的以及通常在什么情况下实现?
我最近几次遇到了这些术语,但我很困惑它们是如何工作的以及通常在什么情况下实现?
那么,这样想。
如果您使用数组,一种简单的基于索引的数据结构,并将其填满随机内容,则随着数据的填充,查找特定条目将变得越来越昂贵,因为您基本上必须从一端开始向另一端搜索,直到找到所需的元素。
如果您想更快地访问数据,则通常会对数组进行排序并使用二进制搜索。然而,这会增加查找现有值的速度,但使插入新值变慢,因为在需要在中间插入元素时需要移动现有元素。
另一方面,哈希表具有一个相关函数,该函数获取条目并将其减少为一个数字,即哈希键。然后将此数字用作数组中的索引,并在此处存储条目。
哈希表围绕一个数组展开,该数组最初为空。空并不意味着长度为零,数组始终具有大小,但数组中的所有元素都不包含任何内容。
每个元素都有两个属性:数据和标识数据的键。例如,美国邮政编码列表将是一种邮政编码->名称类型的关联。该函数减少键,但不考虑数据。
因此,当您将某些东西插入哈希表时,函数会将键减少为数字,该数字用作此(空)数组中的索引,并在此处存储数据,包括键和相关数据。
然后,稍后,您想要查找具有特定键的特定条目,因此将密钥通过相同的函数运行,获取其哈希键,并转到哈希表中的那个特定位置,并检索其中的数据。
理论认为,将您的键缩小为哈希键的函数(即该数字)的计算成本比线性搜索低得多。
一个典型的哈希表并没有无限数量的元素可供存储,因此通常将数字缩小到适合数组大小的索引中。其中一种方法是将索引对数组大小取模。例如,对于大小为10的数组,索引0-9将直接映射到一个索引,而索引10-19将重新映射到0-9,以此类推。lassevk的回答非常好,但可能包含了一些细节。以下是摘要,我有意省略了某些相关信息,您可以99%的时间安全地忽略它们。
在99%的情况下,哈希表和哈希映射之间没有重要区别。
说真的。这是一个神奇的数据结构,几乎保证了三件事情。(有例外情况。您可以基本忽略它们,但有一天学习它们可能对您有用。)
1)哈希表中的所有内容都是一对--有一个键(key)和一个值(value)。通过指定要操作的键,将数据放入哈希表并取出哈希表中的数据。
2)如果您正在使用哈希表上的单个键执行任何操作,则速度非常快速。 这意味着put(key, value)
,get(key)
,contains(key)
和remove(key)
都非常快速。
3)通用哈希表无法执行未列在#2中的任何操作! (通过“失败”,我们的意思是它们非常慢。)
当哈希表的魔法与我们的问题相匹配时,我们使用哈希表。
例如,缓存通常会使用哈希表--例如,假设我们在大学里有45,000名学生,并且某个过程需要保留所有学生的记录。如果您经常使用学生的ID号来引用学生,则ID => student
缓存非常合理。您正在优化此缓存的操作是快速查找。
哈希还可以非常有用地存储数据之间的关系,当您不想彻底更改对象本身时。例如,在课程注册期间,能够将学生与他们参加的课程联系起来可能是一个好主意。但出于某种原因,您可能不希望学生对象本身知道这一点。使用studentToClassRegistration
哈希表并在进行任何必要操作时保留它。
除非您需要执行以下操作,否则它们也是数据结构的相当不错的首选:
遍历元素。哈希表通常不能很好地进行迭代。(通常指通用哈希表,特定的实现有时包含用于减少其迭代负担的链接列表。例如,在Java中,LinkedHashMap
可以让您快速遍历键或值。)
排序。如果无法迭代,则排序也会非常麻烦。
从值到键。使用两个哈希表。相信我,我刚刚为您避免了很多痛苦。