final K key; V value; Entry<K,V> next; int hash;
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value);//见putForNullKey方法 int hash = hash(key); int i = indexFor(hash, table.length);//见indexFor方法,取模 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))) {//判断hash值一样,并且key也要一样 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i);//见addEntry方法 return null; }
key为空的情况,在数组的第一个位置的链表遍历查找,如果有key为空,返回相应的值,如果没有,添加到链表后面。
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; }
注释已经提醒了,length长度必须是2的非0幂数,h & (length-1)是对h%length的意思(length长度为2的非0幂数时有效)。比如123243423 % 16的值是15,123243423 & 15也是15,当然123243423是我随便打的。取模主要是为了能够平均的落在每个数组上面。
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); }
void addEntry(int hash, K key, V value, int bucketIndex) { //扩容为2倍长度,跟上面取模要求的一样,乘以2也是2的非0幂数 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);//见createEntry方法 }
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++; } /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key);//见getEntry方法 return null == entry ? null : entry.getValue(); }
private V getForNullKey() { if (size == 0) { return null; } for (Entry<K,V> e = table[0]; e != null; e = e.next) {//因为put的时候,直接放数组的第一个,所以查询的时候,也查询第一个 if (e.key == null) return e.value; } return null; }
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key);//先取hash 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))))//判断hash和key都相等 return e; } return null; }
这个方法在调用put的时候,在resize扩容的时候调用。在多线程的情况下,会造成死循环。
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; } } }