hashMap.get (“字符串键”)的速度会受到hashMap大小的影响吗？

Question

我想出一个非常大胆的主意。也就是说，我想使用HashMap而不是数据库来存储聊天应用程序的数据。

因此，当用户发送聊天消息时，该特定用户的聊天消息将使用HashMap存储到storeMsg()中。

每个用户将有一个单独的聊天室。每5秒，该特定用户的聊天室将发送一个getMsg()方法来检索该聊天室内的最新消息。在检索消息之后，将删除与该特定用户的聊天室有关的所有消息，这样我们就可以避免开销。

所以，只有用户在那个聊天室里才能看到消息，消息可以一个接一个地追加。最近进入该聊天室的新用户将无法看到之前的消息。这类似于点对点聊天。

每个用户都有一个唯一的字符串用户名，例如"tomhan12“、"Mary2”、“123 has”等等。

public void storeMsg(String userName, String message){
   hMap.put(userName, message);
}

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

因此，我的问题是，如果hMap的Keys是Strings &如果hMap有数百万条条目，那么hMap.get(str)的速度会受到影响吗？

我们能否将String userName转换成一个唯一的整数&然后将"hMap.put(thatUniqueIntegerNumber, message)“转换为更高的性能？或者是HashMap为我们做的，所以我们不需要那么做？

Answer 1

HashMap的get有一个预期的恒定运行时间，这意味着它的运行时间不应该取决于HashMap的大小。当然，这取决于您的密钥的hashCode方法的合理实现，但您的密钥是String，所以应该不会有问题。

也就是说，使用大型HashMap (或任何其他大型数据结构)会消耗大量内存，因此您应该注意，您不会遇到内存不足的问题，这会减慢应用程序的速度。

Answer 2

HashMap get()方法提供了O(1)时间复杂度，如果键hashCode()函数具有良好的分布(对于字符串是正确的)。映射的大小不会影响操作性能(从技术上讲，当映射变得更大时，碰撞会更频繁地发生，但这是另一回事)。

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

Answer 3

根据javadoc：

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

这个实现为基本操作(get和put)提供了恒定的时间性能，假设哈希函数适当地将元素分散在桶中。集合视图的迭代所需的时间与HashMap实例的“容量”(桶的数量)以及其大小(键值映射的数量)成正比。因此，在迭代性能很重要的情况下，不要将初始容量设置得太高(或负载因子太低)是非常重要的。 HashMap的实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子是衡量允许哈希表在其容量自动增加之前得到多满的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，重新哈希表(即重新构建内部数据结构)，使哈希表具有大约两倍的桶数。 通常情况下，默认负载因子(.75)在时间和空间成本之间提供了很好的权衡。较高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put)。在设置其初始容量时，应考虑到映射中的预期条目数及其负载系数，以尽量减少重散列操作的数量。如果初始容量大于最大条目数除以负载因子，则不会发生重散列操作。

由于HashMap将其值存储在散列桶中，因此通常可以在O(1)和O(N)之间查找，这取决于映射哈希的哈希冲突量。

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

为了测试Map的性能，我们将运行一个测试，首先将100/100000项插入到映射中，然后在循环中调用map上的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多个项目。