ArrayList .get 比 HashMap .get 快吗? [英] ArrayList .get faster than HashMap .get?
问题描述
我曾认为 HashMaps 在随机访问单个值方面比 ArrayLists 更快...也就是说，HashMap.get(key) 应该比 ArrayList.get(index) 快，因为 ArrayList 必须遍历集合的每个元素以达到其值，而 HashMap 则不然.你知道，O(1) vs O(n) 等等.
I had thought that HashMaps were faster for random access of individual values than ArrayLists . . . that is, to say, that HashMap.get(key) should be faster than ArrayList.get(index) simply because the ArrayList has to traverse every element of the collection to reach its value, whereas the HashMap does not. You know, O(1) vs O(n) and all that.
所以我对 HashMaps 的理解不够充分，因此我很困惑.此代码的结果符合预期.感谢您的众多解释.
edit: So my understanding of HashMaps was/is inadequate, hence my confusion. The results from this code are as expected. Thanks for the many explanations.
所以我决定在百灵鸟上测试一下.这是我的代码:
So I decided to test it, on a lark. Here is my code:
import java.util.HashMap;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Testing
{
public static void main(String[] args)
{
ArrayList<SomeClass> alist = new ArrayList<>();
HashMap<Short, SomeClass> hmap = new HashMap<>(4000, (float).75);
ListIterator<SomeClass> alistiterator = alist.listIterator();
short j = 0;
do
{
alistiterator.add(new SomeClass());
j++;
}
while(j < 4000);
for (short i = 0; i < 4000; i++)
{
hmap.put(i, new SomeClass());
}
boolean done = false;
Scanner input = new Scanner(System.in);
String blargh = null;
do
{
System.out.println("\nEnter 1 to run iteration tests.");
System.out.println("Enter w to run warmup (recommended)");
System.out.println("Enter x to terminate program.");
try
{
blargh = input.nextLine();
}
catch (NoSuchElementException e)
{
System.out.println("Uh, what? Try again./n");
continue;
}
switch (blargh)
{
case "1":
long starttime = 0;
long total = 0;
for (short i = 0; i < 1000; i++)
{
starttime = System.nanoTime();
iteratearraylist(alist);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: iterating sequentially"
+ " through ArrayList");
total = 0;
for (short i = 0; i< 1000; i++)
{
starttime = System.nanoTime();
iteratearraylistbyget(alist);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: iterating sequentially"
+ " through ArrayList via .get()");
total = 0;
for (short i = 0; i< 1000; i++)
{
starttime = System.nanoTime();
iteratehashmap(hmap);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: iterating sequentially"
+ " through HashMap via .next()");
total = 0;
for (short i = 0; i< 1000; i++)
{
starttime = System.nanoTime();
iteratehashmapbykey(hmap);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: iterating sequentially"
+ " through HashMap via .get()");
total = 0;
for (short i = 0; i< 1000; i++)
{
starttime = System.nanoTime();
getvaluebyindex(alist);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: getting end value"
+ " from ArrayList");
total = 0;
for (short i = 0; i< 1000; i++)
{
starttime = System.nanoTime();
getvaluebykey(hmap);
total += System.nanoTime() - starttime;
}
total = (long)(total * .001);
System.out.println(total + " ns: getting end value"
+ " from HashMap");
break;
case "w":
for (int i = 0; i < 60000; i++)
{
iteratearraylist(alist);
iteratearraylistbyget(alist);
iteratehashmap(hmap);
iteratehashmapbykey(hmap);
getvaluebyindex(alist);
getvaluebykey(hmap);
}
break;
case "x":
done = true;
break;
default:
System.out.println("Invalid entry. Please try again.");
break;
}
}
while (!done);
input.close();
}
public static void iteratearraylist(ArrayList<SomeClass> alist)
{
ListIterator<SomeClass> tempiterator = alist.listIterator();
do
{
tempiterator.next();
}
while (tempiterator.hasNext());
}
public static void iteratearraylistbyget(ArrayList<SomeClass> alist)
{
short i = 0;
do
{
alist.get(i);
i++;
}
while (i < 4000);
}
public static void iteratehashmap(HashMap<Short, SomeClass> hmap)
{
Iterator<HashMap.Entry<Short, SomeClass>> hmapiterator =
map.entrySet().iterator();
do
{
hmapiterator.next();
}
while (hmapiterator.hasNext());
}
public static void iteratehashmapbykey(HashMap<Short, SomeClass> hmap)
{
short i = 0;
do
{
hmap.get(i);
i++;
}
while (i < 4000);
}
public static void getvaluebykey(HashMap<Short, SomeClass> hmap)
{
hmap.get(3999);
}
public static void getvaluebyindex(ArrayList<SomeClass> alist)
{
alist.get(3999);
}
}
和
public class SomeClass
{
int a = 0;
float b = 0;
short c = 0;
public SomeClass()
{
a = (int)(Math.random() * 100000) + 1;
b = (float)(Math.random() * 100000) + 1.0f;
c = (short)((Math.random() * 32000) + 1);
}
}
有趣的是，代码似乎是分阶段预热的.我确定的最后阶段是在所有方法的大约 120,000 次迭代之后.无论如何，在我的测试机器上(AMD x2-220，L3 + 1 个额外核心未锁定，3.6 GHz，2.1 GHz NB)，真正让我吃惊的数字是最后两个报告的数字.即，.get()ArrayList(index == 3999)最后一个条目的时间和的时间>.get() 与 3999 的 Short 键关联的值.
Interestingly enough, the code seems to warm up in stages. The final stage that I've identified comes after around 120,000 iterations of all methods. Anyway, on my test machine (AMD x2-220, L3 + 1 extra core unlocked, 3.6 ghz, 2.1 ghz NB), the numbers that really jumped out at me were the last two reported. Namely, the time taken to .get() the last entry of the ArrayList (index == 3999) and the time taken to .get() the value associated with a Short key of 3999.
经过 2-3 个预热周期后，测试表明 ArrayList.get() 需要大约 56 ns，而 HashMap.get() 需要大约 68 ns.那是 ...不是我所期望的.我的 HashMap 都被冲突吃掉了吗?所有的关键条目都应该自动装箱到 Shorts，它们应该报告它们存储的短值以响应 .hashcode()，所以所有的哈希码都应该是唯一的.我觉得?
After 2-3 warmup cycles, testing shows that ArrayList.get() takes around 56 ns, while HashMap.get() takes around 68 ns. That is . . . not what I expected. Is my HashMap all eaten up with collisions? All the key entries are supposed to autobox to Shorts which are supposed to report their stored short value in response to .hashcode(), so all the hashcodes should be unique. I think?
即使没有预热，ArrayList.get() 仍然更快.这与我在其他地方看到的所有内容相反，例如 这个问题.当然，我也读过使用 ListIterator 遍历 ArrayList 比仅在循环中使用 .get() 更快，并且显然，事实也并非如此...
Even without warmups, the ArrayList.get() is still faster. That is contrary to everything I've seen elsewhere, such as this question. Of course, I've also read that traversing an ArrayList with a ListIterator is faster than just using .get() in a loop, and obviously, that is also not the case . . .
推荐答案
哈希图在检索已知索引处的内容时并不快.如果您以已知顺序存储东西，则列表将获胜.
Hashmaps aren't faster at retrieval of something at a known index. If you are storing things in a known order, the list will win.
但是，不是将所有内容插入列表 1-4000 的示例，而是以完全随机的顺序进行的.现在要从列表中检索正确的项目，您必须一项一项地检查每个项目以寻找正确的项目.但是要从哈希图中检索它，您只需要知道插入它时会提供的密钥.
But say instead of your example of inserting everything into the list 1-4000, you did it in a total random order. Now to retrieve the correct item from a list, you have to check each item one by one looking for the right item. But to retrieve it from the hashmap, all you need to know is the key you would have given it when you inserted it.
真的，你应该比较 Hashmap.get(i) 和
So really, you should be comparing Hashmap.get(i) to
for(Integer i : integerList)
if(i==value)
//found it!
然后你就会看到哈希图的真正效率.
Then you would see the real efficiency of the hashmap.
这篇关于ArrayList .get 比 HashMap .get 快吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
