我曾认为 HashMap 随机访问单个值比 ArrayList 更快。 。 。也就是说，HashMap.get(key) 应该比 ArrayList.get(index) 更快，因为 ArrayList 必须遍历集合中的每个元素以获取其值，而 HashMap 则不然。你知道，O(1) 与 O(n) 等等。
编辑:所以我对 HashMap 的理解是/不充分的，因此我很困惑。这段代码的结果符合预期。感谢您的多次解释。
所以我决定测试一下，只是为了好玩。这是我的代码:
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 快捷键关联的值。
经过 2-3 个预热周期后，测试表明 ArrayList.get() 大约需要 56 ns，而 HashMap.get() 大约需要 68 ns。那是 。 。 。不是我所期望的。我的 HashMap 是否因碰撞而被耗尽？所有键条目都应该自动装箱到 Shorts，Shorts 应该报告其存储的短值以响应 .hashcode()，因此所有哈希码都应该是唯一的。我认为？
即使没有预热，ArrayList.get() 仍然更快。这与我在其他地方看到的一切相反，例如 this question 。当然，我还了解到使用 ListIterator 遍历 ArrayList 比在循环中使用 .get() 更快，并且显然，情况也并非如此。 。 .
最佳答案
HashMap 在检索已知索引处的某些内容时并不更快。如果您按照已知的顺序存储内容，则列表将获胜。
但是，假设您不是将所有内容插入列表 1-4000 的示例，而是完全随机顺序执行的。现在，要从列表中检索正确的项目，您必须逐项检查每个项目以查找正确的项目。但是要从 HashMap 中检索它，您需要知道的只是插入它时提供的 key 。
所以说真的，你应该将 Hashmap.get(i) 与
for(Integer i : integerList)
if(i==value)
//found it!
然后你就会看到 hashmap 的真实效率。
关于java - ArrayList .get 比 HashMap .get 快吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26809537/