哈希表与数组性能比较

36

当数组的索引已知时,使用数组还是HashMap在性能方面更好?请记住,例子中的“对象数组/映射”只是一个示例,在我的实际项目中,它是由另一个类生成的,因此我无法使用单独的变量。

数组示例:

SomeObject[] objects = new SomeObject[2];
objects[0] = new SomeObject("Obj1");
objects[1] = new SomeObject("Obj2");

void doSomethingToObject(String Identifier){
    SomeObject object;
    if(Identifier.equals("Obj1")){
        object=objects[0];
    }else if(){
        object=objects[1];
    }
    //do stuff
}

HashMap示例:

HashMap objects = HashMap();
objects.put("Obj1",new SomeObject());
objects.put("Obj2",new SomeObject());

void doSomethingToObject(String Identifier){
    SomeObject object = (SomeObject) objects.get(Identifier);
    //do stuff
}

HashMap看起来好得多,但我真的需要更高的性能,所以它具有优先权。
编辑:那么就使用数组吧,仍然欢迎建议。
编辑:我忘了提到,数组/ HashMap的大小始终相同(6)。
编辑:似乎HashMap更快 数组:128ms 哈希:103ms
当使用较少的循环时,HashMap甚至可以快两倍。
测试代码:
import java.util.HashMap;
import java.util.Random;

public class Optimizationsest {
private static Random r = new Random();

private static HashMap<String,SomeObject> hm = new HashMap<String,SomeObject>();
private static SomeObject[] o = new SomeObject[6];

private static String[] Indentifiers = {"Obj1","Obj2","Obj3","Obj4","Obj5","Obj6"};

private static int t = 1000000;

public static void main(String[] args){
    CreateHash();
    CreateArray();
    long loopTime = ProcessArray();
    long hashTime = ProcessHash();
    System.out.println("Array: " + loopTime + "ms");
    System.out.println("Hash: " + hashTime + "ms");
}

public static void CreateHash(){
    for(int i=0; i <= 5; i++){
        hm.put("Obj"+(i+1), new SomeObject());
    }
}

public static void CreateArray(){
    for(int i=0; i <= 5; i++){
        o[i]=new SomeObject();
    }
}

public static long ProcessArray(){
    StopWatch sw = new StopWatch();
    sw.start();
    for(int i = 1;i<=t;i++){
        checkArray(Indentifiers[r.nextInt(6)]);
    }
    sw.stop();
    return sw.getElapsedTime();
}



private static void checkArray(String Identifier) {
    SomeObject object;
    if(Identifier.equals("Obj1")){
        object=o[0];
    }else if(Identifier.equals("Obj2")){
        object=o[1];
    }else if(Identifier.equals("Obj3")){
        object=o[2];
    }else if(Identifier.equals("Obj4")){
        object=o[3];
    }else if(Identifier.equals("Obj5")){
        object=o[4];
    }else if(Identifier.equals("Obj6")){
        object=o[5];
    }else{
        object = new SomeObject();
    }
    object.kill();
}

public static long ProcessHash(){
    StopWatch sw = new StopWatch();
    sw.start();
    for(int i = 1;i<=t;i++){
        checkHash(Indentifiers[r.nextInt(6)]);
    }
    sw.stop();
    return sw.getElapsedTime();
}

private static void checkHash(String Identifier) {
    SomeObject object = (SomeObject) hm.get(Identifier);
    object.kill();
}

}


7
等一下,如果你“真的需要性能”,那么你应该已经知道这个问题的答案了,因为你应该已经对你的应用程序进行了分析,以确定HashMap与Array之间的问题实际上是相关的。如果你还没有这样做,你需要这样做来确定这是否确实影响了你的性能,而不是浪费时间。 - Dour High Arch
3
好的,作为一名初学者程序员,如果你漏掉了什么或需要更好的策略建议,得到反馈总是很好的。 - Timotheus
4
如果你“真的需要高性能”,那么你不应该使用Java语言编写代码... - user780363
3
Dasdasd,你必须使用真实数据对你的应用程序进行基准测试。使用两个样本点编造虚假的“基准测试”只会误导你。你必须对整个应用程序进行基准测试并优化瓶颈,而不是选择看起来有趣的代码行进行更改。如果这个问题不是瓶颈,那么优化它也不会提高性能,无论你多快。 - Dour High Arch
2
你的基准测试有缺陷。你需要在每个测试中单独使用JVM调用。现在,如果你反转ProcessArray和ProcessHash,你会看到不同的值。 - Steve Kuo
显示剩余6条评论
7个回答

44

HashMap使用底层数组实现,因此它的速度永远无法比正确使用数组更快。

Random.nextInt()比您测试的内容慢得多,即使使用数组测试数组也会导致结果偏差。

您的数组基准测试之所以如此缓慢,是由于等式比较而不是数组访问本身。

HashTable通常比HashMap慢得多,因为它做的事情差不多,但同时还进行了同步。

微型基准测试的一个常见问题是JIT非常擅长删除不执行任何操作的代码。如果不小心的话,您将只测试您是否已经混淆了JIT,以至于它无法解决您的代码没有任何作用。

这是撰写优于C++系统的微型基准测试的原因之一。这是因为Java是一种更简单的语言,更容易推理出哪些代码没有用处。这可能会导致测试显示Java比C++更快地“不执行任何有用的工作”;)


4
好的,Java 基本上很聪明,如果不需要做任何事情,它就什么也不做。 - Rick
@PeterLawrey 有没有办法知道哪些代码被“JIT”了?我通常使用caliper框架进行基准测试,但他们建议同样要“小心”。 - Eugene
@Eugene 我判断代码的方式是现在它已经变得非常快了,例如每次迭代所需的时钟周期明显减少。这在重复测试中表现得最好。 - Peter Lawrey

5

当索引已知时,数组更快(HashMap在幕后使用链接列表的数组,这增加了一些开销,除了需要执行哈希操作)

顺便提一下,HashMap<String,SomeObject> objects = HashMap<String,SomeObject>();使您无需强制转换


2
“数组更快”最多只是一种过度简化,最糟糕的情况下则完全错误。数组和哈希表是两个不同的概念。在给定其数组索引的情况下查找数组中的值以及在给定其键的情况下查找哈希表中的项都是渐进等价的:O(1)(在哈希表的情况下,这是摊销的O(1))。但是,通过循环遍历数组来查找给定的键要糟糕得多:平均为O(n/2),在渐进意义下为O(n)。确实,在这种情况下,数组实现可能会获胜,但您的答案暗示这是一个普遍规律。 - Daniel Pryden
@daniel 好的,“当数组的索引已知”指向数组是赢家,但我会在答案中明确编辑警告。 - ratchet freak

2

在这个示例中,我认为哈希表胜出。数组方法的问题在于它不可扩展。我想你想要在表中有更多的条目,并且doSomethingToObject中的条件分支树很快会变得难以管理和缓慢。


2
只是挑剔一下 - 对于所示的示例,数组可能更胜一筹。但对于另一个例子,在其中有更多要检查的“标识符”值时,你所说的就成立了。 - jwd
数组的长度也是已知的(如果有关系,则为6) - Timotheus

2

从逻辑上讲,HashMap绝对适合您的情况。从性能角度来看,它也胜过数组,因为在数组中,您需要进行许多字符串比较(在算法中),而在HashMap中,如果负载因子不太高,只需使用哈希码即可。当添加许多元素时,数组和HashMap都需要调整大小,但是在HashMap中,您还需要重新分配元素。在这种情况下,HashMap输了。


有了这个想法,我想我会运行一些测试来看哪种方法是最好的。感谢您提供的信息。 - Timotheus
1
请在您获得结果后添加。对于数据集大小为6,调整大小显然并不重要。 - Alex Gitelman

0
我想知道为什么没有人谈论HashMap的性能。不要忘记一个哈希函数在每次将数据放入HashMap和从HashMap获取数据时都会被调用。每个函数调用都会使用堆栈。而且,哈希函数本身并不是一个简单的原始操作。越聪明的哈希函数,实现的代码就越复杂。同时,在幕后使用树结构需要时间和代码来粘贴数据和重新排列节点。请注意,没有人回答过这个问题:何时使用哈希表比使用简单数组更高效。

1
根据目前的写法,你的回答不够清晰。请编辑以添加更多细节,帮助他人理解这如何回答所提出的问题。你可以在帮助中心找到更多关于如何撰写好回答的信息。 - undefined
我的回答与主题“哈希映射与数组性能”直接相关。不明白你有什么不清楚的。你可以练习提出聪明的问题或者写一些有意义的帖子。只需要阅读帮助中心。 - undefined

0

数组通常比集合类更快。

附:您在帖子中提到了HashTable。HashTable的性能甚至比HashMap还要差。我猜您提到HashTable是一个打字错误。

“HashTable看起来好得多。”


0

这个例子很奇怪。关键问题在于你的数据是否是动态的。如果是,你不能像数组那样编写程序。换句话说,比较你的数组和哈希实现是不公平的。哈希实现适用于动态数据,但数组实现则不行。

如果你只有静态数据(6个固定对象),数组或哈希都可以作为数据容器。你甚至可以定义静态对象。


正如所述,数据是在另一个类中创建的,因此数组/哈希映射确实充当数据持有者。 - Timotheus

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接