我没有在动态语言中使用哈希表以外的经验,所以最近才发现它们是通过对键进行哈希然后使用哈希值存储值来实现的。 我不理解的是,为什么不将键(字符串、数字或其他)作为关键字直接与值一起存储,而要对其进行哈希并存储它。
我没有在动态语言中使用哈希表以外的经验,所以最近才发现它们是通过对键进行哈希然后使用哈希值存储值来实现的。 我不理解的是,为什么不将键(字符串、数字或其他)作为关键字直接与值一起存储,而要对其进行哈希并存储它。
这是一个近似重复的问题:为什么在哈希表中使用哈希码而不是索引?
简而言之,你可以非常快速地检查一个键是否已经被存储,并且同样快速地存储一个新的映射关系。否则,您将不得不保持一个已排序的键列表,这将使从中存储和检索映射关系变得更加缓慢。
什么是哈希表?
它也被称为哈希映射,是一种用于实现关联数组的数据结构。它是一个可以将键映射到值的结构。
它如何工作?
哈希表使用哈希函数计算出一个索引,该索引指向一个包含正确值的桶或插槽数组。
下面的图表清楚地解释了这个过程。
优点:
在维度合适的哈希表中,每次查找的平均成本与表中存储的元素数无关。
许多哈希表设计也允许任意插入和删除键值对。
在许多情况下,哈希表被发现比搜索树或任何其他表查找结构更有效。
缺点:
当条目数非常少时,哈希表不太有效。(然而,在某些情况下,通过将哈希值与键一起保存,可以减轻计算哈希函数的高成本。)
用途:
它们广泛用于各种计算机软件中,特别是关联数组、数据库索引、缓存和集合。
哈希表用于在(一定时间内)恒定数量的位置中存储一组值及其键。在简单情况下,假设您想使用哈希函数 i%10 保存从0到10000的每个整数。
这将创建一个哈希表,其中包含1000个块(通常是数组),每个块深度为10个元素。因此,如果您要搜索1234,则会立即知道要在123的表条目中搜索,然后开始比较以找到精确匹配项。当然,这并不比仅使用10000个元素的数组好多少,但这只是为了演示。
当您不知道将有多少元素时,哈希表非常有用,但哈希函数的碰撞次数要比总元素数少得多。(这使得哈希函数“哈希(x)= 0”非常糟糕。)您的表中可能有空位,但理想情况下,大部分都将有一些数据。