在使用map.entryset时可以知道这是一个导出Map所有键值对的函数集合，其中entry指的是键值对基本单位条目，其实在map接口就已经定义并且有simpleentry,ImmutableEntry(不可更改)两个实现，在实现MAP接口的类中也是使用entry为单位，以数组的形式存储
主要围绕几种典型的实现HashMap，concurrentHashMap,linkedHashMap
当我们使用hashmap时，其实内部已经给我们制定了数组大小，16kb（可以指定，所以当我们使用时尽量估计其可能大小，因为扩容是一件复制过程），阀值threshold 0.75f（超过就会以2进行扩容）
this(initialCapacity, DEFAULT_LOAD_FACTOR);//默认大小
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//2倍扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
当我们put加入entry时，存放在entry[]中，大致过程是，计算其key的hash值，然后将hash与entry.size容量进行位运算，计算出其在entry[]中位置，其中我们都知道的同一key值会进行覆盖，不会增加真实存放容量大小，会返回原value值，代码如下
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
扩容过程中是对key的一次hash计算，和重新在新数组中进行定位，所以除了复制复制之后的消耗至少还有每个entry的indexfor()损耗
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
至于hashmap具有高效率的读取操作，从put()就应该能够得出，不管是增加或是读取，在entry数组中是根据key与size进行位运算后直接得出在数组中的位置，代码如下
key的hash计算
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
位运算
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
HashMap的移除操作，有点不是很不明白，但是把自己的认为写下来
hashmap内部是对entry进行了扩展的，其中增加了了一个Entry next属性，在createEntry方法内
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//获取entry初始的数组，这里面的entry应该是在#1构造过程中entry没
//有任何值
table[bucketIndex] = new Entry<>(hash, key, value, e);//这里面把初始化的entry放进去，就相当每
//个entry都含有一个初始化的entry，#2这就相当于remove操作就是使用这个entry来替代原来的entry
size++;
}
#1
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);//初始化
}
#2
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//替代(没有使用比如标志清除位来进行逻辑判断，或者采用其他方式，使用空间换时间，而且没有其他过多的操作，直接调用方法来进行替换，就又使entry恢初
//始状态，个人认为，其实这里没有怎么看明白，)
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
至于hashmap的其他操作，containkey,putall，clear等基本是在上面实现的
对于map的并发控制，已经做出控制的concurrenthashmap，继承AbstractMap(内部重写了HashEntry<K,V>，并没有继承Hashmap),实现ConCurrentMap接口，内部进行同步控制是使用Reentrantlock()锁机制,Segment
static final class Segment<K,V> extends ReentrantLock implements Serializable
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);//获取锁
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();//释放锁
}
return oldValue;
}
linkedHashMap继承了HashMap，实现Map接口，从字面意思上看，就是在原来具有HashMap的基础上添加了链表的特性，以维护一个双向链表来对map映射关系进行排序（规则为map.key先后顺序），那么具体表现和内部的一些知识点：
双向链表的构造具体还是对map.entry进行重构，就像hashmap中entry增加了.next通过保存初始化entry进行清除原来的entry(key)，具体为像链表一样增加一个前驱节点指向和一个后驱节点指向，after,before,而保存前驱和后驱节点的当前节点用header来保存，这个做法在map的具体实现类里面（重写entry）很常见且非常有用，具体的整个实现尚未完全弄懂，有待研究
entry一部分
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;//前驱和后驱
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);//next 在remove() entry使用
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
}
具体构建链表代码
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
至于HashTable直接实现map接口，不允许key,value=null，是线程安全的，使用synchronized同步机制，又实现了dictionary，顾名思义具有类似词典的映射功能，只是其key，value规定object对象，即为对象集合（jdk注：此类已过时。新的实现应该实现 Map 接口，而不是扩展此类），虽然map中k-v需要进行装箱和拆箱，而且类型检查，类型擦除，损耗性能，但是更为灵活，我想这可能是尽管hashtable与hashmap（保证线程安全之后）比较效率有较小差异，而且步骤少，但是大家却喜欢使用hashmap的原因。
TreeMap是一种二叉树结构的存储方式，并没有使用数组形式，可以看出查询效率应该没有以hashmap高，但是因为在存储过程中。可以进行key的compare所以treemap是可以理解为有序的结构，其中remove操作，应该是将关联节点置为null，添加即创建entry，关联节点，这种方式在设计模式上可以理解为组合模式，使用数组的确不合适，处理麻烦，我试过实现。在lucene为例的索引中倒排列表里面的单词的有一种方式是采用这种形式进行存储的。具体如何实现，详细的东西，源码神马的看了都非常清晰和透彻
以上总结为对map的数据类型的一些认知，个人学习总结使用，虽然大部分以源代码形式，而且可能有些还不正确，讲个大概的数据类型的实现思路，但是这个对于使用数据类型的不同场景的选取有一些帮助，了解这些数据类型之间的关系和性能问题的出现与解决有一定提升。
附1：
线程安全一般3重办法，具体网上资料比较多：
1.信号量semaphore
2.锁机制lock（同步synchronized，在jvm中也是锁机制，只是具体指令不一样）
3.CAS（比较和交换算法，jdk有提供一些此算法的实现类型在java.util.concurrent.atomic中，或者使用第三方AMINO框架提供的数据类型）
附2：
查看源码可以下载open-jdk，如果找不到可以使用jd-gui反编译class,非常好用，或者直接在krugle里面搜索，基本可以找到相关的类和扩展信息。
附2：
查看源码可以下载open-jdk，如果找不到可以使用jd-gui反编译class,非常好用，或者直接在krugle里面搜索，基本可以找到相关的类和扩展信息。
相关推荐
json与bean,array,list,map,简单类型之间的封装、解析
C++解析协议简单示例 解析highway map data 协议数据简单示例
主要介绍了Java中的Map集合简单汇总解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
基本OSM解析器 自述 BasicOSMParser 是一组 Java 类，允许解析原始 OSM XML 文件。 然后您就可以在您的程序中操作这些 Java 对象。 您还可以将数据导出为 CSV 文件。 这个库非常容易理解。 它使用默认的 Java SAX ...
JSON官网上推荐的使用java解析json的类库，官网下载后的是未编译打包的java文件，这是我打包后的东东，使用时直接添加进Build path即可，简单实用……
主要介绍了Java中map内部存储方式解析的相关内容，涉及其实现方式，以及对存储方式作了简单的比较，具有一定参考价值，需要的朋友可了解下。
我写的用VC解析xml文件，通过MSXML，比较简单，不过是个好例子，很小，例子是CHINAmap2008中的城市，飞机，机场xml文件，希望能有小用。
在等待银行专线的过程中，自己闭门造车做了一个简单的8583报文解析框架 —— Simple8583，将程序重写了一遍，渠道中的代码量少了不少，这几天中行的接口在测试环境终于调试完成了。抽空分享一下这段时间自己学到的...
osm-read, openstreetmap XML和PBF数据分析器 for node.js 和浏览器 使用函数和浏览器的PBF解析器 read介绍用法示例简单用法示例从URL示例解析 OSM XMLPBF随机访问分析器版本升级指南合并许可证联系人简介osm读取...
Freemind心智图文件.mm的Python解析器 介绍 我是思维导图的沉迷者。 我每天都使用它进行项目管理和记录。 我在思维导图上应用了GTD（让事情完成）的概念。 Freemind是一个完美的工具，自2003年以来我就一直在使用它...
雅虎日本的工程师开源了这个项目，亮点是可以使用 for-in、map 和 filter。
FastJson是阿里巴巴工程师开发的一个json处理工具包，包括“序列化”和“反序列化”两部分。支持Java Bean、集合、Map、日期等等。我这是用fastjson解析json串一个简单的案例。
外部库OpenNetworkMap 使用以下库： BasicOSMParser - OpenStreetMap 数据解析器 - Adrien Pavie - Batik - SVG Java 工具包 - Apache 基金会 - JUnit - 单元测试框架 - JUnit 团队 - OSBCP CSS 解析器 - CSS 解析器...
mfc中引用#include "MyJson.h",就可以直接使用了，代码简单方便，总共2个个文件，安全明了，不需要复杂的引用编译，只需要一个类就可以完成json字符串转map,
本身是一项非常简单的任务，应该考虑增加工作量。 如果您熟悉docker，可能值得一看 。 用法 专业提示：如果数据结构良好，则{country: 'de', postalcode='10115', street='Somestreet XX'}比{q: 'Somestreet XX, ...
下面写一个简单的示例和解析。至于此种方法使用多进程的效率问题，还希望大佬予以指正。 示例： """ 探索pool.map多进程执行方式的实质 """ from multiprocessing import Pool from time import sleep from ...
人性化的开放时间是Python 3模块，允许简单使用OpenStreetMap中使用的open_hours字段。 由于缺少空闲时间，因此该模块的开发被暂停了。 您当然可以使用它，但是它的功能不会（很长）片刻就发展。 如果您想成为维护...
将对象类型，List包裹对象类型，list包裹String类型，list包裹Map类型数据转换成json数据简单示例源码
简单说下思路： 首先利用 map 将 HTML 字符实体与对应字符进行一个匹配存储 双重循环，首先遍历 map 中所有的字符实体，再遍历字符串 text 进行匹配查找 这里匹配查找使用 string 对象的 substr 方法进行快速定位...