关于集合类查找速度

Question

HashMap，Array，List
这三个速度比较是怎样的？

Answer 1

HashMap最快，但占用存储器多
后两个不是很清楚

Answer 2

多谢楼上两位兄弟，有没有精确的答案啊？
今天笔试就这题
我也知道HashMap最快但是后面就不确定了
感觉好像Array在查找时应该会比List快点吧？

Answer 3

HashMap实际上就是考虑其KEY 即HashSet.
HashSet,Array,List的底层结构都是数组，他们不同是元素的存放
HashSet 采用的是HashCode存放，从而达到使数组中的元素尽可能的散列，这样在某个范围查找的速度大大提高；
当构造一个新的HashSet空集合，其底层默认初始容量是 16，加载因子是 0.75,当超过加载因子的限制时，它会自动将数组的大小增大，由于原HashSet中的元素的下标是根据其容量16来生成的，为了保持其HashCode 的特性，所以不能简单的将原来数组中的元素复制增大的数组中，他必须把原数组中分别元素取出来，然后根据增大后的容量来生成对应的下标。Array 的数组大小固定的，没有在申请空间的开销。即加入元素没Array快，也没ArrayList快
可见Array的开销比HashMap得多，但是速度远远没有通过HashCode来进行查找的HashMap快的。ArrayList 底层就是Array的实现，开销比Array大，即add的速度比Array的速度慢，但是至于他们的查找速度，我个人认为没什么区别；

Answer 4

我曾做过两个 12 万余记录文件的比较，找出不同的，采用 ArrayList 的运行时间为 12 分钟，
而采用 HashSet 的时间为 2 秒钟。由于采用 Hash 算法，将不同的数据分类归放，这样就大大地加快了搜索速度。

Answer 5

打字时，语句错误：
Array 的数组大小固定的，没有在申请空间的开销。即HashMap加入元素没Array快，也没ArrayList快 
可见Array的开销比HashMap少很多，但是速度远远没有通过HashCode来进行查找的HashMap快的。 ArrayList 底层就是Array的实现，但开销比Array大，即add的速度比Array的速度慢，但是至于他们的查找速度，我个人认为没什么区别；

Answer 6

现在可以确定HashMap在这三个中查找速度是最快的了
但是我还是无法确定Array和List的比较

Answer 7

看来是我错了Array比ArrayList快，我用了个比较简单的例子测试了下Array比ArrayList快了很多~import java.util.ArrayList;
import java.util.Calendar;
import java.util.GregorianCalendar;public class TimeTest { public static void main(String[] args) {
int[] a = new int[999999];
ArrayList<Integer> b = new ArrayList<Integer>();
for(int i = 0 ; i < 999999;i++){
a[i] = i;
b.add(i);
}

Calendar c = new GregorianCalendar();
long time1 = c.getTimeInMillis();
for(int i = 0 ; i< 999999 ; i++){
if(a[i] == 999998){
break;
}
}
c = new GregorianCalendar();
long time2 = c.getTimeInMillis();
System.out.println("数组查找到999998，所消耗的时间：" + (time2 - time1));
c = new GregorianCalendar();
time1 = c.getTimeInMillis();
for(Integer num : b){
if(num == 999998){
break;
}
}
c = new GregorianCalendar();
time2 = c.getTimeInMillis();
System.out.println("ArrayList查找到999998，所消耗的时间：" + (time2 - time1));


}}
我运行了几遍 下面是他的输出：
OutPut:
one:
数组查找到999998，所消耗的时间：15毫秒
ArrayList查找到999998，所消耗的时间：63毫秒two:
数组查找到999998，所消耗的时间：0毫秒
ArrayList查找到999998，所消耗的时间：79毫秒three:
数组查找到999998，所消耗的时间：16毫秒
ArrayList查找到999998，所消耗的时间：62毫秒four:
数组查找到999998，所消耗的时间：0毫秒
ArrayList查找到999998，所消耗的时间：78毫秒答案不用我说了吧，哎！什么事情凭空想象不行啊，所以速度上应该是HashMap>ArrAy>ArrayList

Answer 8

其实我感觉虽然HashMap在个方面性能比较好
但是还是看在实际的使用中，根据需要选择最适合的。
各种都有各自的优点吧