转载

Java集合框架分析(四)HashMap分析

本篇文章主要分析一下Java集合框架中的Map部分，HashMap，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请见谅！

HashMap简介

基于哈希表的一个 Map 接口实现，存储的对象是一个键值对对象 (Entry<K,V>)；值得注意的是 HashMap 不是线程安全的，如果想要线程安全的 HashMap，可以通过 Collections 类的静态方法 synchronizedMap 获得线程安全的 HashMap。

Map map = Collections.synchronizedMap(new HashMap());
复制代码

数据结构

Java 最基本的数据结构有数组和链表。数组的特点是空间连续（大小固定）、寻址迅速，但是插入和删除时需要移动元素，所以查询快，增加删除慢。链表恰好相反，可动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找，所以增加删除快，查找慢。有没有一种结构综合了数组和链表的优点呢？当然有，那就是哈希表（虽说是综合优点，但实际上查找肯定没有数组快，插入删除没有链表快，一种折中的方式吧），所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap 的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap 中主要是通过 key 的 hashCode 来计算 hash 值的，只要 hashCode 相同，计算出来的 hash 值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的 hash 值是相同的，这就出现了所谓的 hash 冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap 底层是通过链表来解决 hash 冲突的。图中，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的 key 映射到了数组的同一位置处，就将其放入单链表中。

内部接口

内部接口 EntryEntry 接口是 Map 定义的一个内部接口

interface Entry<K, V> {
	K getKey();
	V getValue();
	V setValue(V value);
	boolean equals(Object o);
	int hashCode();
	public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
		return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getKey().compareTo(c2.getKey());
	}
	public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
		return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getValue().compareTo(c2.getValue());
	}
	public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
		Objects.requireNonNull(cmp);
		return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
	}
	public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
		Objects.requireNonNull(cmp);
		return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
	}
}
复制代码

对于 HashMap，它的内部里面实现一个静态内部类，即为 HashMapEntry<K,V> ，其重要的属性有 key , value, next，从属性 key,value 我们就能很明显的看出来 HashMapEntry 就是 HashMap 键值对实现的一个基础 bean，我们上面说到 HashMap 的基础就是一个线性数组，这个数组就是 HashMapEntry[]，Map 里面的内容都保存在 HashMapEntry[] 里面。

transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
复制代码

我们可以来简单分析一下这个静态内部类 HashMapEntry.java

// HashMapEntry.java静态内部类，实现的HashMap线性数组   
static class HashMapEntry<K, V> implements Map.Entry<K, V> {
	// key,value值
	final K key;
	V value;
	// 每个数组里面包含的链表
	HashMapEntry<K, V> next;
	int hash;
	/** * 构造函数 * 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" */
	HashMapEntry(int h, K k, V v, HashMapEntry<K, V> n) {
		value = v;
		next = n;
		key = k;
		hash = h;
	}
	public final K getKey() {
		return key;
	}
	public final V getValue() {
		return value;
	}
	public final V setValue(V newValue) {
		V oldValue = value;
		value = newValue;
		return oldValue;
	}
	/**
	 * * 判断两个Entry是否相等 * 若两个Entry的“key”和“value”都相等，则返回true。 * 否则，返回false
	 */
	public final boolean equals(Object o) {
		if (!(o instanceof Map.Entry))
			return false;
		Map.Entry e = (Map.Entry) o;
		Object k1 = getKey();
		Object k2 = e.getKey();
		if (k1 == k2 || (k1 != null && k1.equals(k2))) {
			Object v1 = getValue();
			Object v2 = e.getValue();
			if (v1 == v2 || (v1 != null && v1.equals(v2)))
				return true;
		}
		return false;
	}
	public final int hashCode() {
		return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
	}
	public final String toString() {
		return getKey() + "=" + getValue();
	}
	/**
	 * * 当向HashMap中添加元素时，会调用recordAccess()
	 */
	void recordAccess(HashMap<K, V> m) {
	}
	/**
	 * * 当从HashMap中删除元素时，会调用recordRemoval()。
	 */
	void recordRemoval(HashMap<K, V> m) {
	}
}
复制代码

HashMap 其实就是一个 HashMapEntry 数组，HashMapEntry 对象中包含了键和值，其中 next 也是一个 HashMapEntry 对象，它就是用来处理 hash 冲突的，形成一个链表。基本结构我们已经分析了，接下来我们就开始正题，开始分析 HashMap 的源码实现啦！

源码分析

类申明

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
复制代码

首先我们来看看 HashMap 内部申明的一些属性，

//属性申明	
//默认的初始容量，必须是2的幂次方。    
static final int DEFAULT_INITIAL_CAPACITY = 4;    
//最大容量，默认为2的30次方，    
static final int MAXIMUM_CAPACITY = 1 << 30;    
//加载因子    
static final float DEFAULT_LOAD_FACTOR = 0.75f;    
//    
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};    
//数组表，大小可以改变，且大小必须为2的幂    
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;    
//当前Map中key-value映射的个数    
transient int size;    
//当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量    
int threshold;    
//加载因子    
final float loadFactor = DEFAULT_LOAD_FACTOR;    
//Hash表结构性修改次数    
transient int modCount;
复制代码

对于加载因子 loadFactor，我们可以稍作解释：

loadFactor 加载因子是表示 Hsah 表中元素的填满的程度.

若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）冲突的机会越大,则查找的成本越高.因此,必须在“冲突的机会”与”空间利用率”之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的”时-空”矛盾的平衡与折衷.

如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值 0.75 就好了。以上一些基本属性是在 HashMap 中申明的，如果不明白什么意思的话，可以等到后面再来看看。我们接着分析下面的代码。

构造函数

接着我们来分析分析 HashMap 的构造函数

/**     
 * * 设置初始容量大小以及加载因子     
 * *     
 * * @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) {
	//初始容量大小在[DEFAULT_INITIAL_CAPACITY,MAXIMUM_CAPACITY]之间        
	if (initialCapacity < 0)           
		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY) {
		initialCapacity = MAXIMUM_CAPACITY;       
		} 
	else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) { 
		initialCapacity = DEFAULT_INITIAL_CAPACITY;       
		}       
	if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
		throw new IllegalArgumentException("Illegal load factor: " +   
    loadFactor);               
	threshold = initialCapacity; 
	init();   
	}    
/** 
 *     
 *     * 设置初始容量，加载因子为默认的0.75     
 *     * @param  initialCapacity the initial capacity.     
 *     * @throws IllegalArgumentException if the initial capacity is negative.     
 *     */    
public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);    
	}   
/** 
 *     * 使用默认的容量大小和加载因子     
 *     */   
public HashMap() { 
	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);    
	}    
/** 
 *     * 根据指定的map生成一个新的HashMap,负载因子使用默认值，
 *     初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)     
 *     *     
 *     * @param   m the map whose mappings are to be placed in this map     
 *     * @throws  NullPointerException if the specified map is null    
 *      */    
public HashMap(Map<? extends K, ? extends V> m) {  
	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);		
	//初始化HashMapEntry数组        
	inflateTable(threshold);       
	putAllForCreate(m);    
	}
}
复制代码

通过以上 HashMap 的四种构造函数我们可以发现，我们可以通过设置初始容量大小和加载因子或者直接通过一个 map 来构造一个 HashMap，其中初始容量大小我们设定为 4，它必须是 2 的幂次方，同时它的范围在 4 和 2 的 30 次方之间。构造函数比较简单，没什么可以分析的，接下来我们着重分析一下 HashMap 的添加和获取方法，也就是 put 和 get 方法。

存储数据PUT

//向map存入一个键值对，如果key已存在，则覆盖
public V put(K key, V value) {
	//如果HashMapEntry数组为空，则重新初始化一下        
	if (table == EMPTY_TABLE) {
		inflateTable(threshold);        
		}		
	//对key为null的键值对调用putForNullKey处理
	if (key == null)            
		return putForNullKey(value);
	//生成hash值        
	int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
	//生成hash值索引        
	int i = indexFor(hash, table.length);
	//循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出,同时返回旧的value！        
	for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
		Object k;			
		//如果找到了相同的key，则覆盖旧的value
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
			V oldValue = e.value;                
			e.value = value;                
			//调用HashMapEntry增加这个Entry                
			e.recordAccess(this);                
			return oldValue;            
			}        
		}				
	//修改次数        
	modCount++;        
	//将key-value添加到table[i]处，也就是在链表的头部插入一个数据<k,v>        
	addEntry(hash, key, value, i);        
	return null;    
	}
}
复制代码

以上的大概内容就是，先获取 key 的 hash 值，然后根据 hash 值来获取在数组中的位置，判断在 table[i] 中是否存在这个 key，也就是先循环遍历链表，如果找到这个 key 的值，那么就替换这个 key 值，然后将 value 修改进去，如果在链表中找不到这个 key 的话，那么就在链表的头部插入一个数据。在 put 方法中，我们来详细分析其中的一些方法。开头有一个判断数组是否为 null 的操作

//如果HashMapEntry数组为空，则重新初始化一下        
if (table == EMPTY_TABLE) {
	inflateTable(threshold);
	}	
/**
 *      
 *      * 初始化这个数组     
 *      */    
private void inflateTable(int toSize) { 
	// 寻找大于toSize的2的幂次方的最小值        
	int capacity = roundUpToPowerOf2(toSize);
	float thresholdFloat = capacity * loadFactor;       
	if (thresholdFloat > MAXIMUM_CAPACITY + 1) { 
		thresholdFloat = MAXIMUM_CAPACITY + 1;        
		}				
	//初始化数组        
	threshold = (int) thresholdFloat;
	table = new HashMapEntry[capacity];    
	}
}
复制代码

接下来，判断了 key 是否为 null，如果为 null 的话，则进行 putForNullKey(V value) 操作

/**     
 * * 插入key为null的值，在数组的第一个位置进行插入操作     
 * */    
private V putForNullKey(V value) {
	//循环遍历数组第一个数组的链表，如果存在null的则进行覆盖更新操作        
	for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
		if (e.key == null) {                
			V oldValue = e.value; 
			e.value = value;                
			e.recordAccess(this);                
			return oldValue;            
			}        
		}        
	//修改次数        
	modCount++;        
	//链表中不存在key为null的值，则在链表的开头插入这个key为null的值        
	addEntry(0, null, value, 0);       
	return null;    
	}
}
复制代码

如果 key 为 null 的话，hash 值为 0，对象存储在数组中索引为 0 的位置。即 table[0]，接着我们分析一下 addEntry 方法，

//通过hash值来算出在table中哪个位置，然后进行插入操作
void addEntry(int hash, K key, V value, int bucketIndex) {
	//        
	if ((size >= threshold) && (null != table[bucketIndex])) {
		//数组扩容            
		resize(2 * table.length);            
		//如果key为null的话，那么hash值为0，也就是在数组的第一个位置，即table[0]位置            
		hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;            
		//根据hash的值来算出在数组的中位置            
		bucketIndex = indexFor(hash, table.length);        
	}		
	//数据插入或者更新操作        
	createEntry(hash, key, value, bucketIndex);    
}
复制代码

我们通过 hash 值计算得到了 table 下表中的值，接着继续分析 createEntry 方法

//数据操作，在链表头部插入一个数组，这就是在一个链表头部插入一个节点的过程。获取table[i]的对象e，将table[i]的对象修改为新增对象，让新增对象的next指向e。
void createEntry(int hash, K key, V value, int bucketIndex) {
	//保存table[i]的对象为e        
	HashMapEntry<K,V> e = table[bucketIndex];        
	//然后将table[i]的值修改为新增的对象，并将新增对象的next值设置为原先table[i]的值e,这就相当于在链表头部插入一个数据了。        
	table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);        
	size++;   
	}
}
复制代码

分析完了 key 为 null 的情况，接着我们分析一下 key 不等于 null 的情况。接着，我们通过 key来计算出 hash 的，然后根据 hash 的值来计算在 table 数组中的位置 int i = indexFor(hash, table.length);

//  indexFor返回hash值和table数组长度减1的与运算结果。为什么使用的是length-1？应为这样可以保证结果的最大值是length-1，不会产生数组越界问题。
static int indexFor(int h, int length) {
	return h & (length-1);   
}
复制代码

我们找到了在数组 table 中的位置后，我们就开始遍历当前位置中的链表了，如果存在 key 则覆盖操作，不存在的话则在链表头部插入一个数据。上面便是一个完整的增加数据的操作，在这里我们进行概括一下中心思想。首先，我们判断我们需要增加数据的 key 是否为 null，如果为 null 的话，则在数组的第一个位置即 table[0] 处进行插入或者更新操作（如果在第一个位置处的链表中存在 key 未 null 的数据，那么则进行覆盖更新操作，如果不存在的话，则在链表头插入一个数据，就是常见的链表插入操作），接下来就走 key 不等于 null 这一步了，我们需要根据 key 来计算出 hash 的值，其次，需要根据 hash 的值来计算在 table 中的位置，得到了位置之后，我们重复进行在链表中的操作（找到就覆盖更新，没找到就在链表头部插入一个数据），这就是 HashMap 的 put 操作。

我们一般对哈希表的散列很自然地会想到用 hash 值对 length 取模（即除法散列法）， Hashtable 中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap 中则通过 h&(length-1) 的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是 HashMap 对 Hashtable 的一个改进。 接下来，我们分析下为什么哈希表的容量一定要是 2 的整数次幂。首先，length 为 2 的整数次幂的话，h&(length-1) 就相当于对 length 取模，这样便保证了散列的均匀，同时也提升了效率；其次，length 为 2 的整数次幂的话，为偶数，这样 length-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(length-1) 的最后一位可能为 0，也可能为 1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 h&(length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length 取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。分析完了 put 方法，接下来我们分析一下 putAll 方法，

/**     
 * * @param m mappings to be stored in this map     
 * * @throws NullPointerException if the specified map is null     
 * */    
public void putAll(Map<? extends K, ? extends V> m) { 
	int numKeysToBeAdded = m.size();        
	if (numKeysToBeAdded == 0)            
		return;        
	if (table == EMPTY_TABLE) {
		inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));        
		}        /*         */        
	if (numKeysToBeAdded > threshold) {  
		int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);          
		if (targetCapacity > MAXIMUM_CAPACITY)                
			targetCapacity = MAXIMUM_CAPACITY;            
		int newCapacity = table.length;           
		while (newCapacity < targetCapacity)               
			newCapacity <<= 1;           
		if (newCapacity > table.length)                
			resize(newCapacity);        
		}		
	//遍历m中的内容，然后调用put方法将元素添加到table数组中        
	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())            
		put(e.getKey(), e.getValue());   
	}
}
复制代码

遍历的时候涉及到了 entrySet 方法，这个方法定义在 Map 接口中，HashMap 中也有实现。我们在 HashMap 构造函数有个方法叫 putAllForCreate 方法，分析一下内容。

private void putAllForCreate(Map<? extends K, ? extends V> m) {        
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())                            
    	putForCreate(e.getKey(), e.getValue());    
}
复制代码

看这个方法名就知道大概意思，在 HashMap 初始化的时候将一个 map 全部赋值给初始值。代码也是，先遍历一下 Map，然后依次添加进去，我们进入 putForCreate 方法中查看具体源码

private void putForCreate(K key, V value) {
	//获取key的hash值        
	int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);        
	//根据hash值来计算在table中的位置        
	int i = indexFor(hash, table.length);        
	//循环遍历数组下标为i的链表，如果存在则覆盖更新，也就是上面计算出来的table中的位置        
	for (HashMapEntry<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 = value;                
			return;            
			}       
		}		
	//当前数组中的位置链表中不存在，则在链表头部插入一条数据        
	createEntry(hash, key, value, i);    
	}
}
复制代码

该方法先计算需要添加的元素的 hash 值和在 table 数组中的索引 i。接着遍历 table[i] 的链表，若有元素的 key 值与传入 key 值相等，则替换 value，结束方法。若不存在 key 值相同的元素，则调用 createEntry 创建并添加元素。继续进入 createEntry 方法中查看源码

void createEntry(int hash, K key, V value, int bucketIndex) {
	HashMapEntry<K,V> e = table[bucketIndex];        
	table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);        
	size++;   
}
复制代码

该方法比较简单，就是在链表头部插入一条数据，putAllForCreate 方法类似于 put 方法。至此所有 put 相关操作都解释完毕了。put 之外，另一个常用的操作就是 get，下面就来看 get 方法。

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();   
}
复制代码

首先判断 key 是否等于 null，等于的话那就从 getForNullKey() 中获取 value，如果不等于的话，通过 getEntry 获取。我们首先看等于 null 的情况。

private V getForNullKey() {
	if (size == 0) {
		return null;        
	}        
	for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
		if (e.key == null)                
			return e.value;        
		}        
	return null;    
}
复制代码

如果当前 table 的大小为 0 的话，那么将返回 null，如果不为空的话，那么则在数组 table[0] 中的链表进行循环匹配，寻找 key 的 null 的链表节点，如果找到的话，则直接返回 value，否则的话返回 null，很简单。接着我们分析 key 不等于 null 的情况，即进入 getEntry 方法中分析。

final Entry<K,V> getEntry(Object key) {
	if (size == 0) {
		return null;        
	}        
	int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);        
	for (HashMapEntry<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 方法，所以这里面的代码基本类似，很简单了，首先先获取 hash 值，然后根据 hash 值获取在 table 中的索引 table[i]，其次根据这个数组中的位置来循环遍历 table[i] 中的链表，判断是否存在这个 entry 如果存在的话则返回 value，不存在则返回 null。以上便是HashMap 中比较重要的两个方法，一个 put，一个 get，我们已经全部分析完了，接着我们分析一下其余剩下来的方法。

remove方法

分析完了 put、get 方法，接着分析一下 remove 方法。

public V remove(Object key) {
	Entry<K,V> e = removeEntryForKey(key);        
	return (e == null ? null : e.getValue());    
}
复制代码

在 remove 方法中，调用了一个 removeEntryForKey 方法，我们接着看看，

final Entry<K,V> removeEntryForKey(Object key) {
	//如果数组为空，直接返回null        
	if (size == 0) { 
		return null;        
	}        
	//获取需要移除的key的hash值        
	int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);        
	//获取在数组table[i]中的索引值i        
	int i = indexFor(hash, table.length);        
	//保存当前数组中的第一个链表节点        
	HashMapEntry<K,V> prev = table[i];        
	HashMapEntry<K,V> e = prev;        
	while (e != null) {            
		HashMapEntry<K,V> next = e.next;            
		Object k;            
		if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
			modCount++;                
			size--;                
			if (prev == e)                   
				table[i] = next;                
			else                    
				prev.next = next;                
			e.recordRemoval(this);                
			return e;            
			}            
		//单链表删除操作            
		prev = e;            
		e = next;        
		}        
	return e;    
	}
}
复制代码

上面的这个过程就是先找到 table 数组中对应的索引，接着就类似于一般的链表的删除操作，而且是单向链表删除节点，很简单。在 C 语言中就是修改指针，这个例子中就是将要删除节点的前一节点的 next 指向删除被删除节点的 next 即可。

其余方法

以上分析了 HashMap 的大部分代码，还有一些比较不重要的方法我们一次性给出解释，就不一一做分析了。

清空map

/**     
 * * 清空map     
 * */    
public void clear() {
	modCount++;        
	Arrays.fill(table, null); 
	size = 0;   
	} 
复制代码

**判断是否存在指定的value **

/**     
 * * 判断是否存在指定的value     
 * *     
 * * @param value value whose presence in this map is to be tested     
 * * @return <tt>true</tt> if this map maps one or more keys to the     
 * *         specified value     
 * */    
public boolean containsValue(Object value) {
	if (value == null)            
		return containsNullValue();        
	HashMapEntry[] tab = table;        
	for (int i = 0; i < tab.length ; i++)            
		for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
			if (value.equals(e.value))                    
				return true;        
	return false;    
}  
复制代码

循环遍历数组，判断数组table[i]下面的链表是否存在value等于null的节点

/**     
 * * 循环遍历数组，判断数组table[i]下面的链表是否存在value等于null的节点     
 * */    
private boolean containsNullValue() {
	HashMapEntry[] tab = table;        
	for (int i = 0; i < tab.length ; i++)           
		for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
			if (e.value == null)                    
				return true;        
	return false;    
}    

复制代码

**针对HashMap的浅复制 **

/**    
 *  * 针对HashMap的浅复制     
 *  *     
 *  * @return a shallow copy of this map     
 *  */    
public Object clone() {
	HashMap<K,V> result = null;        
	try {            
		result = (HashMap<K,V>)super.clone();        
		} 
	catch (CloneNotSupportedException e) { 
		// assert false;        
		}       
	if (result.table != EMPTY_TABLE) { 
		result.inflateTable(Math.min(  (int) Math.min( size * Math.min(1 / loadFactor, 4.0f), 
				// we have limits...                    
				HashMap.MAXIMUM_CAPACITY),              
				table.length));        
		}        result.entrySet = null;
		result.modCount = 0;        
		result.size = 0;        
		result.init();       
		result.putAllForCreate(this);
		return result;    
		}
	}
}
复制代码

以上便是 HashMap 大概的源码，其中还涉及到 entrySet 的概念，这是其他集合框架也涉及到的，所以打算一起说，本篇暂未说明。敬请期待后面的文章。如有错误，恳请指正，谢谢！最后我们来简单写个测试，来学习一下 HashMap 的常用法。

package MapDemo;
import java.util.HashMap;
import java.util.Map;
public class HashMapTest {
	public static void main(String[] args) {
		
		Map<String, String> mHashMap=new HashMap<String,String>();
		mHashMap.put("A", "AAAAAAAA...");
		mHashMap.put("B", "BBBBBBBB...");
		mHashMap.put("C", "CCCCCCCC...");
		mHashMap.put("D", "DDDDDDDD...");
		mHashMap.put("E", "EEEEEEEE...");
		mHashMap.put("F", "FFFFFFFF...");
		mHashMap.put("G", "GGGGGGGG...");
		mHashMap.put("H", "HHHHHHHH...");
		mHashMap.put("I", "IIIIIIII...");
		
		//打印HashMap
		System.out.println("mHashMap: "+mHashMap);
		
		//打印HashMap的size
		System.out.println("mHashMap size is: "+mHashMap.size());
		
		//判断HashMap中是否存在A的key，结果为TRUE
		System.out.println("mHashMap is containsKey of A:"+ mHashMap.containsKey("A"));
		
		//判断HashMap中是否存在IIIIIIII的value,结果为FALSE
		System.out.println("mHashMap is containsValue of IIIIIIII:"+ mHashMap.containsValue("IIIIIIII"));
		
		//打印HashMap中的key
		System.out.print("the key of mHashMap is :");
		for (String string : mHashMap.keySet()) {
			System.out.print("   "+string);
		}
		System.out.println();
		
		//打印HashMap中的value
		System.out.print("the value of mHashMap is :");
		for (String string : mHashMap.values()) {
			System.out.print("   "+string);
		}
		System.out.println();
		//打印key-value集合
		System.out.println("key-value集合:");
		for (Map.Entry<String, String> entry : mHashMap.entrySet()) {
			System.out.println("key: "+entry.getKey()+" value: "+entry.getValue());
		}
	}
}
复制代码

输出结果

mHashMap: {A=AAAAAAAA..., B=BBBBBBBB..., C=CCCCCCCC..., D=DDDDDDDD..., E=EEEEEEEE..., F=FFFFFFFF..., G=GGGGGGGG..., H=HHHHHHHH..., I=IIIIIIII...}
mHashMap size is: 9
mHashMap is containsKey of A:true
mHashMap is containsValue of IIIIIIII:false
the key of mHashMap is :   A   B   C   D   E   F   G   H   I
the value of mHashMap is :   AAAAAAAA...   BBBBBBBB...   CCCCCCCC...   DDDDDDDD...   EEEEEEEE...   FFFFFFFF...   GGGGGGGG...   HHHHHHHH...   IIIIIIII...
key-value集合:
key: A value: AAAAAAAA...
key: B value: BBBBBBBB...
key: C value: CCCCCCCC...
key: D value: DDDDDDDD...
key: E value: EEEEEEEE...
key: F value: FFFFFFFF...
key: G value: GGGGGGGG...
key: H value: HHHHHHHH...
key: I value: IIIIIIII...
复制代码

关于作者

专注于 Android 开发多年，喜欢写 blog 记录总结学习经验，blog 同步更新于本人的公众号，欢迎大家关注，一起交流学习～

Java集合框架分析(四)HashMap分析
原文  https://juejin.im/post/5dbad16bf265da4cfb512701
正文到此结束
所属分类： 编程技术 Java

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 springcloud-demo Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 如何将Spring Cloud Task发布Data Flow上执行？
  2. 2 Spring Cloud Data Flow快速入门Demo
  3. 3 Spring Cloud Consul实现选举机制
  4. 4 Spring Boot集成ShedLock实现分布式定时任务
  5. 5 利用oss进行数据库和网站图片备份
  6. 6 Spring Cloud Stream实现数据流处理
  7. 7 Python3访问MySQL数据库快速入门Demo
  8. 8 Github开源项目作者可以免费申请 JetBrains 全家桶
  9. 9 Spring Cloud Vault快速入门Demo
  10. 10 Spring Cloud Gateway快速入门Demo
网站信息
  • 文章总数：82,716 篇
  • 文件总数：284,297 个
  • 标签总数：2,396 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：607 人
  • 运行天数：4,411天
  • 最后更新：2024年11月24日07点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG