选择不同的Map 实施方案时,注意Map 的大小对于性能的影响是最大的,下面这个测试程序清楚地阐示了这
一点:
//: MapPerformance.java
// Demonstrates performance differences in Maps
package c08.newcollections;
import java.util.*;
public class MapPerformance {
private static final int REPS = 200;
public static Map fill(Map m, int size) {
for(int i = 0; i < size; i++) {
String x = Integer.toString(i);
m.put(x, x);
}
return m;
}
private abstract static class Tester {
String name;
Tester(String name) { this.name = name; }
abstract void test(Map m, int size);
}
private static Tester[] tests = {
new Tester("put") {
void test(Map m, int size) {
for(int i = 0; i < REPS; i++) {
m.clear();
fill(m, size);
}
}
},
new Tester("get") {
void test(Map m, int size) {
for(int i = 0; i < REPS; i++)
for(int j = 0; j < size; j++)
m.get(Integer.toString(j));
}
},
new Tester("iteration") {
void test(Map m, int size) {
for(int i = 0; i < REPS * 10; i++) {
Iterator it = m.entries().iterator();
while(it.hasNext())
it.next();
}
}
},
};
public static void test(Map m, int size) {
// A trick to print out the class name:
System.out.println("Testing " +
m.getClass().getName() + " size " + size);
252
fill(m, size);
for(int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(m, size);
long t2 = System.currentTimeMillis();
System.out.println(": " +
((double)(t2 - t1)/(double)size));
}
}
public static void main(String[] args) {
// Small:
test(new Hashtable(), 10);
test(new HashMap(), 10);
test(new TreeMap(), 10);
// Medium:
test(new Hashtable(), 100);
test(new HashMap(), 100);
test(new TreeMap(), 100);
// Large:
test(new HashMap(), 1000);
test(new Hashtable(), 1000);
test(new TreeMap(), 1000);
}
} ///:~
由于Map 的大小是最严重的问题,所以程序的计时测试按Map 的大小(或容量)来分割时间,以便得到令人
信服的测试结果。下面列出一系列结果(在你的机器上可能不同):
类型 测试大小 置入 取出 反复
T y p e T e s t
s i z e
P u t G e t Iteration
10 11.0 5.0 44.0
Hashtable 100 7.7 7.7 16.5
1000 8.0 8.0 14.4
10 16.0 11.0 22.0
T r e e M a p 100 25.8 15.4 13.2
1000 33.8 20.9 13.6
10 11.0 6.0 33.0
H a s h M a p 100 8.2 7.7 13.7
1000 8.0 7.8 11.9
即使大小为10,ArrayMap 的性能也要比HashMap 差——除反复循环时以外。而在使用Map 时,反复的作用通
常并不重要(get()通常是我们时间花得最多的地方)。TreeMap 提供了出色的put()以及反复时间,但get()
的性能并不佳。但是,我们为什么仍然需要使用TreeMap 呢?这样一来,我们可以不把它作为Map 使用,而
作为创建顺序列表的一种途径。树的本质在于它总是顺序排列的,不必特别进行排序(它的排序方式马上就
要讲到)。一旦填充了一个TreeMap,就可以调用keySet()来获得键的一个Set“景象”。然后用toArray()
253
产生包含了那些键的一个数组。随后,可用static 方法Array.binarySearch()快速查找排好序的数组中的
内容。当然,也许只有在HashMap 的行为不可接受的时候,才需要采用这种做法。因为HashMap 的设计宗旨
就是进行快速的检索操作。最后,当我们使用Map 时,首要的选择应该是HashMap。只有在极少数情况下才
需要考虑其他方法。
此外,在上面那张表里,有另一个性能问题没有反映出来。下述程序用于测试不同类型Map 的创建速度:
//: MapCreation.java
// Demonstrates time differences in Map creation
package c08.newcollections;
import java.util.*;
public class MapCreation {
public static void main(String[] args) {
final long REPS = 100000;
long t1 = System.currentTimeMillis();
System.out.print("Hashtable");
for(long i = 0; i < REPS; i++)
new Hashtable();
long t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("TreeMap");
for(long i = 0; i < REPS; i++)
new TreeMap();
t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("HashMap");
for(long i = 0; i < REPS;
分享到:
相关推荐
List、ArrayList、Vector及map、HashTable、HashMap分别的区别
用数据结构的思想实现java中的类hashmap
Java中List、ArrayList、Vector及map、HashTable、HashMap分别的区别.
这与 Firefox 使用的算法相同——它是一种不基于任何广为人知的算法的自制算法——尽管经过修改以生成 64 位散列值而不是 32 位散列值。它始终优于 rustc 本身中基于 FNV 的哈希——冲突率与 FNV 相似或略差,但哈希...
Map,HashMap,TreeMap的使用 很详细额,值得看看
《java编程思想》,Map结合HashMap获取键相关联的值
比较Java原生的 3种Map的效率。 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 本测试查找方法使用Map的get方法,循环、离散获取。对于ConcurrentSkipListMap,获得顺序片段,可用subMap()方法,提取50w的子序列...
JNI处理hashmap,string等对象的操作,别处绝对没有的
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
A HashMap for Geeks and normal programmers.
可以通过2种方法遍历HashMap <br>Map map = new HashMap(); <br>for (Iterator iter = map.entrySet().iterator(); iter.hasNext();) { <br> Map.Entry entry = (Map.Entry) iter.next(); <br> Object ...
C++hashmap的使用实例
1、此HashMap类采用java jdk中HashMap的实现方式 2、相比网站上发布过的hashtable之类的源码: 此HashMap寻址方法是拉链法.比开放寻址法对连续内存要求更低 哈希函数用的是java中String.hashCode()算法(经实际验证其...
易语言HashMap类源码,HashMap类,初始设置,加入,取值,删除,清空,取所有键,取所有值,枚举所有键,键总数,是否为空,是否存在键,取所有键值对,计算散列值,更新阈值,计算索引,重新索引
HashMap介绍和使用
Java——HashMap HashMap 底层: 哈希表存储(数组+链表+红黑树) 特点: 查询,增删效率高,但是无序,存储键值对的值 去重: 根据key做去重,根据key计算桶的位置 扩容: 初始容量: 默认初始用量为16 加载因子: 0.75 当16*...
Map a = new HashMap(); //方法一 Iterator it = a.entrySet().iterator(); while (it.hasNext()) { Map.Entry pairs = (Map.Entry) it.next(); System.out.println(pairs.getValue()); } //以下方法需要jdk5以上...
1、此HashMap类采用java jdk中HashMap的实现方式。2、相比网站上发布过的hashtable之类的源码:。此HashMap寻址方法是拉链法.比开放寻址法对连续内存要求更低。哈希函数用的是java中String.hashCode()算法(经实际验证...
多线程环境下,建议使用 ConcurrentHashMap,或者使用 Collections.synchronizedMap(hashMap) 将 HashMap 转成线程同步的。 只能使用关联的键来获取值。 HashMap 只能存储对象,所以基本数据类型应该使用其包装器...
使用jQuery开发HashMap,包含一些基本的功能。