Map是一种非常用的数据结构,在一些底层框架或者效率十分关键的地方也是十分常用的。我写这篇文章的意图就是把我关于高效使用map的一些经验技巧写下来,当然其中我的一些观点可能不对,如果有朋友发现有错误的地方,欢迎指正。
在Java中Map是什么呢?先说HashMap,java.util.HashMap这个类,就是一个链表数组,最简单的理解就是把key的hashCode % len得到所在链表的位置,然后在链表上挨个查找。
这个代码摘抄自JDK 6的java.util.HashMap,为了方便说明问题,有所删减。其中一些关键点,我都已经注释说明
Java代码
public class HashMap<K, V> {
// Entry是一个很标准的链表结构
static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
}
transient Entry[] table; // table就是一个链表数组
transient int size;
public HashMap(int initialCapacity) {
// 注意,这里是性能的一个很关键地方,如果自行编写HashMap时,table.length不是2的n次方,性能会很容易很糟糕。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = new Entry[capacity];
}
// get方法所做的事情包括hash、indexFor、链表遍历、链表中每个Entry.key的相等比较
public V get(Object key) {
int hash = hash(key.hashCode()); //
int index = indexFor(hash, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) { // 链表遍历
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e.value;
}
}
return null;
}
public V put(K key, V value) {
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, index);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold) {
resize(2 * table.length); // 多个线程并发访问时,resize会调用transfer方法,而transfer方法会在某种情况下产生死循环。
}
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length - 1); // 这个比取模运算%速度快。
}
}
通过上面的代码和注释,我们基本能够了解HashMap是干啥的,他是一个很简单很常用的数据结构,本身HashMap的性能很好,但是某些场景下,我们还是对HashMap做定制化的处理,使得其更高效。
例如Key是int的场景,专门编写IntHashMap能够获得更高效的性能,中间能够减少Integer对象的产生,减轻GC负担,同时,hash函数和遍历时的equals也能省下不少动作。一个性能比较数据如下:
测试的代码:
Java代码
final int COUNT = 1000 * 10;
final int loopCount = 10000;
HashMap<Object, Object> map = new HashMap<Object, Object>(); // IntHashMap测试时相对应是IntHashMap
for (int i = 0; i < loopCount; ++i) {
for (int j = 0; j < COUNT; ++j) {
if (map.get(j) == null) {
map.put(j, value);
}
}
}
结果:
Map类型 耗时 YoungGC FullGC
IntHashmap<Object> 5,437 0 0
Hashmap<Integer, Object> 13,312 251 0
从结果来看,使用原生类型int替代Integer作为key,性能翻倍。
HashMap的性能是很好的,但不是线程安全的,最恶劣的并发问题就是table的resize时产生死循环。为了线程安全,我们通常需要使用 ConcurrentHashMap,ConcurrentHashMap缺省能够支持16个并发写,而且不会产生令人十分讨厌的 ConcurrentModificationException。可是ConcurrentHashMap的性能并不好,如上面的测试场景,测试性能数 据如下:
Map类型 耗时 YoungGC FullGC
IntHashmap<Object> 5,437 0 0
Hashmap<Integer, Object> 13,312 251 0
ConcurrentIntHashmap<Object> 21,452 0 0
ConcurrentHashmap<Integer, Object> 37,624 1409 0
通过测试数据看,ConcurrentHashMap的get性能要比HashMap性能要差很多,3倍多的差距。
有没有办法做到线程安全,但是get性能接近HashMap呢?答案是肯定的!ConcurrentHashMap其实就是一个Segment数 组,每个Segment的功能类似一个HashMap,Segment是线程安全的,一个ConcurrentHashMap缺省包含16个 Segment,所以支持16个并发写入,但大多数场景我们并不需要并发写入,需要的是线程安全并且高效查找。那么思路就很明确了,把 ConcurentHashMap的Segement拿出来,修改成一个HashMap,性能如何?测试数据补上:
Map类型 耗时 YoungGC FullGC 说明
IntHashmap<Object> 5,437 0 0 参考HashMap修改而成
Hashmap<Integer, Object> 13,312 251 0
ConcurrentIntHashmap<Object> 21,452 0 0 参考ConcurrentHashMap修改而成
ConcurrentHashmap<Integer, Object> 37,624 1409 0
FastConcurrentIntHashmap<Object> 5,703 0 0 参考ConcurrentHashMap.Segment修改而成
FastConcurrentHashmap<Integer, Object> 12,499 225 0 参考ConcurrentHashMap.Segment修改而成
从数据来看,FastConcurrentIntHashmap的性能非常好,接近IntHashMap 了,FastConcurrentHashmap<Integer, Object>的性能则比HashMap速度还快一点点,可能是ConcurrentHashMap.Segement的实现更高效吧。
总结一下,我们可以参考HashMap编写IntHashMap,参考ConcurrentHashMap编写 ConcurrentIntHashMap,参考ConcurrentHashMap.Segment编写专门针对读取优化的 FastConcurrentHashMap,从而在特别场景下获得更快的性能。
同理,我们也可以参考HashMap和ConcurrentHashMap编写相应的CharArrayHashMap和 CharArrayConcurrentHashMap,在特别场景下,能够获得比HashMap<String, Object>以及ConcurrentHashMap<String, Object>更好的性能。
在Java中Map是什么呢?先说HashMap,java.util.HashMap这个类,就是一个链表数组,最简单的理解就是把key的hashCode % len得到所在链表的位置,然后在链表上挨个查找。
这个代码摘抄自JDK 6的java.util.HashMap,为了方便说明问题,有所删减。其中一些关键点,我都已经注释说明
Java代码
public class HashMap<K, V> {
// Entry是一个很标准的链表结构
static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
}
transient Entry[] table; // table就是一个链表数组
transient int size;
public HashMap(int initialCapacity) {
// 注意,这里是性能的一个很关键地方,如果自行编写HashMap时,table.length不是2的n次方,性能会很容易很糟糕。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = new Entry[capacity];
}
// get方法所做的事情包括hash、indexFor、链表遍历、链表中每个Entry.key的相等比较
public V get(Object key) {
int hash = hash(key.hashCode()); //
int index = indexFor(hash, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) { // 链表遍历
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e.value;
}
}
return null;
}
public V put(K key, V value) {
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, index);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold) {
resize(2 * table.length); // 多个线程并发访问时,resize会调用transfer方法,而transfer方法会在某种情况下产生死循环。
}
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length - 1); // 这个比取模运算%速度快。
}
}
通过上面的代码和注释,我们基本能够了解HashMap是干啥的,他是一个很简单很常用的数据结构,本身HashMap的性能很好,但是某些场景下,我们还是对HashMap做定制化的处理,使得其更高效。
例如Key是int的场景,专门编写IntHashMap能够获得更高效的性能,中间能够减少Integer对象的产生,减轻GC负担,同时,hash函数和遍历时的equals也能省下不少动作。一个性能比较数据如下:
测试的代码:
Java代码
final int COUNT = 1000 * 10;
final int loopCount = 10000;
HashMap<Object, Object> map = new HashMap<Object, Object>(); // IntHashMap测试时相对应是IntHashMap
for (int i = 0; i < loopCount; ++i) {
for (int j = 0; j < COUNT; ++j) {
if (map.get(j) == null) {
map.put(j, value);
}
}
}
结果:
Map类型 耗时 YoungGC FullGC
IntHashmap<Object> 5,437 0 0
Hashmap<Integer, Object> 13,312 251 0
从结果来看,使用原生类型int替代Integer作为key,性能翻倍。
HashMap的性能是很好的,但不是线程安全的,最恶劣的并发问题就是table的resize时产生死循环。为了线程安全,我们通常需要使用 ConcurrentHashMap,ConcurrentHashMap缺省能够支持16个并发写,而且不会产生令人十分讨厌的 ConcurrentModificationException。可是ConcurrentHashMap的性能并不好,如上面的测试场景,测试性能数 据如下:
Map类型 耗时 YoungGC FullGC
IntHashmap<Object> 5,437 0 0
Hashmap<Integer, Object> 13,312 251 0
ConcurrentIntHashmap<Object> 21,452 0 0
ConcurrentHashmap<Integer, Object> 37,624 1409 0
通过测试数据看,ConcurrentHashMap的get性能要比HashMap性能要差很多,3倍多的差距。
有没有办法做到线程安全,但是get性能接近HashMap呢?答案是肯定的!ConcurrentHashMap其实就是一个Segment数 组,每个Segment的功能类似一个HashMap,Segment是线程安全的,一个ConcurrentHashMap缺省包含16个 Segment,所以支持16个并发写入,但大多数场景我们并不需要并发写入,需要的是线程安全并且高效查找。那么思路就很明确了,把 ConcurentHashMap的Segement拿出来,修改成一个HashMap,性能如何?测试数据补上:
Map类型 耗时 YoungGC FullGC 说明
IntHashmap<Object> 5,437 0 0 参考HashMap修改而成
Hashmap<Integer, Object> 13,312 251 0
ConcurrentIntHashmap<Object> 21,452 0 0 参考ConcurrentHashMap修改而成
ConcurrentHashmap<Integer, Object> 37,624 1409 0
FastConcurrentIntHashmap<Object> 5,703 0 0 参考ConcurrentHashMap.Segment修改而成
FastConcurrentHashmap<Integer, Object> 12,499 225 0 参考ConcurrentHashMap.Segment修改而成
从数据来看,FastConcurrentIntHashmap的性能非常好,接近IntHashMap 了,FastConcurrentHashmap<Integer, Object>的性能则比HashMap速度还快一点点,可能是ConcurrentHashMap.Segement的实现更高效吧。
总结一下,我们可以参考HashMap编写IntHashMap,参考ConcurrentHashMap编写 ConcurrentIntHashMap,参考ConcurrentHashMap.Segment编写专门针对读取优化的 FastConcurrentHashMap,从而在特别场景下获得更快的性能。
同理,我们也可以参考HashMap和ConcurrentHashMap编写相应的CharArrayHashMap和 CharArrayConcurrentHashMap,在特别场景下,能够获得比HashMap<String, Object>以及ConcurrentHashMap<String, Object>更好的性能。
发表评论
-
初学者学习linux
2012-12-19 17:53 609http://wuhaoshu.blog.51cto.com/ ... -
jquery选择器总结
2012-11-21 11:43 9151.<script type="text/ja ... -
外网的压力测试
2012-11-07 10:32 1102外网的压力测试,可以使用apache的ab或curl-load ... -
试着学学object-c
2012-11-05 15:50 7291.http://www.neatstudio.com/sho ... -
栈的基本原理,实现自己的堆栈
2012-10-23 10:16 1216栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在 ... -
java双括弧初始化
2012-10-22 17:39 135001. Map map = new HashMap() {{ ... -
学习java单例模式
2012-10-22 16:16 664http://calmness.iteye.com/blog/ ... -
JsonUtil错误总结
2012-09-26 10:10 1013java.lang.Integer cannot be cas ... -
struts2总结错误
2012-09-25 10:40 7061.数据类型的不对应,一般是,后台要求int而前端的zoneI ... -
Jquery总结
2012-09-18 14:08 0$.toJSON(); $.parseJson(unescap ... -
mysql学习总结
2012-08-23 17:19 8081.<![CDATA[ select ifnull(su ... -
学习强者的成长之路
2012-08-09 10:25 806http://xwnet.blog.51cto.com/233 ... -
MD5正规的写法
2012-07-20 10:26 846public static String getMD5(byt ... -
引用:异常处理!
2012-07-20 09:37 681... -
关于网站的设计
2012-07-19 10:08 696网站的性能优化:http://www.cnblogs.com/ ... -
eval用法
2012-07-12 10:12 846在函数中改变全局变量 var X2={} X2.Eval= ... -
错误总结
2012-07-11 10:38 6121.missing ) in parenthetical错误可 ... -
登录验证struts2
2012-07-09 09:40 706类需要继承ActionSupport,重写execute方法, ... -
学习js的好地方
2012-06-28 13:16 728http://www.zhuoda.org/lunzi/dir ... -
登陆页面
2012-06-26 18:42 921http://themeforest.net/item/dre ...
相关推荐
C++实现的支持插入顺序的高效map https://github.com/nlohmann/fifo_map
map算法MAP算法在Turbo码译码中的实现及性能在数域中,串行级联的MAP算法是用于获得高性能的Turbo码译码器。一般情况下,解码器通过可编程门...随着Turbo码解码器同步技术的实现,提出了一种高效连续的MAP译码算法。
HENON MAP的MATLAB实现,可以尝试一下 简单高效
在使用hash_map的时候,发现他对字符串的支持不是很好,就特写了一个str hash map 的程序,设置和提取键值的性能是hash_map 的20 倍左右。 特意拿出来给大家分享,如果有改进的, 请大家指出。
它通过集成高效的地图(map)数据结构,为用户提供了一种快速、直观的方式来管理和展示排队信息。以下是排队取号map组件的主要特点: 数据结构优化:利用map数据结构,实现快速的键值对存取,优化排队数据处理。 动态...
相对于springBeanUtils更加高效的对象复制方法mapstruct
本文将讨论在ADI Blackfin 通用定点DSP 处理器上如何高效实现Turbo MAP 解码 器的技术。
你知道map的遍历方法有几种吗? 那这几种的区别是什么呢? 那种更简单、高效呢? 我的资源文件将告诉你。
基于DSP处理器的UMTS Turbo MAP解码器高效实现.pdf
sparse-map一个高效hash map和hash set的C 实现
音视频-编解码-Turbo编译码系统高效MAP译辅助SNR估计与多项式交织器设计.pdf
graphhopper是一个快速且内存高效的java路由引擎,在apache许可证2.0下发布。默认情况下,它使用openstreetmap和gtfs数据,但它可以导入其他数据源。
Map内部通常使用哈希表或平衡树等数据结构来保证这一操作的高效性。 - **删除**:根据键移除键值对。如果键不存在,某些实现可能不做操作或抛出异常。 - **遍历**:顺序或无序地访问Map中的所有键值对,这对于数据...
一个动态平衡二叉树算法的MAP的template,使用预分配内存,经测试(顺序插入256万条数据)效率比STL高5倍。乱序插入256万条数据,是stl的2倍。本算法在最差情况下,其树深 (n),而且每次树的平衡操作数为O(1).
MAP-LAB 设计背后的主要思想是为 MATLAB 用户和研究人员提供一个高效且易于使用的 GUI 来生成地图,而无需编写脚本或使用 MATLAB 的命令窗口。 MAP-LAB 利用 M_Map 制图工具箱的功能,这是一个辅助绘制地理空间信息...
Algorithm-map_matching.zip,寻找车辆应该行驶的街道以生成给定GPS轨迹的算法,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
TDS-OFDM系统高效并行MAP定时恢复算法
ngx-amapngx-amap是为在Angular (ver> = 2.x)项目中便捷,高效地使用高德地图Javascript API而构建的组件集合目录最新进度2020.02.06:v3.0.0 新:支持AMapUI库,可通过AmapUILoaderService服务加载使用,部分UI...
ECMAScript 6以前,在JavaScript中实现“键/值”式存储可以使用Object来方便高效地完成,也就是使用对象属性作为键,再使用属性来引用值。但这种实现并非没有问题,为此TC39委员会专门为“键/值”存储定义了一个...
为了跨帧匹配与同一个人对应的姿势,我们还提供了一个高效的在线姿势跟踪器,称为姿势流。它是第一个开源在线姿势跟踪器,在PoseTrack Challenge数据集上实现了60+ mAP(66.5 mAP)和50+ MOTA(58.3 MOTA)。Alpha...