Java集合系列之HashMap源码分析-创新互联

前面我们已经分析了ArrayList和LinkedList这两个集合，我们知道ArrayList是基于数组实现的，LinkedList是基于链表实现的。它们各自有自己的优劣势，例如ArrayList在定位查找元素时会优于LinkedList，而LinkedList在添加删除元素时会优于ArrayList。而本篇介绍的HashMap综合了二者的优势，它的底层是基于哈希表实现的，如果不考虑哈希冲突的话，HashMap在增删改查操作上的时间复杂度都能够达到惊人的O(1)。我们先看看它所基于的哈希表的结构。

从上图中可以看到，哈希表是由数组和链表共同构成的一种结构，当然上图是一个不好的示例，一个好的哈希函数应该要尽量平均元素在数组中的分布，减少哈希冲突从而减小链表的长度。链表的长度越长，意味着在查找时需要遍历的结点越多，哈希表的性能也就越差。接下来我们来看下HashMap的部分成员变量。

//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默认大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认加载因子, 指哈希表可以达到多满的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};

//实际使用的哈希表
transient Entry[] table = (Entry[]) EMPTY_TABLE;

//HashMap大小, 即HashMap存储的键值对数量
transient int size;

//键值对的阈值, 用于判断是否需要扩增哈希表容量
int threshold;

//加载因子
final float loadFactor;

//修改次数, 用于fail-fast机制
transient int modCount;

//使用替代哈希的默认阀值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//随机的哈希种子, 有助于减少哈希碰撞的次数
transient int hashSeed = 0;