HashMap具有〜100万个键，仍然是恒定时间？ [英] HashMap with ~100 million keys, still constant time?

问题描述

有人知道这个问题的答案吗？

解决方案

是的。要搜索一个包含1亿个项目的哈希映射，您可以这样做：

<1>计算您要查找的对象的哈希值。

2）找到该桶

3）在该桶中搜索该物品。

（p）（1）独立于哈希映射或其中的项目数。

（2）是O（1），假设标准哈希映射实现为链表的数组。
（3）的时间与桶中物品的数量相关，这应该近似于（散列加入的物品的数量）/（桶的数量）。这部分将从O（1）开始，但随着项目数量开始大大超过桶的数量，缓慢增加。

对于几乎任何目的，Hash只要您使用足够多的桶，就可以将地图视为O（1）插入和检索，即使是非常大的数据集。

Does anyone know the answer to this question?

解决方案

Yes. To search a hash map with 100 million items added to it, you do this:

1) Calculate the hash of the object you're looking for.
2) Find that bucket
3) Search through that bucket for the item.

(1) is independent of the size of the hash map or number of items in it.
(2) is O(1), assuming a standard hashmap implemented as an array of linked lists.
(3) takes an amount of time related to the number of items in the bucket, which should be approximately (number of items added to hash) / (number of buckets). This part will start at O(1), but will very slowly increase as the number of items begins to greatly exceed the number of buckets.

For almost any purpose, Hash Maps can be considered O(1) for both insertion and retrieval, even with very large data sets, as long as you start with a sufficiently large number of buckets.

这篇关于HashMap具有〜100万个键，仍然是恒定时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！