Map之HashMap源码分析

时间:2021-05-20 16:48:17

public class HashMap<K,V>

extends AbstractMap<K,V>

implements Map<K,V>, Cloneable, Serializable

HashMap继承自AbstractMap,实现了Map接口,有map的基本操作;实现了Cloneable接口,使得该类是可克隆的;实现了Serializable接口,说明该类支持序列化。HashMap是线程不安全的。源码版本为JDK1.7.0_75。

   

HashMap的数据结构

Map之HashMap源码分析

紫色的对应Entry<K,V>[] table,绿色的是Entry<K,V>对象队列,解决hash冲突。

put时,首先调用hashCode方法获得哈希值,在调用indexFor方法获取该key存放在table数组的下标index,新建entry插入到index所指向的链表的队首。在删除时也是通过相同的方法找到该key所在的index,然后遍历链表,将key相同、hash值相等的entry删除。

HashMap还对map存放的key-value数目进行限制(使用threshold),且要求数组大小(capacity)必须是2的幂次方(考虑indexFor方法),当容量无法将entry全部保存或者entry数目超过threshold时,根据loadfactor使用resize对容量进行扩大,其中threshold=capacity*loadfactor。

HashMap中允许存放key为null的entry,对于key为null,其index为0。

inflateTable方法是在当table==EMPTY_TABLE时才用到,用于初始化table

   

成员变量

   

/**

* 默认初始化空间——必须为2的倍数

* The default initial capacity - MUST be a power of two.

*/

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

   

/**

* 最大空间,若在构造方法中没有给定,则使用该值——必须为2的倍数

* 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;

   

/**

* 若在构造时没有指出则使用该值作为加载因子

* The load factor used when none specified in constructor.

*/

static final float DEFAULT_LOAD_FACTOR = 0.75f;

   

/**

* 当表格没有膨胀,则空表实例

* An empty table instance to share when the table is not inflated.

*/

static final Entry<?,?>[] EMPTY_TABLE = {};

   

/**

* 哈希表,有必要时需resize。长度总是2的倍数

* The table, resized as necessary. Length MUST Always be a power of two.

*/

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

   

/**

* map中包含的key-value映射数目

* The number of key-value mappings contained in this map.

*/

transient int size;

   

/**

* 调整大小的值??临界值,当实际大小超过临界值时,会进行resize,threshold=capacity*load factor

* The next size value at which to resize (capacity * load factor).

* @serial

*/

// If table == EMPTY_TABLE then this is the initial capacity at which the

// table will be created when inflated.

int threshold;

   

/**

* 哈希表的加载因子

* The load factor for the hash table.

*

* @serial

*/

final float loadFactor;

   

/**

* HashMap进行结构上修改的次数。用来是对HashMap的集合上的迭代器fast-fail

* 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;

   

/**

* 当使用string作为键值的哈希时的map容量的默认阈值。。。

* The default threshold of map capacity above which alternative hashing is

* used for String keys. Alternative hashing reduces the incidence of

* collisions due to weak hash code calculation for String keys.

* <p/>

* This value may be overridden by defining the system property

* {@code jdk.map.althashing.threshold}. A property value of {@code 1}

* forces alternative hashing to be used at all times whereas

* {@code -1} value ensures that alternative hashing is never used.

*/

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

/**

* 随机值,用在keyshash code上,使得哈希冲突较难发生。若该值为0,则alternative hash不可用(我理解的是二次哈希

* A randomizing value associated with this instance that is applied to

* hash code of keys to make hash collisions harder to find. If 0 then

* alternative hashing is disabled.

*/

transient int hashSeed = 0;

  

loadFactor为加载因子,表示hash表中元素的填满程度,加载因子越大,空间利用率高,但冲突机会就加大了,链表长度会越来越长,查找效率将降低;反之,加载因子越小,填满的元素越少,冲突机会减少,但空间浪费了。

冲突机会越大,则查找效率将降低。

因此,需要在"冲突机会"与"空间利用率"之间寻找平衡——类似"时空"平衡。

参考:

http://www.cnblogs.com/ITtangtang/p/3948406.html

   

私有静态内部类Holder

/**

* 保存那些直到虚拟机启动时才能初始化的值

* holds values which can't be initialized until after VM is booted.

*/

private static class Holder {

   

/**

* 当转向使用alternative hashing时,table的容量

* Table capacity above which to switch to use alternative hashing.

*/

static final int ALTERNATIVE_HASHING_THRESHOLD;

   

static {

String altThreshold = java.security.AccessController.doPrivileged(

new sun.security.action.GetPropertyAction(

"jdk.map.althashing.threshold"));

   

int threshold;

try {

threshold = (null != altThreshold)

? Integer.parseInt(altThreshold)

: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

   

// disable alternative hashing if -1

if (threshold == -1) {

threshold = Integer.MAX_VALUE;

}

   

if (threshold < 0) {

throw new IllegalArgumentException("value must be positive integer.");

}

} catch(IllegalArgumentException failed) {

throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);

}

   

ALTERNATIVE_HASHING_THRESHOLD = threshold;

}

}

   

构造函数

   

/**

* 指定了初始容量和加载因子,构造一个空HashMap

* 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;

threshold = initialCapacity;

init();

}

   

/**

* 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) {

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(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

   

/**

* 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) {

this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

inflateTable(threshold);

   

putAllForCreate(m);

}

   

inflateTable,该方法在table==EMPTY_TABLE时被调用,用于初始化table,并将capacity提至2的幂次方。

private static int roundUpToPowerOf2(int number) {

// assert number >= 0 : "number must be non-negative";

return number >= MAXIMUM_CAPACITY

? MAXIMUM_CAPACITY

: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;

}

/**

* Inflates the table.

*/

private void inflateTable(int toSize) {

// Find a power of 2 >= toSize

int capacity = roundUpToPowerOf2(toSize);

   

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

table = new Entry[capacity];

initHashSeedAsNeeded(capacity);

}

   

// internal utilities

   

/**

* 为子类初始化hook(钩子)。该方法在构造方法和伪构造方法(clonereadObject)中初始化HashMap之后entry被插入之前调用的。没有该方法,readObject将需要子类信息。

* Initialization hook for subclasses. This method is called

* in all constructors and pseudo-constructors (clone, readObject)

* after HashMap has been initialized but before any entries have

* been inserted. (In the absence of this method, readObject would

* require explicit knowledge of subclasses.)

*/

void init() {

}

   

/**

* 初始化哈希mask值。直到真的需要用到hashseed时,才初始化它。

* Initialize the hashing mask value. We defer initialization until we

* really need it.

*/

final boolean initHashSeedAsNeeded(int capacity) {

boolean currentAltHashing = hashSeed != 0;

boolean useAltHashing = sun.misc.VM.isBooted() &&

(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);

boolean switching = currentAltHashing ^ useAltHashing;

if (switching) {

hashSeed = useAltHashing

? sun.misc.Hashing.randomHashSeed(this)

: 0;

}

return switching;

}

  

   

hashing相关

   

/**

* 获得对象哈希码,并将一个补充的哈希函数应用到哈希结果以防poor哈希函数。

* 注意:键为null总是映射到哈希0,因此索引为0。

* Retrieve object hash code and applies a supplemental hash function to the

* result hash, which defends against poor quality hash functions. This is

* critical because HashMap uses power-of-two length hash tables, that

* otherwise encounter collisions for hashCodes that do not differ

* in lower bits. Note: Null keys always map to hash 0, thus index 0.

*/

final int hash(Object k) {

int h = hashSeed;

if (0 != h && k instanceof String) {

return sun.misc.Hashing.stringHash32((String) k);

}

   

h ^= k.hashCode();

  // 通过若干次移位、异或操作,把hashCode的1的位置变得"松散,均匀",

// 以免在计算index时不均匀

// 等价于操作 h ^ (h >>> 4) ^ (h >>> 7) ^ (h >>> 12) ^ (h >>> 16) ^ (h >>> 20) ^ (h >>> 24) ^ (h >>> 27);

// 将hashcode用十六进制表示为…nmlkjihgfedcba,则a'=a^b^c…,b'=b^c^d…,c'=c^d^e…

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

   

/**

* 返回哈希码h的索引

* 因为length为2的幂次方,因此length-1使用二进制表示所有位都是1,即111111..,h&(length-1)得到的数可以均匀分布到table数组上,例如length=8,则1&7=1,2&7=2,3&7=3,…7&7=7,8&7=0,9&7=1..,可以看出该公式相当于h%length,注意的是针对length要为2的幂次方。

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

return h & (length-1);

}

   

Get key相关

   

/**

* 返回给定keymap上对应的value,若map中没有该key,则返回null

* Returns the value to which the specified key is mapped,

* or {@code null} if this map contains no mapping for the key.

*

* <p>More formally, if this map contains a mapping from a key

* {@code k} to a value {@code v} such that {@code (key==null ? k==null :

* key.equals(k))}, then this method returns {@code v}; otherwise

* it returns {@code null}. (There can be at most one such mapping.)

*

* <p>A return value of {@code null} does not <i>necessarily</i>

* indicate that the map contains no mapping for the key; it's also

* possible that the map explicitly maps the key to {@code null}.

* The {@link #containsKey containsKey} operation may be used to

* distinguish these two cases.

*

* @see #put(Object, Object)

*/

public V get(Object key) {

if (key == null)

return getForNullKey();

Entry<K,V> entry = getEntry(key);

   

return null == entry ? null : entry.getValue();

}

   

/**

* 获取keynull所对应的value。前面提到keynull对应的索引为0,因此从table[0]

* 开始遍历。

* Offloaded version of get() to look up null keys. Null keys map

* to index 0. This null case is split out into separate methods

* for the sake of performance in the two most commonly used

* operations (get and put), but incorporated with conditionals in

* others.

*/

private V getForNullKey() {

if (size == 0) {

return null;

}

for (Entry<K,V> e = table[0]; e != null; e = e.next) {

if (e.key == null)

return e.value;

}

return null;

}

   

/**

* Returns <tt>true</tt> if this map contains a mapping for the

* specified key.

*

* @param key The key whose presence in this map is to be tested

* @return <tt>true</tt> if this map contains a mapping for the specified

* key.

*/

public boolean containsKey(Object key) {

return getEntry(key) != null;

}

   

/**

* Returns the entry associated with the specified key in the

* HashMap. Returns null if the HashMap contains no mapping

* for the key.

*/

final Entry<K,V> getEntry(Object key) {

if (size == 0) {

return null;

}

   

int hash = (key == null) ? 0 : hash(key);

for (Entry<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 相关

   

/**

* 根据key值将key-value对插入到map中,若key已存在,则更新value。返回插入前map

* 中key所对应的value值。

* Associates the specified value with the specified key in this map.

* If the map previously contained a mapping for the key, the old

* value is replaced.

*

* @param key key with which the specified value is to be associated

* @param value value to be associated with the specified key

* @return the previous value associated with <tt>key</tt>, or

* <tt>null</tt> if there was no mapping for <tt>key</tt>.

* (A <tt>null</tt> return can also indicate that the map

* previously associated <tt>null</tt> with <tt>key</tt>.)

*/

public V put(K key, V value) {

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

if (key == null)

return putForNullKey(value);

int hash = hash(key);

int i = indexFor(hash, table.length);

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

   

modCount++;

addEntry(hash, key, value, i);

return null;

}

   

/**

* 设置keynull时的value值。

* Offloaded version of put for null keys

*/

private V putForNullKey(V value) {

for (Entry<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++;

addEntry(0, null, value, 0);

return null;

}

   

/**

* 不同于put,该方法不需要resize table,构造方法或伪构造方法(clone,readObject)调用该方法。

* This method is used instead of put by constructors and

* pseudoconstructors (clone, readObject). It does not resize the table,

* check for comodification, etc. It calls createEntry rather than

* addEntry.

*/

private void putForCreate(K key, V value) {

int hash = null == key ? 0 : hash(key);

int i = indexFor(hash, table.length);

   

/**

* Look for preexisting entry for key. This will never happen for

* clone or deserialize. It will only happen for construction if the

* input Map is a sorted map whose ordering is inconsistent w/ equals.

*/

for (Entry<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);

}

   

private void putAllForCreate(Map<? extends K, ? extends V> m) {

for (Map.Entry<? extends K, ? extends V> e : m.entrySet())

putForCreate(e.getKey(), e.getValue());

}

   

Resize

 

   

/**

* 将原来map内容重哈希到一个更大容量的新数组上。当mapkey数目达到threshold时,自动调用该方法。若当前容量为MAXIMUM_CAPACITY,则不resize map,设置threshold为Integer.MAX_VALUE

* Rehashes the contents of this map into a new array with a

* larger capacity. This method is called automatically when the

* number of keys in this map reaches its threshold.

*

* If current capacity is MAXIMUM_CAPACITY, this method does not

* resize the map, but sets threshold to Integer.MAX_VALUE.

* This has the effect of preventing future calls.

*

* @param newCapacity the new capacity, MUST be a power of two;

* must be greater than current capacity unless current

* capacity is MAXIMUM_CAPACITY (in which case value

* is irrelevant).

*/

void resize(int newCapacity) {

Entry[] oldTable = table;

int oldCapacity = oldTable.length;

if (oldCapacity == MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return;

}

   

Entry[] newTable = new Entry[newCapacity];

transfer(newTable, initHashSeedAsNeeded(newCapacity));

table = newTable;

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

}

   

/**

* 将当前表中所有entry转换到newTable中。rehash标志转换时是否需要重哈希。

* Transfers all entries from current table to newTable.

*/

void transfer(Entry[] newTable, boolean rehash) {

int newCapacity = newTable.length;

for (Entry<K,V> e : table) {

while(null != e) {

Entry<K,V> next = e.next;

if (rehash) {

e.hash = null == e.key ? 0 : hash(e.key);

}

int i = indexFor(e.hash, newCapacity);

e.next = newTable[i];

newTable[i] = e;

e = next;

}

}

}

   

将m中的key-value对全都复制到map中,在put之前,首先对table进行resize,若要添加的键-值对大于threshold,则对table进行resize。

   

/**

* Copies all of the mappings from the specified map to this map.

* These mappings will replace any mappings that this map had for

* any of the keys currently in the specified map.

*

* @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));

}

   

/*

* Expand the map if the map if the number of mappings to be added

* is greater than or equal to threshold. This is conservative; the

* obvious condition is (m.size() + size) >= threshold, but this

* condition could result in a map with twice the appropriate capacity,

* if the keys to be added overlap with the keys already in this map.

* By using the conservative calculation, we subject ourself

* to at most one extra resize.

*/

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);

}

   

for (Map.Entry<? extends K, ? extends V> e : m.entrySet())

put(e.getKey(), e.getValue());

}

   

删除。。。删除特定key,首先根据key,计算hash,得到索引,获取所在的"桶",遍历桶内的链表,删除hash相等且key相等的entry。

   

/**

* Removes the mapping for the specified key from this map if present.

*

* @param key key whose mapping is to be removed from the map

* @return the previous value associated with <tt>key</tt>, or

* <tt>null</tt> if there was no mapping for <tt>key</tt>.

* (A <tt>null</tt> return can also indicate that the map

* previously associated <tt>null</tt> with <tt>key</tt>.)

*/

public V remove(Object key) {

Entry<K,V> e = removeEntryForKey(key);

return (e == null ? null : e.value);

}

   

/**

* 删除并返回key所对应的entry,若map中不存在该key,返回null

* Removes and returns the entry associated with the specified key

* in the HashMap. Returns null if the HashMap contains no mapping

* for this key.

*/

final Entry<K,V> removeEntryForKey(Object key) {

if (size == 0) {

return null;

}

int hash = (key == null) ? 0 : hash(key);

int i = indexFor(hash, table.length);

Entry<K,V> prev = table[i];

Entry<K,V> e = prev;

   

while (e != null) {

Entry<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;

}

   

   

/**

* 根据Map.Entry.equals方法找出与对象o相匹配的entry,将其删除。

* Special version of remove for EntrySet using {@code Map.Entry.equals()}

* for matching.

*/

final Entry<K,V> removeMapping(Object o) {

if (size == 0 || !(o instanceof Map.Entry))

return null;

   

Map.Entry<K,V> entry = (Map.Entry<K,V>) o;

Object key = entry.getKey();

int hash = (key == null) ? 0 : hash(key);

int i = indexFor(hash, table.length);

Entry<K,V> prev = table[i];

Entry<K,V> e = prev;

   

while (e != null) {

Entry<K,V> next = e.next;

if (e.hash == hash && e.equals(entry)) {

modCount++;

size--;

if (prev == e)

table[i] = next;

else

prev.next = next;

e.recordRemoval(this);

return e;

}

prev = e;

e = next;

}

   

return e;

}

   

/**

* 删除map中所有映射,使用Arrays.fill方法将table数组的值都设为null

* Removes all of the mappings from this map.

* The map will be empty after this call returns.

*/

public void clear() {

modCount++;

Arrays.fill(table, null);

size = 0;

}

   

containXXX类方法

   

/**

* Returns <tt>true</tt> if this map maps one or more keys to the

* specified 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();

   

Entry[] tab = table;

for (int i = 0; i < tab.length ; i++)

for (Entry e = tab[i] ; e != null ; e = e.next)

if (value.equals(e.value))

return true;

return false;

}

   

/**

* Special-case code for containsValue with null argument

*/

private boolean containsNullValue() {

Entry[] tab = table;

for (int i = 0; i < tab.length ; i++)

for (Entry e = tab[i] ; e != null ; e = e.next)

if (e.value == null)

return true;

return false;

}

   

clone方法

   

/**

* Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and

* values themselves are not cloned.

*

* @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;

}

   

静态内部类Entry

   

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

V value;

Entry<K,V> next;

int hash;

   

/**

* Creates new entry.

*/

Entry(int h, K k, V v, Entry<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;

}

   

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();

}

   

/**

* entry的值通过调用put方法被重写时该方法将被调用

* This method is invoked whenever the value in an entry is

* overwritten by an invocation of put(k,v) for a key k that's already

* in the HashMap.

*/

void recordAccess(HashMap<K,V> m) {

}

   

/**

* entrytable中删除时该方法将被调用

* This method is invoked whenever the entry is

* removed from the table.

*/

void recordRemoval(HashMap<K,V> m) {

}

}

   

entry相关操作

   

/**

* 添加一个新的entry

* Adds a new entry with the specified key, value and hash code to

* the specified bucket. It is the responsibility of this

* method to resize the table if appropriate.

*

* Subclass overrides this to alter the behavior of put method.

*/

void addEntry(int hash, K key, V value, int bucketIndex) {

if ((size >= threshold) && (null != table[bucketIndex])) {

resize(2 * table.length);

hash = (null != key) ? hash(key) : 0;

bucketIndex = indexFor(hash, table.length);

}

   

createEntry(hash, key, value, bucketIndex);

}

   

/**

* 创建entry,并将其添加到table[bucketIndex]队首中。

* Like addEntry except that this version is used when creating entries

* as part of Map construction or "pseudo-construction" (cloning,

* deserialization). This version needn't worry about resizing the table.

*

* Subclass overrides this to alter the behavior of HashMap(Map),

* clone, and readObject.

*/

void createEntry(int hash, K key, V value, int bucketIndex) {

Entry<K,V> e = table[bucketIndex];

table[bucketIndex] = new Entry<>(hash, key, value, e);

size++;

}

   

迭代。。。。(没看)

   

私有内部类KeySet及相关方法

   

// Views

   

private transient Set<Map.Entry<K,V>> entrySet = null;

   

/**

* Returns a {@link Set} view of the keys contained in this map.

* The set is backed by the map, so changes to the map are

* reflected in the set, and vice-versa. If the map is modified

* while an iteration over the set is in progress (except through

* the iterator's own <tt>remove</tt> operation), the results of

* the iteration are undefined. The set supports element removal,

* which removes the corresponding mapping from the map, via the

* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,

* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>

* operations. It does not support the <tt>add</tt> or <tt>addAll</tt>

* operations.

*/

public Set<K> keySet() {

Set<K> ks = keySet;

return (ks != null ? ks : (keySet = new KeySet()));

}

   

private final class KeySet extends AbstractSet<K> {

public Iterator<K> iterator() {

return newKeyIterator();

}

public int size() {

return size;

}

public boolean contains(Object o) {

return containsKey(o);

}

public boolean remove(Object o) {

return HashMap.this.removeEntryForKey(o) != null;

}

public void clear() {

HashMap.this.clear();

}

}

   

私有内部类Value及其相关方法

   

/**

* Returns a {@link Collection} view of the values contained in this map.

* The collection is backed by the map, so changes to the map are

* reflected in the collection, and vice-versa. If the map is

* modified while an iteration over the collection is in progress

* (except through the iterator's own <tt>remove</tt> operation),

* the results of the iteration are undefined. The collection

* supports element removal, which removes the corresponding

* mapping from the map, via the <tt>Iterator.remove</tt>,

* <tt>Collection.remove</tt>, <tt>removeAll</tt>,

* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not

* support the <tt>add</tt> or <tt>addAll</tt> operations.

*/

public Collection<V> values() {

Collection<V> vs = values; // values属于AbstractMap的成员变量

return (vs != null ? vs : (values = new Values()));

}

   

private final class Values extends AbstractCollection<V> {

public Iterator<V> iterator() {

return newValueIterator();

}

public int size() {

return size;

}

public boolean contains(Object o) {

return containsValue(o);

}

public void clear() {

HashMap.this.clear();

}

}

   

私有内部类EntrySet及相关方法

   

/**

* Returns a {@link Set} view of the mappings contained in this map.

* The set is backed by the map, so changes to the map are

* reflected in the set, and vice-versa. If the map is modified

* while an iteration over the set is in progress (except through

* the iterator's own <tt>remove</tt> operation, or through the

* <tt>setValue</tt> operation on a map entry returned by the

* iterator) the results of the iteration are undefined. The set

* supports element removal, which removes the corresponding

* mapping from the map, via the <tt>Iterator.remove</tt>,

* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and

* <tt>clear</tt> operations. It does not support the

* <tt>add</tt> or <tt>addAll</tt> operations.

*

* @return a set view of the mappings contained in this map

*/

public Set<Map.Entry<K,V>> entrySet() {

return entrySet0();

}

   

private Set<Map.Entry<K,V>> entrySet0() {

Set<Map.Entry<K,V>> es = entrySet;

return es != null ? es : (entrySet = new EntrySet());

}

   

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {

public Iterator<Map.Entry<K,V>> iterator() {

return newEntryIterator();

}

public boolean contains(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry<K,V> e = (Map.Entry<K,V>) o;

Entry<K,V> candidate = getEntry(e.getKey());

return candidate != null && candidate.equals(e);

}

public boolean remove(Object o) {

return removeMapping(o) != null;

}

public int size() {

return size;

}

public void clear() {

HashMap.this.clear();

// HashMap.this值获取HashMap本身,所调用的clear即HashMap的方法

}

}

   

参考:

http://www.cnblogs.com/ITtangtang/p/3948406.html

http://blog.csdn.net/dyllove98/article/details/9207601