hash - 哈希在编程中是如何工作的？

Question

哈希在编程中是如何工作的？我对散列的看法是让我能够使用一些独特的值来检索一些数据。就像如果我们有一个数组并且我开始将东西放入数组中，如果我有另一个变量来跟踪插槽 0、1、2 中的项目……那么我就有了找到项目的即时能力。那是哈希吗？

哈希的目的是什么？

什么时候应该实现散列？就数据结构而言，哈希类似于什么？

我认为我对哈希的了解是它允许我们能够在 O(1) 内检索项目。那是正确的吗？

Answer 1

哈希映射/字典是一种键/值数据结构，它根据哈希函数的值将对象存储在桶中。这些键必须是唯一的，但散列函数值(有时称为散列码)不一定是唯一的。

Like if we have an array and I start to put htings in the array, if I have another varible that keeps track of what item is in slot 0,1,2... then I have that instant ability to find an item. Is that hashing?

不可以。散列函数是一种确定性函数，它始终为对象提供相同的值。哈希码不会根据对象的存储位置而改变。

What I think I know about hashes is that it allows us the ability to retrieve the item within O(1). Is that correct?

差不多。如果没有太多哈希码冲突，字典的查找复杂度为 O(1)。但是，如果散列函数很差并且每个对象都具有相同的散列值，那么字典可能具有 O(n) 性能。