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 657http://wuhaoshu.blog.51cto.com/ ... -
jquery选择器总结
2012-11-21 11:43 9461.<script type="text/ja ... -
外网的压力测试
2012-11-07 10:32 1136外网的压力测试,可以使用apache的ab或curl-load ... -
试着学学object-c
2012-11-05 15:50 7961.http://www.neatstudio.com/sho ... -
栈的基本原理,实现自己的堆栈
2012-10-23 10:16 1248栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在 ... -
java双括弧初始化
2012-10-22 17:39 137501. Map map = new HashMap() {{ ... -
学习java单例模式
2012-10-22 16:16 697http://calmness.iteye.com/blog/ ... -
JsonUtil错误总结
2012-09-26 10:10 1055java.lang.Integer cannot be cas ... -
struts2总结错误
2012-09-25 10:40 7241.数据类型的不对应,一般是,后台要求int而前端的zoneI ... -
Jquery总结
2012-09-18 14:08 0$.toJSON(); $.parseJson(unescap ... -
mysql学习总结
2012-08-23 17:19 8381.<![CDATA[ select ifnull(su ... -
学习强者的成长之路
2012-08-09 10:25 836http://xwnet.blog.51cto.com/233 ... -
MD5正规的写法
2012-07-20 10:26 876public static String getMD5(byt ... -
引用:异常处理!
2012-07-20 09:37 705... -
关于网站的设计
2012-07-19 10:08 740网站的性能优化:http://www.cnblogs.com/ ... -
eval用法
2012-07-12 10:12 877在函数中改变全局变量 var X2={} X2.Eval= ... -
错误总结
2012-07-11 10:38 6371.missing ) in parenthetical错误可 ... -
登录验证struts2
2012-07-09 09:40 738类需要继承ActionSupport,重写execute方法, ... -
学习js的好地方
2012-06-28 13:16 793http://www.zhuoda.org/lunzi/dir ... -
登陆页面
2012-06-26 18:42 978http://themeforest.net/item/dre ...
相关推荐
TileMap(瓷砖地图)是一种高效且灵活的工具,常用于构建2D游戏的环境和场景。本素材包主要围绕如何使用TileMap来快速构造2D关卡,帮助开发者节省时间和精力,专注于游戏玩法的创新。 1. TileMap简介: TileMap是2...
C++中的`map`是一种关联式容器,它提供了一种基于键值对(Key-Value Pair)的数据存储方式。在C++标准库中,`map`位于`<map>`头文件内,它允许用户以...理解和熟练使用`map`可以帮助开发者编写更加高效和简洁的代码。
C++实现的支持插入顺序的高效map https://github.com/nlohmann/fifo_map
Google Map API 是一款强大的工具,它允许开发者在自己的网站或应用程序中嵌入地图功能,提供定位、导航、地理编码、路线规划等多种服务。...记住,始终要关注 API 的使用限制和最佳实践,以确保服务的稳定性和高效性。
《GameMap:游戏地图设计与分割技术详解》 在游戏开发中,地图是构建游戏世界不可或缺的元素。本文将深入探讨GameMap,一种专用于游戏地图设计和管理的工具,以及其中涉及到的关键技术和概念。 首先,我们要理解...
### Map 总结:原理与使用详解 #### 一、Map 概述 **Map** 是 C++ STL(Standard Template Library)中的一种关联容器,它主要用于存储键值对(Key-Value pairs)。Map 的特点在于它能高效地进行查找、插入和删除...
MapServer 是一个开源的Web GIS服务器,用于发布地图和地理数据。它由明尼苏达大学于20世纪90年代中期...MapServer与OpenLayers的结合,是开源Web GIS领域中的重要解决方案,提供了灵活、高效的地图服务和展示功能。
XML因其结构化和易于解析的特性,在数据交换和配置文件中广泛使用,而Map则作为Java中存储键值对的高效数据结构。在实际开发中,我们可能需要在XML和Map之间进行转换,以便于数据处理。本文将详细讲解如何使用Java...
自定义`Map`的一个挑战是实现高效的查找、插入和删除操作,这通常需要熟练掌握二叉搜索树的特性,尤其是红黑树的插入和旋转规则。此外,为了保证`Map`的线程安全,可能还需要考虑多线程环境下的同步机制,如互斥锁...
下面我们将详细探讨SSH框架与Map容器的使用。 **1. Spring框架中的Map容器** Spring作为IoC(Inversion of Control,控制反转)和AOP(Aspect Oriented Programming,面向切面编程)容器,允许开发者将对象之间的...
绘制电机效率MAP通常使用专业软件或者编程实现,如在描述中提到的"map.zip"可能就是一个用于绘制此类图表的程序。该程序可能包含了数据处理、曲线拟合以及二维图形绘制等功能。用户可能需要输入电机在不同工况下的...
在C++编程中,标准模板库(Standard Template Library, STL)提供了一种高效且方便的关联容器——map。本文将详细讲解map的特性和使用方法,帮助开发者更好地理解和运用这一强大的工具。 1. **map简介** map是一种...
- 遍历:通常使用迭代器或者增强for循环遍历Map中的键值对。 4. **Java中的Map接口**: - `HashMap`:基于哈希表实现,允许null键和null值。 - `TreeMap`:基于红黑树实现,保持键的排序,适用于需要有序Map的...
4. **gdb调试器**:虽然不是专门分析map文件的工具,但GDB能提供丰富的内存和代码执行信息,可以和map文件一起使用来深入理解程序行为。 在实际操作中,你可以通过以下步骤进行map文件分析: 1. **生成map文件**:...
在Java编程语言中,Map接口是集合框架的重要组成部分,它提供了键值对(key-value pairs)的存储方式。Map不是列表或数组,而是允许我们通过一个键...理解并正确使用这些Map类可以帮助你编写更高效、更可读的Java代码。
使用`insert`函数或直接使用成员初始化器列表可以向map中插入元素: ```cpp myMap.insert(std::make_pair("key1", "value1")); myMap["key2"] = "value2"; // 若键不存在,会自动创建并插入 ``` 3. **查找元素...
6. **结果解释**:根据Map图解析电机在不同工况下的表现,如高效区、最大功率点等。 在实际应用中,电机Map图对于优化电机设计、选择合适的驱动策略以及预测系统性能至关重要。通过理解并使用提供的MATLAB程序和...
《MapBrowser 1.2:梦幻西游的资源...总的来说,MapBrowser 1.2 是梦幻西游玩家的一款必备工具,它通过高效、便捷的方式,让玩家能够更深入地探索游戏世界,同时也提醒我们在享受游戏乐趣的同时,应合法合规使用资源。
在C++编程中,`std::map`和`std::unordered_map`是两种常见的关联容器,它们都用于存储键值对,但实现机制和性能特点有所不同。...理解和掌握这些容器的特性和性能差异,有助于编写更高效、更符合需求的代码。
总结,C++的STL`map`容器是处理键值对数据的强大工具,其增删查改操作高效且易于使用。学习并熟练掌握`map`的使用,能够显著提升C++编程的效率和代码质量。在实际编程中,我们应根据需求选择合适的容器,充分利用STL...