Java集合框架之Java HashMap源码解析
继上一篇文章Java集合框架综述后，今天正式开始分析具体集合类的代码，首先以既熟悉又陌生的HashMap开始。
签名（signature）
1.public class HashMap<K,V>
3.implements Map<K,V>,Cloneable,Serializable
可以看到HashMap继承了
∙标记接口Cloneable，用于表明HashMap对象会重写
java.lang.Object#clone()方法，HashMap实现的是浅拷贝（shallow
copy）。
∙标记接口Serializable，用于表明HashMap对象可以被序列化
比较有意思的是，HashMap同时继承了抽象类AbstractMap与接口Map，因为抽象类AbstractMap的签名为
1.public abstract class AbstractMap<K,V>implements Ma
resizedp<K,V>
Stack Overfloooow上解释到：
在语法层面继承接口Map是多余的，这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的，起到了文档的作用
AbstractMap相当于个辅助类，Map的一些操作这里面已经提供了默认实现，后面具体的子类如果没有特殊行为，可直接使用AbstractMap提供的实现。Cloneable接口
1.<code>It's evil,don't use it.</code>
Cloneable这个接口设计的非常不好，最致命的一点是它里面竟然没有clone方法，也就是说我们自己写的类完全可以实现这个接口的同时不重写clone方法。关于Cloneable的不足，大家可以去看看《Effective Java》一书的作者给出的理由，在所给链接的文章里，Josh Bloch也会讲如何实现深拷贝比较好，我这
里就不在赘述了。
Map接口
在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抽象类
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是一种基于哈希表（hash table）实现的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时，会进行resiz
e，reside会导致key进行rehash）设置的过低。
∙由于HashMap是线程非安全的，这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变（添加、删除entry，只改
变entry的value的值不算结构改变），那么会报
ConcurrentModificationException，专业术语叫fail-fast，尽早报错
对于多线程程序来说是很有必要的。
∙Map m=Collections.synchronizedMap(new HashMap(...))；通过这种方式可以得到一个线程安全的map。
源码剖析
首先从构造函数开始讲，HashMap遵循集合框架的约束，提供了一个参数为空的构造函数与有一个参数且参数类型为Map的构造函数。除此之外，还提供了两个构造函数，用于设置HashMap的容量（capacity）与平衡因子（loadFactor）。
1.public HashMap(int initialCapacity,float loadFactor)
{
2.if(initialCapacity<0)
3.throw new IllegalArgumentException("Illegal
initial capacity:"+
4.initialCa
pacity);
5.if(initialCapacity>MAXIMUM_CAPACITY)
6.initialCapacity=MAXIMUM_CAPACITY;
7.if(loadFactor<=0||Float.isNaN(loadFactor))
8.throw new IllegalArgumentException("Illegal
load factor:"+
9.loadFacto
r);
10.this.loadFactor=loadFactor;
11.threshold=initialCapacity;
12.init();
13.}
14.public HashMap(int initialCapacity){
15.this(initialCapacity,DEFAULT_LOAD_FACTOR);
16.}
17.public HashMap(){
18.this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FAC
TOR);
19.}
20.
21.从代码上可以看到，容量与平衡因子都有个默认值，并且容量有个最大
值
22.
23./**
24.*The default initial capacity-MUST be a power of two.
25.*/
26.static final int DEFAULT_INITIAL_CAPACITY=1<<4;
//aka16
27./**
28.*The maximum capacity,used if a higher value is implicitly spec
ified
29.*by either of the constructors with arguments.
30.*MUST be a power of two<=1<<30.
31.*/
32.static final int MAXIMUM_CAPACITY=1<<30;
33./**
34.*The load factor used when none specified in constructor.
35.*/
36.static final float DEFAULT_LOAD_FACTOR=0.75f;
可以看到，默认的平衡因子为0.75，这是权衡了时间复杂度与空间复杂度之后的最好取值（JDK说是最好的），过高的因子会降低存储空间但是查（lookup，包括HashMap中的put与get方法）的时间就会增加。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。