哈希表 - 搜索不存在的键的时间复杂度
hashtable - time complexity for searching a non-existent key
让我们有一个包含 n 个键的散列 table，每个键都有一个只有一个值的桶。
假设我们寻找一个不存在于散列 table 中的键，这个操作的最坏情况时间复杂度是多少？
在我看来，这将是 O(n)。 hashfunction 将必须检查它的所有键，以确定给定的键不存在于哈希中。
你怎么看？我对吗？
这取决于实施。我希望时间复杂度为 O(1)，因为从本质上讲，哈希表不会遍历元素来查找元素，而是根据哈希方法直接在内存中进行索引。它唯一超过 O(1) 的时间是当它需要 re-size 内存或遇到冲突时。当然，除此之外还有很多小细节以及影响事物的哈希算法之间的差异。这是一个很好的话题，可以查看更多信息：
Hash table runtime complexity (insert, search and delete)
让我们有一个包含 n 个键的散列 table，每个键都有一个只有一个值的桶。 假设我们寻找一个不存在于散列 table 中的键，这个操作的最坏情况时间复杂度是多少？
在我看来，这将是 O(n)。 hashfunction 将必须检查它的所有键，以确定给定的键不存在于哈希中。
你怎么看？我对吗？
这取决于实施。我希望时间复杂度为 O(1)，因为从本质上讲，哈希表不会遍历元素来查找元素，而是根据哈希方法直接在内存中进行索引。它唯一超过 O(1) 的时间是当它需要 re-size 内存或遇到冲突时。当然，除此之外还有很多小细节以及影响事物的哈希算法之间的差异。这是一个很好的话题，可以查看更多信息：
Hash table runtime complexity (insert, search and delete)