logo标签列表

哈希表中get("字符串键")的速度是否会受到哈希表大小的影响？

javahashmap
3
我有一个非常大胆的想法，就是我想使用 HashMap 来代替数据库存储聊天应用程序的数据。
因此，当用户发送聊天消息时，该特定用户的聊天消息将使用 storeMsg() 存储到 HashMap 中。
每个用户都有一个单独的聊天室。每 5 秒钟，该特定用户的聊天室将发送 getMsg() 方法来检索该聊天室内的最新消息。检索到消息后，它将移除与该特定用户的聊天室相关的所有消息，以避免负担过重。
因此，只有存在于该聊天室中的用户可以看到消息，消息可以逐一追加。最近进入该聊天室的新用户将无法看到以前的消息。这类似于点对点聊天。
每个用户都有一个唯一的字符串用户名，例如 "tomhan12"、"Mary2"、"123cat" 等。
public void storeMsg(String userName, String message){
   hMap.put(userName, message);
}

public String getMsg(String userName){
    return hMap.get(userName);
}

所以，我的问题是，如果hMap具有字符串键并且hMap具有数百万个条目，那么hMap.get（str）的速度会受到影响吗？
我们可以将String userName转换为唯一的整数，然后“hMap.put（thatUniqueIntegerNumber，message）”以提高性能吗？还是HashMap已经为我们完成了这项工作，因此我们不需要这样做？
我们能否将字符串userName转换为唯一的整数，然后使用"hMap.put(thatUniqueIntegerNumber, message)"来提高性能？或者HashMap已经为我们完成了这个操作，因此我们不需要自己做呢？这是HashMap存储键值对的工作原理的一部分。 - user1717259
FYI：5秒可能是一个非常高的时间跨度来获取消息，因为一些用户在发送消息之前只写了几个字符，比如“hi”和“whatsup”。 - Leonid Glanz
4个回答
8
HashMap的get方法拥有预期的恒定运行时间，也就是说其运行时间不应该依赖于HashMap的大小。当然，这基于一个良好实现的hashCode方法，但由于你的key是String类型，所以不应该成为问题。
话虽如此，使用大型HashMap（或任何其他大型数据结构）会消耗大量内存，因此你需要注意是否会遇到内存不足的问题，这会减慢你的应用程序速度。
我们插入消息，然后几秒钟后删除该消息，这样我们就可以最小化内存问题。 - Tum
@Tum 你提到有百万条目。如果这些条目足够大，它们将需要大量的内存。 - Eran
3

HashMap的get()方法在键hashCode()函数有良好分布（对于字符串而言是真的）的情况下，提供O(1)时间复杂度。映射的大小不会影响操作性能（当映射变得更大时，碰撞更频繁，但这是另一个故事）。

用Integer键替换String键不会给您带来任何显著的性能提升。

是的，“保证”这个词不太准确。引用文档中的话：“假设哈希函数将元素适当地分散在桶中，此实现为基本操作（获取和放置）提供恒定时间性能。” - Bart Kiers
这个人只是在存储字符串，你为什么要用极端情况来困扰他呢？ - AdamSkywalker
1
那么你应该写成“在字符串的情况下……”。存储除内置Java类之外的键（其中您提供自己的hashCode()和equals(...)）并不是一个极端情况。 - Bart Kiers
2
我们不是在打扰他，而是在打扰你，因为你使用“保证”这个词时很容易展示出一个不成立的情况。 - Kayaman
如果您使用int作为键，而不是String，那么性能上会有巨大的显著变化。 - NaviRamyle
1
根据Javadoc文档：

https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html


该实现提供了基本操作（获取和放置）的常数时间性能，假设哈希函数在桶之间适当地分散元素。对集合视图的迭代需要与HashMap实例的“容量”（桶的数量）加上其大小（键值映射的数量）成比例的时间。因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载因子太低）非常重要。
HashMap实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，而初始容量只是创建哈希表时的容量。负载因子是哈希表允许达到的填充程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新哈希（即内部数据结构将被重建），以便哈希表具有大约两倍的桶数。
一般来说，默认的负载因子（.75）在时间和空间成本之间提供了良好的平衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置其初始容量时，应考虑映射中预期的条目数和其负载因子，以便最小化重新哈希操作的数量。如果初始容量大于最大条目数除以负载因子，则永远不会发生重新哈希操作。

由于HashMap将其值存储在哈希桶中，因此查找的时间复杂度通常在O(1)和O(N)之间，具体取决于映射中哈希冲突的数量。

让我们测试一下这个性能：

为了测试Map的性能，我们将运行一个测试，首先向Map中插入100/100000个项目，然后我们在循环中调用get("0-9")以测试查找的性能。我们使用以下代码来完成此操作：

import java.util.HashMap;
public class HashMapTest {
    public static void test(int items, boolean print) {
        System.gc();
        System.gc();
        HashMap<String,Object> map = new HashMap<>();
        for(int i = 0; i < items; i++) {
            map.put("" + i, map);
        }
        long start = System.nanoTime();
        for(int i = 0; i < 100000; i++) {
            map.get("0");
            map.get("1");
            map.get("2");
            map.get("3");
            map.get("4");
            map.get("5");
            map.get("6");
            map.get("7");
            map.get("8");
            map.get("9");
        }
        long end = System.nanoTime();
        long time = end - start;
        if(print) {
            System.out.println("items: "+ items + " time: "+ time);
        }
    }
    
    public static void main(String ... args) {
        // warmup
        for(int i = 0; i < 2; i++) {
            test(100, false);
        }
        for(int i = 0; i < 2; i++) {
            test(1000000, false);
        }
        // Real test:
        for(int i = 0; i < 10; i++) {
            test(100, true);
        }
        for(int i = 0; i < 10; i++) {
            test(1000000, true);
        }
    }
}

测试结果
items: 100     time: 11102830
items: 100     time: 12228567
items: 100     time: 34309933
items: 100     time: 36976824
items: 100     time: 34290557
items: 100     time: 19819022
items: 100     time: 14747533
items: 100     time: 15818922
items: 100     time: 15026368
items: 100     time: 16830762
items: 1000000 time: 12421862
items: 1000000 time: 13931351
items: 1000000 time: 13083504
items: 1000000 time: 11453028
items: 1000000 time: 13265455
items: 1000000 time: 11030050
items: 1000000 time: 11362288
items: 1000000 time: 11521082
items: 1000000 time: 11198296
items: 1000000 time: 11303685

items 100     min: 11102830
items 100     max: 36976824
items 1000000 min: 11030050
items 1000000 max: 13931351

如果我们分析测试结果，我们会发现当项数增加1000倍时，访问时间并没有真正的改善。
0
理论上，如果哈希表没有过度填充且项目在桶之间分布良好，则 HashMap#get(...) 的时间复杂度保证为 O(1)。实际上，这取决于具体的实现方式，但通常情况下，如果哈希表过度填充，它会变慢一些。一般来说，HashMap 的负载因子应该低于 0.7，以避免过度填充并保持性能最优。尽管如此，它的减速将是很小的（除了一些极端情况）。
1
你如何在一个段落中写出“保证”和“除了一些极端情况”的意思... - Betlista
访问时间为O(1)。这意味着访问与地图的大小无关，是恒定时间的。但有些条目会发生冲突，如果hash(A) mod p = hash(B) mod p。这些冲突总是导致应用某种冲突策略，需要额外的处理。尽管如此，它仍然是O(1)。只是运行时复杂性的常见陷阱：它并不说明算法在特定情况下的行为方式。 - user4668606
抱歉，但这只是您对大O符号的错误理解，它描述了最坏情况和碰撞数量可能不是关于映射大小的常数... - Betlista
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接