HashMap的重要性就不多说了，经常用到，面试也很喜欢问，所以有必要研究下。
HashMap结构1.png
当调用put方法往HashMap存入数据时，HashMap的数据分布可能如下，需要注意的是，数组里面装的元素是一个节点，Node类型或者TreeNode型；这种类型包装了我们传进来的键值对key ---> value：
HashMap结构2.png
可以看到，这些数据不一定是连续的；那么这些数据是怎么确定放在数组的哪个桶的呢？这就要借助于hash算法了，当一个数据要存入HashMap时，拿键的hash值与数组长度 - 1做与运算，即：
(n - 1) & hash
其中n是数组长度，hash是key的hash。
当存入的数据很多时，每个key之间的hash值可能就一样了，不同的key也可能产生不同的hash值；如果hash值一样的话，那么根据上面的公式，桶的位置也就一样了；一个桶装多个数据，怎么办？
HashMap结构3.png
如上图所示，如果E的hash和X的hash值相等，那么就发生了hash冲突，这时候把X连在E的后面；对于一个HashMap来说，碰撞发生的越少，查找效率就越高；因为碰撞太多的话，这个链表就越长(或者红黑树越高)，这样在get数据的时候就需要遍历链表或者红黑树，这样就降低了效率；总之，数据分布越均匀，查找效率越高。
当链表的长度过长时，HashMap就会把链表转换成红黑树：
HashMap结构4.png
链表转换成红黑树的过程叫做树化(下篇文章会分析)；当链表的节点快速增加时，会造成搜索效率的降低，而红黑树能够解决搜索效率问题，所以树化就出现了。
废话不多说，直接上源码，先看类信息和构造函数：
//继承自AbstractMap，实现了Map、Cloneable和Serializable接口
//AbstractMap是一个实现了Map接口的抽象类，他对Map接口进行了有限
//的扩展，同时实现了部分接口方法，比如size()、clear()、hashCode()等
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* The default initial capacity - MUST be a power of two.
*/
//HashMap的默认初始化容量16，这个容量比如是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
//HashMap的最大容量，2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
//HashMap的默认加载因子，加载因子的作用是判断是不是需要扩容了
//比如初始容量是16，加载因子是0.75，16 * 0.75 = 12，也就是说
//当HashMap里面的元素个数达到12个的时候就需要对HashMap进行扩容了
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
//当链表中的节点达到8个时，就将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
//当红黑树的节点数量小于等于6时，将红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
//链表转换成树的必要条件之一，除了上面的阈值判断之外，还会判断HashMap的容量
//只有容量大于64的时候，才会转换；小于这个值时，HashMap宁愿选择扩容，而不是
//树化建立初期，多个键值对放入同一个链表中而导致不必要的转换
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//注释比较简单，自己看。HashMap里面的数据首先是存放在数组里面
//的长度不够的时候，我们可以扩容，这个容量都是2的n次幂，transient
//代表该变量无法被序列化(HashMap本身是实现了序列化接口的)
transient Node<K,V>[] table;
/**
* The number of key-value mappings contained in this map.
*/
//size代表该Map里面键值对的个数，其实就是HashMap的元素个数
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//扩容阈值，当HashMap里面的元素个数达到这个值的时候就必须
//扩容了，这个值是由容量*加载因子确定的，默认的加载因子是0.75
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
//加载因子
final float loadFactor;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
//构造函数，开发中直接调用这个构造函数的比较少，这个构造函数指定了默认
//容量和加载因子
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 = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
//只指定默认容量的构造函数，加载因子还是用默认的0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
//这种构造函数用的最多，什么都是默认的
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
//根据一个Map构造一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
网友评论