java ArrayList。比HashMap更快。收到
我原以为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);
}
}
有趣的是，代码似乎是分阶段预热的。我确定的最后一个阶段是在所有方法大约120000次迭代之后。无论如何，在我的测试机（AMD x2-220，L3+1额外核心解锁，3.6 ghz，2.1 ghz NB）上，真正让我吃惊的数字是最后两个报告。也就是说，到.get()最后一个ArrayList（index == 3999）条目所花费的时间，以及到.get()与3999短键相关的值所花费的时间
在2-3个预热周期后，测试显示ArrayList.get()大约需要56纳秒，而HashMap.get()大约需要68纳秒。那就是。不是我想的那样。我的HashMap都被碰撞吞噬了吗？所有键条目都应该自动装箱到Shorts，Shorts应该报告它们存储的short值以响应.hashcode()，因此所有哈希代码都应该是唯一的。我想是吧
即使没有热身，ArrayList.get()的速度也更快。这与我在其他地方看到的情况相反，比如this question。当然，我也读过，用ListIterator遍历ArrayList比在循环中使用.get()更快，显然，情况并非如此
# 1 楼答案
Hashmaps在检索已知索引的内容时不会更快。如果你按已知顺序存储物品，列表将获胜
但是假设你没有把所有的东西都插入到1-4000列表中，而是按照完全随机的顺序。现在，要从列表中检索正确的项目，您必须逐个检查每个项目以查找正确的项目。但要从hashmap中检索它，只需要知道在插入它时会给它的密钥
所以说真的，你应该比较Hashmap。开始
然后你会看到hashmap的真正效率
# 2 楼答案
对于
HashMap来说，大O是O(1+α)。您的α来自哈希代码冲突，必须遍历一个bucket来检查是否相等通过索引
O(1)从ArrayList中拉出项目的大O当有疑问的时候。。。把它画出来