为什么即使哈希函数可能不是O(1)，也要通过键O(1)访问字典的元素? [英] Why is accessing an element of a dictionary by key O(1) even though the hash function may not be O(1)?

问题描述

我了解了如何通过密钥访问您的收藏集.但是，哈希函数本身在幕后有很多操作，不是吗?

I see how you can access your collection by key. However, the hash function itself has a lot of operations behind the scenes, doesn't it?

假设您有一个非常高效的哈希函数，它仍然可能需要进行很多操作.

Assuming you have a nice hash function which is very efficient, it still may take many operations.

这可以解释吗?

推荐答案

HashFunc本身在幕后有很多操作

the HashFunc itself has a lot of operations behind the scenes

当然是这样.但是，这些操作的数量取决于 key 的大小，而不取决于插入密钥的 hash表的大小:要计算的操作数对于具有十个或一万个条目的表中的键，哈希函数是相同的.

That is certainly true. However, the number of these operations depends on the size of the key, not on the size of the hash table into which the key is inserted: the number of operations to compute hash function is the same for a key in a table with ten or with ten thousand entries.

这就是为什么通常将哈希函数的调用视为O(1)的原因.这对于固定大小的键(整数值和固定长度的字符串)可以很好地工作.它还为具有实际上限的可变大小键提供了一个不错的近似值.

That is why the call of hash function is often considered O(1). This works fine for fixed-size keys (integral values and fixed-length strings). It also provides a decent approximation for variable-sized keys with a practical upper limit.

但是，通常，哈希表的访问时间为O(k)，其中k是哈希键大小的上限.

Generally, though, access time of a hash table is O(k), where k is the upper limit on the size of the hash key.

这篇关于为什么即使哈希函数可能不是O(1)，也要通过键O(1)访问字典的元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！