问题描述
我以为HashMap s可以比ArrayList s更快地访问各个值. . .也就是说，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.
编辑:所以我对HashMap的理解不充分，因此感到困惑.此代码的结果与预期的一样.感谢您的许多解释.
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关联的值所花费的时间.
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都被冲突吞噬了吗?所有键项都应该自动装到短裤"中，以便响应.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更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！