我正在学习哈希表、 HashMap 等。我刚刚用 C 语言实现了一个哈希表,操作如下:insert(HTable, key)
, delete(HTable, key)
、initialize(HTable)
和search(HTable, key)
。
我想请教一下。由于在(适当的)哈希表中计算的哈希索引可能非常大,这是否意味着消耗的空间将像 INT_MAX
(当然仍然是 O(n)),或者更多的?我的意思是给定我们要存储在哈希表中的输入元素(即将其插入),insert() 函数将调用哈希函数,该函数然后计算元素的哈希索引以进入。因此它将使用找到这个索引的哈希函数。
当我们使用散列函数对元素进行操作时,散列索引可能会变得非常大。使用适当的加密散列函数,这个索引可能会变得很大(他们使用 300 位的质数 - Diffie Hellman 公钥加密等),对吧?我知道在普通哈希函数(例如初学者用来学习的琐碎函数)中,我们应用模运算以使元素适合哈希表的边界,但这样做可能会限制哈希函数的潜力?
因此,要将一个元素唯一地映射到哈希表,我们必须使用一个巨大的哈希表。这些加密哈希表是如何实现的?它们一定是完全安全的,对吧?甚至“cryptographichashfunction”上的 Stack Overflow 标签也表示,极不可能找到将映射到同一元素的两个输入(因此发生冲突的可能性很小)。这是否需要将一个巨大的数组存储在内存中(或磁盘)?因此,内存消耗将是巨大的。
当然,时间复杂度不是问题。我们只是看到哈希表/数组的起始地址加上索引,然后在内存中的那个地方去获取值(O(1) - 哈希表的搜索原则)。
我哪里错了吗?有什么我想念的吗?我希望我说清楚了。所以总而言之,我想确认这一点。一个好的散列函数是否需要一个巨大的数组(散列表)以及如此大量的内存才能正确实现?这么多空间是否合理,还是有什么我不太明白的地方?谢谢。
最佳答案
一般来说,加密哈希值不用于哈希表。取而代之的是使用快速散列。该散列值中只有尽可能多的位可用于调整表的大小。如果多个键值映射到同一个索引,那么这些值将存储在一个单独的结构中,可能带有额外信息以在两者之间进行选择。
不要求哈希输出是唯一的;散列函数的输出会太大,而且所需的表肯定不适合内存。除此之外,加密哈希通常非常慢。
加密哈希函数通常是从对称分组密码中也使用的操作构建的。这意味着在大量回合中使用混合和按位运算符。模块化算法,例如用于RSA 通常不使用。
总而言之,最主要的是生成的索引不需要是唯一的。通常,如果一个散列导致多个值,它们将存储在列表中或设置为可以按值比较键的位置。
关于哈希表困惑 - 具有良好(例如密码)哈希函数的哈希表需要多少空间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44530507/