参考:
https://juejin.im/post/5b5bf507f265da0fa42ce89e
好吧，这应该算java源码
内部存储结构示意图.png
不考虑红黑树扩容示意图.png
要点总结
1.HashMap内部数据元素(Map.Entry<key,value>)的存储采用的是数组+链表+红黑树(JDK8新增)的形式存储的,并且存储顺序是无序的,如图一所示,数组上每个节点所存在的元素的个数是不一定的；实现 Map<K,V>, Cloneable, Serializabl接口;
2.所谓的"哈希碰撞"，在从图一存储上看，便是数组上的同一位置挂载多个元素，如索引0发生了2次哈希碰撞,索引3发生了1次哈希碰撞；
3.计算元素存放索引的公式为(n-1)&hash,其中n为当前哈希同table的容量，hash为元素key经过特定的哈希运算方法获取的,计算过程可以从图二上看出；
4.HashMap是非线程安全的，多线程访问的情况下可能导致数据不一致；允许key为null，value为null的情况;
5.在JDK8(即JDK1.8)中当链表的长度达到8后，便会转换为红黑树用于提高查询、插入效率；
6.哈希表在满足扩容条件时，都是翻倍扩容的，但是每次扩容要重新计算每个元素的位置，数量大的话相对耗资源，所以使用的使用可以估计数量大小，先赋予初始容量，避免频繁扩容；
7.负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
8.JDK8引入红黑树、并且部分地方的计算替换为位运算取代原本的%运算，提高了效率
要点解释
源码分析
构造函数
HashMap提供4种构造函数：
//1.最常用的构造函数
HashMap<String,String> map=new HashMap<String,String>() ;
//2.指定初始容量的构造函数
HashMap<String,String> map2=new HashMap<String,String>(16) ;
//3.指定初始容量和负载因子的构造函数
HashMap<String,String> map3=new HashMap<String,String>(16,0.5f) ;
//4.通过一个已存在的Map进行内容赋值的构造函数
HashMap<String,String> map4=new HashMap<String,String>(new HashMap<String,String>()) ;
下面为源码的构造函数相关源码：
复制代码
/**
/** HashMap中实际存放的元素个数,HashMap.size()返回的就是该size
* The number of key-value mappings contained in this map.
*/
transient int size;
/** 注解意思为:默认初始哈希表容量为16，容量一定必须是2的倍数
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 注解意思为:哈希表最大容量不得超过1<<30 即2^30=1073741824
* 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.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 注解意思为：当构造方法没指定负载因子时，默认负载因子为0.75f
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 实际的负载因子，未指定时默认为DEFAULT_LOAD_FACTOR 0.75f
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/* **重要！重要！重要！**
***哈希表内元素数量的阈值，当表内数量超过这个值时，哈希表会发生自动扩容操作resize();**
*阈值的计算方式=capacity * load factor,即:哈希表容量capacity*负载因子capacity
* 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.)
int threshold;
/** **重要！重要！重要！ 注意是数组,**
*哈希桶，**链表结构**，table存放的当前哈希表的内容，哈希表内容数据存储实际上是以链表的形式存储的；
*在第一次使用的时候进行初始化，并且在需要的时候进行resize()扩容操作;
*使用时大小一直为2^n或者0;
* 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.)
*/
transient Node<K,V>[] table;
构造方法一：
* 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) {
//初始容量不允许小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //初始容量限制为不允许大于2^30次方
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//负载因子必须是大于0的有效数字
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.
*/
public HashMap(int initialCapacity) {//该构造方法实际执行的是HashMap(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
*/
public HashMap(Map<? extends K, ? extends V> m) {
//赋值默认加载因子0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
复制代码
HashMap中数据存在实际是以链表的形式存储的，即 transient Node<K,V>[] table中，对此这边我们先查看分析下Node的结构
Node链表类，实现了Map.Entry<K,V>元素接口，用于存放HashMap内容
/** *
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //节点的hash值
final K key; //元素的key值，即Map.put(key,value)中的key
V value; //元素的value值,即Map.put(key,value)中的value
Node<K,V> next; //链表所指向的下一个元素next ,可以看出是链表的一个形式，一链串一链
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//每一个节点的hash值，是将key的hashCode 和 value的hashCode 异或得到的。
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置value并返回旧value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断节点是否相同,key和value都相等为相同
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
复制代码
这边结合上诉源码中的注解,
先对构造方法一:HashMap(int initialCapacity, float loadFactor),进行分析，该构造方法中使用
this.threshold = tableSizeFor(initialCapacity);来获取当前哈希表的阈值，
其中tableSizeFor(initialCapacity)方法操作如下：
复制代码
tableSizeFor函数，根据期望容量获取哈希桶阈值
/**
* 这边的位操作最后会得到一个>=期望容量cap的最接近的2^n的值；
* 结果会判断是否阈值是否<0或者大于现在的最大容量2^30，，并进行修复
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
//经过下面的 或 和位移 运算， n最终各位都是1。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码
构造方法四:public HashMap(Map<? extends K, ? extends V> m)中调用putMapEntries(m, false);来对哈希表进行一个初始化的赋值操作
putMapEntries函数，通过Map进行初始赋值
/**
* 实现了Map.putAll和Map构造方法四的功能,
其中参数evict在构造方法中传入的为false，其它地方为true
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取需要从中获取内容的哈希表的大小
int s = m.size();
//传入的哈希表不为空才进行操作
if (s > 0) {
//如果当前链表table为空，即尚未使用过,
if (table == null) { // pre-size
//获取链表table需要的初始大小
float ft = ((float)s / loadFactor) + 1.0F;
//限制大小不得超过MAXIMUM_CAPACITY 2^30
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果需要的大小大于阈值threshold时，
则执行tableSizeFor(见上述分析)获取阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果当前链表不为空（例如使用过程中，再次通过Map.putAll添加元素）
//当前需要添加的元素大小大于阈值,则进行扩容操作resize()
else if (s > threshold)
resize();
//循环遍历m,并使用putVal将里面的元素逐一添加进来
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
复制代码
resize方法，对HashMap的容量进行扩展
当添加到表内的元素的大小即将超过阈值的时候，会执行扩容操作，扩大哈希表的大小用于存放元素； 返回的是扩容后的哈希桶对象(数组) Node<K,V>[]
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
//获取保存的原本哈希桶对象
Node<K,V>[] oldTab = table;
//获取原本哈希桶的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取原本阈值大小
int oldThr = threshold;
//新的哈希桶容量长度、新的阈值
int newCap, newThr = 0;
//如果原本的哈希桶容量大小>0
if (oldCap > 0) {
//当前容量已经达到限制的最大大小MAXIMUM_CAPACITY
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;//不再进行扩容操作，返回原本的哈希桶
}
/*当前容量尚未达到最大大小时，则扩容后的容量大小为2*oldCap, (新容量newCap = oldCap << 1即newCap = oldCap *2)，
如果翻倍后的新容量newCap小于MAXIMUM_CAPACITY，
并且原本容量oldCap大于默认的DEFAULT_INITIAL_CAPACITY(16)，
则新阈值大小 = 旧阈值oldThr*2 */
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果原本的哈希桶尚没有大小并且原本已经设置了阈值,则新容量的大小等于旧阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果原本的哈希桶没有大小并且尚未设置阈值时（比如直接使用构造方法三new HashMap()刚创建时），
//则新容量默认为16，新阈值默认计算公式计算
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新阈值newThr大小为0,对newThr根据newCap与加载因子进行赋值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
//越界修复,newCap已经最大了则设置newThr=Integer.MAX_VALUE即2^31-1，
使得后续不再扩容
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//计算结束后，重新设置HashMap的阈值threshold
threshold = newThr;
//根据计算后的新容量大小重新创建数组Node<K,V>[]
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将重新创建后的数组赋值给HashMap的哈希桶
table = newTab;
//将原本哈希桶中的元素逐一复制过来
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//循环遍历旧哈希桶
Node<K,V> e;
//当前桶中有元素则将准备其赋值给新桶,
哈希桶虽然底层是数组，但存放时不一定是按序存的，
可能还有的位置是没有存放元素的
if ((e = oldTab[j]) != null) {
oldTab[j] = null; //旧桶(旧链表)中的元素设置为null，方便后续GC回收
//代表原本旧链表中就一个表头元素(说明没有发生哈希碰撞)，将其赋值给新链表
if (e.next == null)
//下标使用&符号实现，相比之前版本的取余%更有效率
newTab[e.hash & (newCap - 1)] = e;
//如果发生了哈希碰撞且节点数超过8个，已转换为红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果发生了哈希碰撞且节点数不超过8个,则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//之前版本计算方式为hash& (newCap - 1);
这里又是一个利用位运算代替常规运算的高效点：
利用哈希值与 旧的容量，可以得到哈希值去模后，
是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，
否则存放在高位
if ((e.hash & oldCap) == 0) {
//while循环获取需要存放在低位的元素链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//while循环获取需要存放在高位的元素链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { //将低位链表赋值给新的哈希桶j索引处
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//将高位链表赋值给新的哈希桶j+oldCap索引处
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab; //返回创建并添加了旧元素的哈希桶
}
复制代码
增加、修改
1.put(k,v)方法，往哈希表中添加或者覆盖更新对应key的元素,调用putVal实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
复制代码
2.putIfAbsent(k,v)方法(JDK8才新增的API)，往哈希表中添加key对应的新元素，若原本已存在key对应的元素则不进行更新,调用putVal实现
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
复制代码
3.replace(k,v)方法(JDK8才新增的方法),替换key对应元素的value值,不存在不替换(内部还是调用了put)
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
复制代码
4.replace(K key, V oldValue, V newValue) ,若存在key对应的元素且value相等于oldValue则将其替换为newValue(内部还是调用了put)
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
复制代码
5.putAll(Map<? extends K, ? extends V> m),将m中存在的元素全部添加进哈希表, 前面已描述过putMapEntries
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
复制代码
/**
* onlyIfAbsent这个参数,true表示原本不存在这个key对应的元素，
则进行添加.若原本已经存在，则不会覆盖更新旧元素的值;
false代表每次都进行更新覆盖
*
* evict 这个参数，第一次初始化时时为false,其余为true
* 使用put(K,V)时 ,onlyIfAbsent=false ,evict=true
* 使用putIfAbsent(K,V)时(JDK8新增),onlyIfAbsent=true ,evict=true
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
，true代表如果元素原本存在该key，则不修改
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果原本哈希桶未创建或者大小为0,代表是初始化,则进行创建扩容操作，
并获取扩容后的容量大小n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果计算需要存放索引的位置(n-1)&hash尚未存放元素时,
说明未发生哈希碰撞,则直接存放
// jdk8使用 (n - 1) & hash代替之前版本的hash & (n-1)，更高效
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//需要存放的元素的索引位置已存在其它元素，发生哈希碰撞
else {
Node<K,V> e; K k;
//如果原索引根位置元素与新元素hash和key一致，则直接覆盖value
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果不是覆盖操作，插入一个普通的链表节点
else {
//遍历该位置的链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到尾部，追加新节点到尾部
p.next = newNode(hash, key, value, null);
//如果追加节点后，链表数量》=8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果找到了要覆盖的节点
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e不为空，说明需要更新覆盖旧元素的value,不用增加元素个数
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent参数判断
e.value = value;
//这是一个空实现的函数，用作LinkedHashMap重写使用。
afterNodeAccess(e);
return oldValue;
}
}
//如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。
//修改modcout
++modCount;
//增加有效元素的个数，并判断是否需要进行扩容
if (++size > threshold)
resize();
//这是一个空实现的函数，用作LinkedHashMap重写使用。
afterNodeInsertion(evict);
return null;
}
复制代码
删除
1.remove(k)方法，从哈希表中移除指定key对应的元素
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
复制代码
2.remove(k,v)方法(JDK8才新增的API)，从哈希表中移除指定key并且value匹配对应的元素
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
复制代码
2.clear方法，清空哈希表的所有元素
//源码上看出就是把哈希桶的每个索引位置指向的链表头元素置为null，清除元素数量size=0
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
复制代码
/** 返回被删除的元素Node<K,V>
* 参数matchValue，代表需要value也相等才进行删除
* 如果movable参数是false，在删除节点时，不移动其他节点(红黑树用)
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//当前哈希表不为空才进行删除操作，
获取key应该存放的索引index位置的表头元素p,
p不为空进行下一步判断
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//如果链表表头p就是要删除的元素时,node=p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//如果链表表头p不是要删除的元素，则遍历该链表
else if ((e = p.next) != null) {
if (p instanceof TreeNode)//红黑树,获取需要删除的元素node
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; //获取到需要删除的元素node
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果存在key匹配的需要删除的元素node
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) //红黑树，删除元素node
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //需要删除的元素就是链表的链表头
tab[index] = node.next;
//只需要将哈希表索引位置的链表头重新修改为node.next即可
//需要删除的不是根元素，只需要将node前一元素p的p.next
指向要node后一元素node.next即可
else
p.next = node.next;
++modCount;//修改次数
--size;//对应动态减少当前有效元素数量标志量
afterNodeRemoval(node);//空操作,LinkHashMap重写用
return node;
}
}
return null;
}
复制代码
查询
1.get方法，获取指定key对应元素的Value,存放则返回value，否则返回null
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
复制代码
2.getOrDefault(K key,V defaultValue),JDK8提供的方法,获取指定key对应的元素value,存在则返回对应的value，否则返回defaultValue
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
复制代码
3.containsKey方法，判断哈希表中所有key项是否包含该key，存在返回true,不存在返回false
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
复制代码
3.containsValue方法，判断哈希表中所有value项中是否包含该value，存在返回true,不存在返回false,源码上看就是所有节点遍历过去，遇到存在value相等则停止
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
复制代码
/** 该方法为根据的key获取到节点元素Node,存在返回Node,否则返回null
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//和removeNode类似，判断哈希表不为空，并获取索引index位置的链表头元素first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果first是要查询的元素，则返回first
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//循环遍历链表进行查询
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
复制代码
查询之迭代器遍历
1.keySet()，根据key进行遍历
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
复制代码
2.values(),根据value进行遍历
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
复制代码
3.entrySet(),根据元素节点进行遍历
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
qrcode_for_gh_1bbc19ef669d_258.jpg
网友评论