中国领先的IT技术网站
51CTO旗下网站
Java集合框架之 Java HashMap 源码解析
继上一篇文章Java集合框架综述后，今天正式开始分析具体集合类的代码，首先以既熟悉又陌生的HashMap开始。
作者：来源：ImportNew| 09:17
继上一篇文章后，今天正式开始分析具体集合类的代码，首先以既熟悉又陌生的开始。
签名（signature）
public&class&HashMap&K,V&&extends&AbstractMap&K,V&&implements&Map&K,V&,&Cloneable,&Serializable&
可以看到HashMap继承了
标记接口，用于表明HashMap对象会重写java.lang.Object#clone()方法，HashMap实现的是浅拷贝（shallow copy）。
标记接口，用于表明HashMap对象可以被序列化
比较有意思的是，HashMap同时继承了抽象类AbstractMap与接口Map，因为抽象类AbstractMap的签名为
public&abstract&class&AbstractMap&K,V&&implements&Map&K,V&&
上解释到：
在语法层面继承接口Map是多余的，这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的，起到了文档的作用
AbstractMap相当于个辅助类，Map的一些操作这里面已经提供了默认实现，后面具体的子类如果没有特殊行为，可直接使用AbstractMap提供的实现。
&code&It's&evil,&don't&use&it.&&/code&&
Cloneable这个接口设计的非常不好，最致命的一点是它里面竟然没有clone方法，也就是说我们自己写的类完全可以实现这个接口的同时不重写clone方法。
关于Cloneable的不足，大家可以去看看《Effective Java》一书的作者，在所给链接的文章里，Josh Bloch也会讲如何实现深拷贝比较好，我这里就不在赘述了。
在Eclipse中的outline面板可以看到Map接口里面包含以下成员方法与内部类：
Map_field_method
可以看到，这里的成员方法不外乎是&增删改查&，这也反映了我们编写程序时，一定是以&数据&为导向的。
在讲了Map虽然并不是Collection，但是它提供了三种&集合视角&（collection views），与下面三个方法一一对应：
Set&K& keySet()，提供key的集合视角
Collection&V& values()，提供value的集合视角
Set&Map.Entry&K, V&& entrySet()，提供key-value序对的集合视角，这里用内部类Map.Entry表示序对
AbstractMap对Map中的方法提供了一个基本实现，减少了实现Map接口的工作量。
举例来说：
如果要实现个不可变（unmodifiable）的map，那么只需继承AbstractMap，然后实现其entrySet方法，这个方法返回的set不支持add与remove，同时这个set的迭代器（iterator）不支持remove操作即可。
相反，如果要实现个可变（modifiable）的map，首先继承AbstractMap，然后重写（override）AbstractMap的put方法，同时实现entrySet所返回set的迭代器的remove方法即可。
设计理念（design concept）
哈希表（hash table）
HashMap是一种基于实现的map，哈希表（也叫关联数组）一种通用的数据结构，大多数的现代语言都原生支持，其概念也比较简单：key经过hash函数作用后得到一个槽（buckets或slots）的索引（index），槽中保存着我们想要获取的值，如下图所示
hash table demo
很容易想到，一些不同的key经过同一hash函数后可能产生相同的索引，也就是产生了冲突，这是在所难免的。
所以利用哈希表这种数据结构实现具体类时，需要：
设计个好的hash函数，使冲突尽可能的减少
其次是需要解决发生冲突后如何处理。
后面会重点介绍HashMap是如何解决这两个问题的。
HashMap的一些特点
线程非安全，并且允许key与value都为null值，HashTable与之相反，为线程安全，key与value都不允许null值。
不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能改变（resize的情况）
put、get操作的时间复杂度为O(1)。
遍历其集合视角的时间复杂度与其容量（capacity，槽的个数）和现有元素的大小（entry的个数）成正比，所以如果遍历的性能要求很高， 不要把capactiy设置的过高或把平衡因子（load
factor，当entry数大于capacity*loadFactor时，会进行resize，reside会导致key进行rehash）设置的过 低。
由于HashMap是线程非安全的，这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变（添加、删除entry，只改变entry的value的值不算结构改变），那么会报，专业术语叫fail-fast，尽早报错对于多线程程序来说是很有必要的。
Map m = Collections.synchronizedMap(new HashMap(...));&通过这种方式可以得到一个线程安全的map。
首先从构造函数开始讲，HashMap遵循，提供了一个参数为空的构造函数与有一个参数且参数类型为Map的构造函数。除此之外，还提供了两个构造函数，用于设置HashMap的容量（capacity）与平衡因子（loadFactor）。
public&HashMap(int&initialCapacity,&float&loadFactor)&{&&&&&if&(initialCapacity&&&0)&&&&&&&&&throw&new&IllegalArgumentException(&Illegal&initial&capacity:&&&+&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&initialCapacity);&&&&&if&(initialCapacity&&&MAXIMUM_CAPACITY)&&&&&&&&&initialCapacity&=&MAXIMUM_CAPACITY;&&&&&if&(loadFactor&&=&0&||&Float.isNaN(loadFactor))&&&&&&&&&throw&new&IllegalArgumentException(&Illegal&load&factor:&&&+&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loadFactor);&&&&&this.loadFactor&=&loadF&&&&&threshold&=&initialC&&&&&init();&}&public&HashMap(int&initialCapacity)&{&&&&&this(initialCapacity,&DEFAULT_LOAD_FACTOR);&}&public&HashMap()&{&&&&&this(DEFAULT_INITIAL_CAPACITY,&DEFAULT_LOAD_FACTOR);&}&&从代码上可以看到，容量与平衡因子都有个默认值，并且容量有个最大值&&&&&static&final&int&DEFAULT_INITIAL_CAPACITY&=&1&&&&4;&&&&&&&static&final&int&MAXIMUM_CAPACITY&=&1&&&&30;&&&&static&final&float&DEFAULT_LOAD_FACTOR&=&0.75f;&
可以看到，默认的平衡因子为0.75，这是权衡了时间复杂度与空间复杂度之后的最好取值（JDK说是最好的），过高的因子会降低存储空间但是查找（lookup，包括HashMap中的put与get方法）的时间就会增加。
这里比较奇怪的是问题：容量必须为2的指数倍（默认为16），这是为什么呢？解答这个问题，需要了解HashMap中哈希函数的设计原理。
哈希函数的设计原理
&&&&&&&final&int&hash(Object&k)&{&&&&&&int&h&=&hashS&&&&&&if&(0&!=&h&&&&k&instanceof&String)&{&&&&&&&&&&return&sun.misc.Hashing.stringHash32((String)&k);&&&&&&}&&&&&&h&^=&k.hashCode();&&&&&&&&&&&&&&&&&&&&&&&&h&^=&(h&&&&&20)&^&(h&&&&&12);&&&&&&return&h&^&(h&&&&&7)&^&(h&&&&&4);&}&&&&static&int&indexFor(int&h,&int&length)&{&&&&&&&&&&&&return&h&&&(length-1);&}&
看到这么多位操作，是不是觉得晕头转向了呢，还是搞清楚原理就行了，毕竟位操作速度是很快的，不能因为不好理解就不用了。
网上说这个问题的也比较多，我这里根据自己的理解，尽量做到通俗易懂。
在哈希表容量（也就是buckets或slots大小）为length的情况下，为了使每个key都能在冲突最小的情况下映射到[0,length)（注意是左闭右开区间）的索引（index）内，一般有两种做法：
让length为素数，然后用hashCode(key) mod length的方法得到索引
让length为2的指数倍，然后用hashCode(key) & (length-1)的方法得到索引
用的是方法1，HashMap用的是方法2。
因为本篇主题讲的是HashMap，所以关于方法1为什么要用素数，我这里不想过多介绍，大家可以看。
重点说说方法2的情况，方法2其实也比较好理解：
因为length为2的指数倍，所以length-1所对应的二进制位都为1，然后在与hashCode(key)做与运算，即可得到[0,length)内的索引
但是这里有个问题，如果hashCode(key)的大于length的值，而且hashCode(key)的二进制位的低位变化不大，那么冲突就会很多，举个例子：
Java中对象的哈希值都32位整数，而HashMap默认大小为16，那么有两个对象那么的哈希值分别为：0xABAB0000与0xBABA0000，它们的后几位都是一样，那么与16异或后得到结果应该也是一样的，也就是产生了冲突。
造成冲突的原因关键在于16限制了只能用低位来计算，高位直接舍弃了，所以我们需要额外的哈希函数而不只是简单的对象的hashCode方法了。
具体来说，就是HashMap中hash函数干的事了
首先有个随机的hashSeed，来降低冲突发生的几率
然后如果是字符串，用了sun.misc.Hashing.stringHash32((String) k);来获取索引值
最后，通过一系列无符号右移操作，来把高位与低位进行异或操作，来降低冲突发生的几率
右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该就是把高位与低位做异或运算，至于这几个数是如何选取的，就不清楚了，网上搜了半天也没统一且让人信服的说法，大家可以参考下面几个链接：
HashMap.Entry
HashMap中存放的是HashMap.Entry对象，它继承自Map.Entry，其比较重要的是构造函数
static&class&Entry&K,V&&implements&Map.Entry&K,V&&{&&&&&final&K&&&&&&V&&&&&&Entry&K,V&&&&&&&int&&&&&&Entry(int&h,&K&k,&V&v,&Entry&K,V&&n)&{&&&&&&&&&value&=&v;&&&&&&&&&next&=&n;&&&&&&&&&key&=&k;&&&&&&&&&hash&=&h;&&&&&}&&&&&&&&&&public&final&int&hashCode()&{&&&&&&&&&&&&&&&&&&return&Objects.hashCode(getKey())&^&Objects.hashCode(getValue());&&&&&}&&&&&&&&&&&&&&void&recordAccess(HashMap&K,V&&m)&{&&&&&}&&&&&&&&&&&&&void&recordRemoval(HashMap&K,V&&m)&{&&&&&}&}&
可以看到，Entry实现了单向链表的功能，用next成员变量来级连起来。
介绍完Entry对象，下面要说一个比较重要的成员变量
* The table, resized as necessary. Length MUST Always be a power of two.
//HashMap内部维护了一个为数组类型的Entry变量table，用来保存添加进来的Entry对象
transient Entry&K,V&[] table = (Entry&K,V&[]) EMPTY_TABLE;
你也许会疑问，Entry不是单向链表嘛，怎么这里又需要个数组类型的table呢？
我翻了下之前的算法书，其实这是解决冲突的一个方式：，效果如下：
链地址法处理冲突得到的散列表
就是相同索引值的Entry，会以单向链表的形式存在
链地址法的可视化
网上找到个很好的网站，用来可视化各种常见的算法，很棒。瞬间觉得国外大学比国内的强不知多少倍。
下面的链接可以模仿哈希表采用链地址法解决冲突，大家可以自己去玩玩
get操作相比put操作简单，所以先介绍get操作
public&V&get(Object&key)&{&&&&&&&&&&if&(key&==&null)&&&&&&&&&return&getForNullKey();&&&&&Entry&K,V&&entry&=&getEntry(key);&&&&&return&null&==&entry&?&null&:&entry.getValue();&}&private&V&getForNullKey()&{&&&&&if&(size&==&0)&{&&&&&&&&&return&null;&&&&&}&&&&&&&&&&&&&&&for&(Entry&K,V&&e&=&table[0];&e&!=&null;&e&=&e.next)&{&&&&&&&&&if&(e.key&==&null)&&&&&&&&&&&&&return&e.&&&&&}&&&&&return&null;&}&final&Entry&K,V&&getEntry(Object&key)&{&&&&&if&(size&==&0)&{&&&&&&&&&return&null;&&&&&}&&&&&int&hash&=&(key&==&null)&?&0&:&hash(key);&&&&&&&&&&&&&&&for&(Entry&K,V&&e&=&table[indexFor(hash,&table.length)];&&&&&&&&&&e&!=&null;&&&&&&&&&&e&=&e.next)&{&&&&&&&&&Object&k;&&&&&&&&&if&(e.hash&==&hash&&&&&&&&&&&&&&&&((k&=&e.key)&==&key&||&(key&!=&null&&&&key.equals(k))))&&&&&&&&&&&&&return&e;&&&&&}&&&&&return&null;&}&
put操作（含update操作）
因为put操作有可能需要对HashMap进行resize，所以实现略复杂些
private&void&inflateTable(int&toSize)&{&&&&&&&&&&&&&&&int&capacity&=&roundUpToPowerOf2(toSize);&&&&&&&&&&threshold&=&(int)&Math.min(capacity&*&loadFactor,&MAXIMUM_CAPACITY&+&1);&&&&&table&=&new&Entry[capacity];&&&&&initHashSeedAsNeeded(capacity);&}&&&&&&public&V&put(K&key,&V&value)&{&&&&&if&(table&==&EMPTY_TABLE)&{&&&&&&&&&inflateTable(threshold);&&&&&}&&&&&if&(key&==&null)&&&&&&&&&return&putForNullKey(value);&&&&&int&hash&=&hash(key);&&&&&int&i&=&indexFor(hash,&table.length);&&&&&&&&&&&&&&&for&(Entry&K,V&&e&=&table[i];&e&!=&null;&e&=&e.next)&{&&&&&&&&&Object&k;&&&&&&&&&&&&&&&&&&&&&&&&&&&if&(e.hash&==&hash&&&&((k&=&e.key)&==&key&||&key.equals(k)))&{&&&&&&&&&&&&&V&oldValue&=&e.&&&&&&&&&&&&&e.value&=&&&&&&&&&&&&&&e.recordAccess(this);&&&&&&&&&&&&&return&oldV&&&&&&&&&}&&&&&}&&&&&&&&&&modCount++;&&&&&addEntry(hash,&key,&value,&i);&&&&&return&null;&}&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++;&}&&void&resize(int&newCapacity)&{&&&&&Entry[]&oldTable&=&&&&&&int&oldCapacity&=&oldTable.&&&&&&&&&&if&(oldCapacity&==&MAXIMUM_CAPACITY)&{&&&&&&&&&threshold&=&Integer.MAX_VALUE;&&&&&&&&&return;&&&&&}&&&&&Entry[]&newTable&=&new&Entry[newCapacity];&&&&&&&&&&transfer(newTable,&initHashSeedAsNeeded(newCapacity));&&&&&table&=&newT&&&&&threshold&=&(int)Math.min(newCapacity&*&loadFactor,&MAXIMUM_CAPACITY&+&1);&}&&&&void&transfer(Entry[]&newTable,&boolean&rehash)&{&&&&&int&newCapacity&=&newTable.&&&&&&&&&&for&(Entry&K,V&&e&:&table)&{&&&&&&&&&while(null&!=&e)&{&&&&&&&&&&&&&Entry&K,V&&next&=&e.&&&&&&&&&&&&&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&=&&&&&&&&&&}&&&&&}&}&&&&&final&boolean&initHashSeedAsNeeded(int&capacity)&{&&&&&boolean&currentAltHashing&=&hashSeed&!=&0;&&&&&boolean&useAltHashing&=&sun.misc.VM.isBooted()&&&&&&&&&&&&&&&&(capacity&&=&Holder.ALTERNATIVE_HASHING_THRESHOLD);&&&&&&&&&&&&&&&&&&&&boolean&switching&=&currentAltHashing&^&useAltH&&&&&if&(switching)&{&&&&&&&&&hashSeed&=&useAltHashing&&&&&&&&&&&&&?&sun.misc.Hashing.randomHashSeed(this)&&&&&&&&&&&&&:&0;&&&&&}&&&&&return&&}&
remove操作
public&V&remove(Object&key)&{&&&&&Entry&K,V&&e&=&removeEntryForKey(key);&&&&&&&&&&return&(e&==&null&?&null&:&e.value);&}&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&=&&&&&&&&&&&while&(e&!=&null)&{&&&&&&&&&Entry&K,V&&next&=&e.&&&&&&&&&Object&k;&&&&&&&&&if&(e.hash&==&hash&&&&&&&&&&&&&&&&((k&=&e.key)&==&key&||&(key&!=&null&&&&key.equals(k))))&{&&&&&&&&&&&&&modCount++;&&&&&&&&&&&&&size--;&&&&&&&&&&&&&if&(prev&==&e)&&&&&&&&&&&&&&&&&&table[i]&=&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&prev.next&=&&&&&&&&&&&&&&e.recordRemoval(this);&&&&&&&&&&&&&return&e;&&&&&&&&&}&&&&&&&&&prev&=&e;&&&&&&&&&e&=&&&&&&}&&&&&return&e;&}&
到现在为止，HashMap的增删改查都介绍完了。
一般而言，认为HashMap的这四种操作时间复杂度为O(1)，因为它hash函数性质较好，保证了冲突发生的几率较小。
HashMap的序列化
介绍到这里，基本上算是把HashMap中一些核心的点讲完了，但还有个比较严重的问题：保存Entry的table数组为transient的，也就是说在进行序列化时，并不会包含该成员，这是为什么呢？
transient Entry&K,V&[] table = (Entry&K,V&[]) EMPTY_TABLE;
为了解答这个问题，我们需要明确下面事实：
Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值
我们可以试想下面的场景：
我们在机器A上算出对象A的哈希值与索引，然后把它插入到HashMap中，然后把该HashMap序列化后，在机器B上重新算对象的哈希值与索引，这与机器A上算出的是不一样的，所以我们在机器B上get对象A时，会得到错误的结果。
所以说，当序列化一个HashMap对象时，保存Entry的table是不需要序列化进来的，因为它在另一台机器上是错误的。
因为这个原因，HashMap重现了writeObject与readObject&方法
private&void&writeObject(java.io.ObjectOutputStream&s)&&&&&throws&IOException&{&&&&&&&&&&s.defaultWriteObject();&&&&&&&&&&&if&(table==EMPTY_TABLE)&{&&&&&&&&&s.writeInt(roundUpToPowerOf2(threshold));&&&&&}&else&{&&&&&&&&s.writeInt(table.length);&&&&&}&&&&&&&&&&&s.writeInt(size);&&&&&&&&&&&if&(size&&&0)&{&&&&&&&&&for(Map.Entry&K,V&&e&:&entrySet0())&{&&&&&&&&&&&&&s.writeObject(e.getKey());&&&&&&&&&&&&&s.writeObject(e.getValue());&&&&&&&&&}&&&&&}&}&&private&static&final&long&serialVersionUID&=&181265L;&&private&void&readObject(java.io.ObjectInputStream&s)&&&&&&throws&IOException,&ClassNotFoundException&{&&&&&&&&&&s.defaultReadObject();&&&&&if&(loadFactor&&=&0&||&Float.isNaN(loadFactor))&{&&&&&&&&&throw&new&InvalidObjectException(&Illegal&load&factor:&&&+&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loadFactor);&&&&&}&&&&&&&&&&&table&=&(Entry&K,V&[])&EMPTY_TABLE;&&&&&&&&&&&s.readInt();&&&&&&&&&&&&int&mappings&=&s.readInt();&&&&&if&(mappings&&&0)&&&&&&&&&throw&new&InvalidObjectException(&Illegal&mappings&count:&&&+&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&mappings);&&&&&&&&&&&int&capacity&=&(int)&Math.min(&&&&&&&&&&&&&&&&&mappings&*&Math.min(1&/&loadFactor,&4.0f),&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&HashMap.MAXIMUM_CAPACITY);&&&&&&&&&&&if&(mappings&&&0)&{&&&&&&&&&inflateTable(capacity);&&&&&}&else&{&&&&&&&&&threshold&=&&&&&&}&&&&&&init();&&&&&&&&&&&&&for&(int&i&=&0;&i&&&&i++)&{&&&&&&&&&K&key&=&(K)&s.readObject();&&&&&&&&&V&value&=&(V)&s.readObject();&&&&&&&&&putForCreate(key,&value);&&&&&}&}&private&void&putForCreate(K&key,&V&value)&{&&&&&int&hash&=&null&==&key&?&0&:&hash(key);&&&&&int&i&=&indexFor(hash,&table.length);&&&&&&&&&&&&&&&for&(Entry&K,V&&e&=&table[i];&e&!=&null;&e&=&e.next)&{&&&&&&&&&Object&k;&&&&&&&&&if&(e.hash&==&hash&&&&&&&&&&&&&&&&((k&=&e.key)&==&key&||&(key&!=&null&&&&key.equals(k))))&{&&&&&&&&&&&&&e.value&=&&&&&&&&&&&&&&return;&&&&&&&&&}&&&&&}&&&&&&createEntry(hash,&key,&value,&i);&}&
简单来说，在序列化时，针对Entry的key与value分别单独序列化，当反序列化时，再单独处理即可。
在总结完HashMap后，发现这里面一些核心的东西，像哈希表的冲突解决，都是算法课上学到，不过由于&年代久远&，已经忘得差不多了，我觉得忘
一方面是由于时间久不用
另一方面是由于本身没理解好
平时多去思考，这样在遇到一些性能问题时也好排查。
还有一点就是我们在分析某些具体类或方法时，不要花太多时间一些细枝末节的边界条件上，这样很得不偿失，倒不是说这么边界条件不重要，程序的bug往往就是边界条件没考虑周全导致的。
只是说我们可以在理解了这个类或方法的总体思路后，再来分析这些边界条件。
如果一开始就分析，那真是丈二和尚&&摸不着头脑了，随着对它工作原理的加深，才有可能理解这些边界条件的场景。
【责任编辑： TEL：（010）】
大家都在看猜你喜欢
原创头条头条头条外电
24H热文一周话题本月最赞
讲师：1人学习过
讲师：27人学习过
讲师：0人学习过
精选博文论坛热帖下载排行
本书将实时系统、实时统一建模语言、实时系统的统一开发过程和Rational Rose RealTime建模环境有机地结合起来，以案例为基础，系统地介绍了...
订阅51CTO邮刊新浪广告共享计划>
广告共享计划
json实践--修改JSONObject&输出时，数字为null时被转换为0，解决方案，经过本人实践
本人用的jar包版本：json-lib-2.1-jdk15.jar
重点介绍 &设置jsonConfig
#########################################################################################33
//定义JsonConfigFactory 这里用到了单利模式
public class JsonConfigFactory {
private static JsonConfig instance =
public static synchronized JsonConfig getInstance() {
if (instance == null) {
System.out.println("初始化");
instance = new JsonConfig();
register(instance);
private static void register(JsonConfig jsonConfig) {
//如果double类型为null，想输出null，那就注册double.class
jsonConfig.registerJsonValueProcessor(Double.class,
new JsonValueProcessor() {
& & //这个方法不用管
public Object processArrayValue(Object value,
JsonConfig arg1) {
//修改此方法就可以
public Object processObjectValue(String key, Object
JsonConfig arg2) {
//如果vlaue为null，就返回"",不为空就返回他的值，
if (value == null) {
return "";
//地下是注册Integer类型的，详细就不说了，和上面一样，如果有其他类型，就按照此方法在注册
jsonConfig.registerJsonValueProcessor(Integer.class,
new JsonValueProcessor() {
public Object processArrayValue(Object value,
JsonConfig arg1) {
public Object processObjectValue(String key, Object
JsonConfig arg2) {
if (value == null) {
return "";
############################################################################################
List&Bean& list=
//list=service.getList();获取方法我这里不介绍，不是重点
JSONObject jsonObject = new JSONObject();
Map&String,Object& map=new
HashMap&String , Object&();
map.put("data", list);
jsonObject.putAll(map,JsonConfigFactory.getInstance());
} catch (Exception e) {
e.printStackTrace();
jsonObject.toString();就是你需要的字符串；
############################################################################################
注意：从数据库里面取值的时候，要判断下
if(rs.getString("id")!=null){
bean.setId(rs.getDouble("id"))
bean.setId(null)
rs.getDouble("id"),如果id为null的话，默认页是0
############################################################################################
以上方法是我经过实践中，一下在转载其他版本处理方法
如果未设置的话默认是DefaultDefaultValueProcessor&
public&class&DefaultDefaultValueProcessor&implements&DefaultValueProcessor&{&&
&&&public&Object&getDefaultValue(&Class&type&)&{&&
&&&&&&if(&JSONUtils.isArray(&type&)&){&&
&&&&&&&&&return&new&JSONArray();&&
&&&&&&}else&if(&JSONUtils.isNumber(&type&)&){&&
&&&&&&&&&if(&JSONUtils.isDouble(&type&)&){&&
&&&&&&&&&&&&return&new&Double(&0&);&&
&&&&&&&&&}else{&&
&&&&&&&&&&&&return&new&Integer(&0&);&&
&&&&&&&&&}&&
&&&&&&}else&if(&JSONUtils.isBoolean(&type&)&){&&
&&&&&&&&&return&Boolean.FALSE;&&
&&&&&&}else&if(&JSONUtils.isString(&type&)&){&&
&&&&&&&&&return&"";&&
&&&&&&return&JSONNull.getInstance();&&
&在jsonConfig
注册defaultValueProcessor&
//&设置Integer类型为空的默认值&json-lib默认是0&&&&&
jsonConfig.registerDefaultValueProcessor(Integer.class,&&
&&&&&&&&new&DefaultValueProcessor()&{&&
&&&&&&&&&&&&public&Object&getDefaultValue(Class&type)&{&&
&&&&&&&&&&&&&&&&return&null;&&
&&&&&&&&&&&&}&&
&&&&&&&&});&&&&
&这样转换时Integer类型如果为null转换还是null，不会被转为0
参考资料：
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。HashMap的实现与优化 - 简书
HashMap的实现与优化
HashMap的优化与实践
本文是基于作者在github上的Android 问题交流讨论坛而产生的一篇文章，也是自己早打算开坑的一篇文章。文章首先介绍了hashMap的一些基本知识，然后介绍了它在JDK8下的实现原理，最后着重介绍了几个面试中处理大数据的方法，文章比较长，我也写了好久，希望各位能够读完并发表意见。
Android 题交流讨论坛是开源达人 Trinea 在gitHub上组建的一个讨论组织，那里的提问与回答都非常靠谱。
HashMap的复杂度
如图是ArrayList/LinkedList/HashMap三个数据结构的复杂度对比，可以看出HashMap整体上性能都非常不错，但是不稳定，为O(N/Buckets)，N就是以数组中没有发生碰撞的元素，Buckets是因碰撞产生的链表。
LinkedList
O(N/Bucket_size)
O(N/Bucket_size)
O(N/Bucket_size)
注：发生碰撞实际上是非常稀少的，所以N/Bucket_size约等于1
HashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改（添加/删除）的效率非常低；Link由于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。
复杂度是如何考察的？
对于数据结构，在时间上我们需要考察Acessing ,Search, Deletion/Insertion的平均与最差的复杂度。在空间上，我们要考虑维护这个数据结构所占用的内存空间。
常见的数据结构与排序的复杂度都在
HashMap的实现
本文以JDK8的API实现进行分析
1. 什么是hash，什么是碰撞？
Hash：是一种信息摘要算法，它还叫做哈希，或者散列，但是它不是加密。我们平时使用的MD5,SHA1,SSL中的公私钥验证都属于Hash算法，通过输入key进行Hash计算，就可以获取key的HashCode()，比如我们通过校验MD5来验证文件的完整性。
碰撞：好的Hash算法可以出计算几乎出独一无二的HashCode，如果出现了重复的hashCode，就称作碰撞;
就算是MD5这样优秀的算法也会发生碰撞，即两个不同的key也有可能生成相同的MD5。
2. HashMap中是如何实现写入与读取的？
HashMap实现了Map接口，保存着K-V这样的集合。我们以put操作为例
2.1. 对key进行Hash计算
在JDK8中，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了
static final int hash(Object key) {
//计算hashCode，并无符号移动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h &&& 16);
举个例子: ^( &&& 16)
10 11 3771819)
00 01 50) XOR
--------------------------------------- =
10 10 3766277)
这样做可以实现了高地位更加均匀地混到一起，详见
下面给出几个常用的哈希码(hashCode)的算法。
Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
String类的hashCode. 根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
Integer等包装类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
int，char这样的基础类，它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。
2.2. 获取到当前的位置
计算了Hash，我们现在要把它插入数组中了
i = (tab.length - 1) & hash；
通过位运算，确定了当前的位置，因为HashMap数组的大小总是2^n，所以实际的运算就是 (0xfff...ff) & hash ，这里的tab.length-1相当于一个mask，滤掉了大于当前长度位的hash，使每个i都能插入到数组中。
2.3. 生成包装类
这个对象是一个包装类，Node&K,V&，内部有key,value,hash还有next，可以看出来它是一个链表。
static class Node&K,V& implements Map.Entry&K,V& {
//getter and setter .etc.
2.4. 插入包装类到数组
(1). 如果输入当前的位置是空的，就插进去，如图，左为插入前，右为插入后
1 - & null
2 - & null
..- & null
i - & new node
n - & null
(2). 如果当前位置已经有了node，且它们发生了碰撞，则新的放到前面，旧的放到后面，这叫做链地址法处理冲突。
1 - & null
2 - & null
..- & null
i - & new - & old
n - & null
我们可以发现，失败的hashCode算法会导致HashMap的性能由数组下降为链表，所以想要避免发生碰撞，就要提高hashCode结果的均匀性。当然，在JDK8中，采用了红黑二叉树进行了处理，这个我们后面详细介绍。
什么是Hash攻击?
通过请求大量key不同，但是hashCode相同的数据，让HashMap不断发生碰撞，硬生生的变成了SingleLinkedList
1 -& a -&b -& c -& d(撞！撞！撞！复杂度由O(1)变成了O(N))
2 -& null(本应该均匀分布，这里却是空的)
这样put/get性能就从O(1)变成了O(N)，CPU负载呈直线上升，形成了放大版DDOS的效果，这种方式就叫做hash攻击。在Java8中通过使用TreeMap，提升了处理性能，可以一定程度的防御Hash攻击。
如果当表中的75%已经被占用，即视为需要扩容了
(threshold = capacity * load factor ) & size
它主要有两个步骤：
1. 容量加倍
左移1位，就是扩大到两倍，用位运算取代了乘法运算
newCap = oldCap && 1;
newThr = oldThr && 1;
2. 遍历计算Hash
for (int j = 0; j & oldC ++j) {
//如果发现当前有Bucket
if ((e = oldTab[j]) != null) {
oldTab[j] =
//如果这里没有碰撞
if (e.next == null)
//重新计算Hash，分配位置
newTab[e.hash & (newCap - 1)] =
//这个见下面的新特性介绍，如果是树，就填入树
else if (e instanceof TreeNode)
((TreeNode&K,V&)e).split(this, newTab, j, oldCap);
//如果是链表，就保留顺序....目前就看懂这点
else { // preserve order
Node&K,V& loHead = null, loTail =
Node&K,V& hiHead = null, hiTail =
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loTail.next =
if (hiTail == null)
hiTail.next =
} while ((e = next) != null);
if (loTail != null) {
loTail.next =
newTab[j] = loH
if (hiTail != null) {
hiTail.next =
newTab[j + oldCap] = hiH
由此可以看出扩容需要遍历并重新赋值，成本非常高，所以选择一个好的初始容量非常重要。
如何提升性能？
解决扩容损失：如果知道大致需要的容量，把初始容量设置好以解决扩容损失；比如我现在有1000个数据，需要
= 1333 个坑位，又 1024 & 1333 & 2048，所以最好使用2048作为初始容量。
解决碰撞损失：使用高效的HashCode与loadFactor，这个...由于JDK8的高性能出现，这儿问题也不大了。
解决数据结构选择的错误：在大型的数据与搜索中考虑使用别的结构比如TreeMap，这个就是知识积累了。一般需要key排序时，建议使用TreeMap，本文暂不讨论；
HashMap与HashTable的主要区别
在很多的Java基础书上都已经说过了，他们的主要区别其实就是Table全局加了线程同步保护
HashTable线程更加安全，代价就是因为它粗暴的添加了同步锁，所以会有性能损失。
其实有更好的concurrentHashMap可以替代HashTable，一个是方法级，一个是Class级
JDK8中HashMap的新特性
如果某个桶中的链表记录过大的话（当前是TREEIFY_THRESHOLD = 8），就会把这个链动态变成红黑二叉树，使查询最差复杂度由O(N)变成了O(logN)。
//e 为临时变量，p为当前的链
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount &= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
JDK8在其他地方也有提升，更多的可以看。
HashMap的装箱空间效率
在笔试题中，一般“内存限制”是不考虑装箱的，而在现实中HashMap空间效率之低，你却不一定知道。
比如定义了一个 HashMap&Long,Long&
1. Long的装箱
在对象头中，加入额外的指针8Bype，加入8Bype的MarkWord(hashcode与锁信息)，这里就是16Byte
也就是说，long在装箱后，效率为 8/24 = 1/3
2. Map.Entry的装箱
字段空间: hash(4) + padding(4) ＋ next(8) = 16Byte，这里的padding是字节对齐
对象头: 16Byte，指针+MarkWord
也就是说，维护一个Entry需要32Byte的空间
static class Node&K,V& implements Map.Entry&K,V&
8/(24 + 32) = 1/7
计算结果可能有差异，本文主要在强调装箱过程造成的损失
在Android中使用SparseArray代替HashMap
官方推荐使用SparseArray([spɑ:s][?'re?],稀疏的数组)或者LongSparseArray代替HashMap，目前国内好像涉及的比较少，容我先粘贴一段
Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array.
For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-used for the same key, or compacted later in a single garbage collection step of all removed entries. This garbage collection will need to be performed at any time the array needs to be grown or the the map size or entry values are retrieved.
总的来说就是：
SparseArray使用基本类型(Primitive)中的int作为Key，不需要Pair&K,V&或者Entry&K,V&这样的包装类，节约了内存;
SpareAraay维护的是一个排序好的数组，使用二分查找数据，即O(log(N))，每次插入数据都要进行排序，同样耗时O(N)；而HashMap使用hashCode来加入/查找/删除数据，即O(N/buckets_size)；
总的来说，就是SparseArray针对Android嵌入式设备进行了优化，牺牲了微小的时间性能，换取了更大的内存优化;同时它还有别的优化，比如对删除操作做了优化；
如果你的数据非常少(实际上也是如此)，那么使用SpareArray也是不错的；
在笔试中的使用
1. 查重与分组问题
某公司正在做一个寻找走失儿童的公益项目，现在有一个函数，可以输入两个图片，并返回这个儿童是否重复。请你设计一个系统，帮助他们寻找儿童。
网友可以同时上传一批图片
系统能够把所有图片分类并归为一组
网友上传图片后，网页要尽快返回该照片所在的组。
A：假设你现在有一个机器，请写出你的数据结构与处理流程，设计的思路。B：如果你有多台机器，如果缩短请求的时间？
A：我们可以把它分解为两个部分，一个是数据结构一个是上传流程。
(1). 对于数据结构来说，一个是对儿童信息进行包装，另一个是实现儿童信息的高效查找。对于儿童信息包装类来说，除了加入儿童的图片，姓名，生日等基本信息外，特别要注意重写equals与hashCode，这个equals就是题目所说的比较函数。对于查找的实现来说，首先我们建立一个HashSet，用于存储儿童信息。网友上传后，服务器通过对图像计算出特征Hash值，并查Hash表，如果HashCode相同，则返回所在的组；如果不相同，就加入hash表，伪代码如下。
List&Set&Child&&
list.forEach(set -& {
if(!set.contain(child)){
set.add(child);
(2). 对于多图上传问题，有成熟的中间件，比如。
此问题明显是一个事件处理与分发的流程。可以通过Hash后取余进行分发，然后交给Handoff集群。
TOP10的实现
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
这个题目与上个题目类似，我们选择使用HashMap，key为查询值，val为计数，内存使用为 3
* 256 M == 768M & 1G，然后我们不断的put就可以了，伪代码
HashMap&String, Integer& map = new HashMap&String,Integer&();
//如果内存再多点的话，我们就可以把初始化容量凑个1024的整数，减少扩容损失。
while(fileLog.hasNext()){
String query = fileLog.next();
map.put(query, map.get(query) + 1);
接着使用堆排序遍历即可，堆的大小为10，复杂度为10xO(LogN)。
总复杂度为O(10^7) +10 * O(Log(3x10^6));
额外还有一种，就是使用Redis来实现TopN，即Sorted Sets，可以参考《Redis的设计与实现》，里面也讲了Hash相关，不过是用C写的。
还有一种是使用LinkedHashMap&T,Integer&作为统计工具，内部已经实现了渐进式排序，最后计算KeySet.subList(0,10)即可。
使用WeakHashMap作为缓冲
在动态代理、Spring依赖、NoSQL等耗查询时操作中，为了实现复用，使用了HashMap实现缓存，下面的一个例子是Picasso的Transformation操作
public final class PaletteTransformation implements Transformation {
private static final PaletteTransformation INSTANCE = new PaletteTransformation();
private static final Map&Bitmap, Palette& CACHE = new WeakHashMap&&();
public static PaletteTransformation instance() {
return INSTANCE;
public static Palette getPalette(Bitmap bitmap) {
return CACHE.get(bitmap);
private PaletteTransformation() {
public Bitmap transform(Bitmap source) {
Palette palette = Palette.generate(source);
CACHE.put(source, palette);
public String key() {
return "PaletteTransformation";
附录一：集合中元素的排序方式：
刚刚对比SparseArray与HashMap时，我怕各位绕进去了，这里再讲下Java中集合的排序方式
按照添加/删除的顺序，比如FIFO,FILO，常见的比如Queue,Stack就是按照这个顺序实现的；
按照Hash表进行排序，比如HashMap的table中的元素是通过hash运算随机均匀排列的（至少理论上是），可以通过计算Key的Hash值快速查找到Value
按照自定义的排序，比如按照数字大小，拼音首字母排序，常见的有线性顺序表，二叉查找树，以及高度封装好的TreeMap，它们需要实现Comaparable接口以进行进一步的自定义CompareTo操作。
附录二：hashCode， == ，equals, Comparable的区别？
== : 这个就是内存地址的比较，从C语言开始我们就知道这个了。
hashCode/equals：对于Object来说，hashCode就是地址的取样运算，而equals就是判断地址是否相同，是native方法，需要jvm实现；在实际使用中，特别是在集合(Set)中,特别是HashSet，为了防止插入的是两个相同的值，我们更注重内容上的对比而不是地址的对比，需要通过计算hashCode来判断是否equals，所以两个方法要同时重写，比如String。
Comparable: 在集合需要排序(SortSet)的情况下，就需要给对象实现Comparable接口，比如TreeMap。这个在Android开发中实际需要手动写的情况并不多，毕竟包多，在ORM框架中一般都帮你写好了。
Map在Android／Sever项目中的使用
Bundle与Parcelable，实际上就是Android中对Map与Serializable的接口实现（当然底层已经是基于ASM的IPC了）；
反射时使用WeakReference做缓存，比如Retrofit等动态代理框架；
Otto广播的底层结构是HashMap&IBinder, ReceiverList&;
在Zookeeper等框架中，使用LinkedHashMap作为NamingService的缓存。
在Redis等框架中，作为缓存结构。
按照王垠的话，JDK源码简直让人无语，特别是if((n.next=p) != null)这样的代码频频出现，说明了自己的基础不足（然并卵，现在看完后已经能写出这种WTF的代码了）。这是我第一次写分析而不是写过程，希望有问题能够提出，无论是文章排版还是技术上的问题都可以提出来。
最后打个广告我目前正在准备技术面试，所以关于Java所有的文章有个总结，不妨。
深圳HW奋斗者， bWlhbzEwMDdAZ21haWwuY29tCg==