hashMap实现Map接口,基于hashing原理,以键值对形式存储,允许null键/值,非同步的集合类型;
hashmap的底层存储结构是基于数组和链表的
一、put方法
public Object put(Object key,Object value);
1、因为hashmap存储的底层结构是数组和链表,所以,当我们put时,需要计算出数组的下标:
1)执行key.hashCode()方法,得到哈希码:hashCode=key.hashCode();
2)用哈希码做hash运算,得到一个散列值:int hash = hash(hashCode);
3)散列值与数组的长度做indexFor运算,得到数组下标。
2、了解了这个过程,我们很容易能发现,即使key不同,经过前两步运算,也可能得到相同散列值。所以我们put时,新的entry和旧的entry可能发生冲突,解决hash冲突的方法有很多,在hashmap中采用的是链地址法。即:
对新entry和旧entry进行判断:
1)散列值相同,key相同;
此时说明是相同的entry,用新的entry覆盖旧的entry。
2)散列值相同,key不同;
执行key.equals()方法;
如果这两个对象通过hashmap重写的equals()方法判断是一样的,说明是同一个entry对象,用新的entry覆盖旧的entry;
如果不同,就把新加入的entry对象放在对应数组下标位置的表头,早进来的entry向后移动一个位置,形成链表;
特别注意:我们存放在数组中的并不只有value,是一个entry(hash,key,value,bucketIndex)对象。
3、链表长度太长,影响查询效率怎么办?
JDK1.8多了一个新特性,当链表的长度>=8时,链表转换为红黑树,提高查询效率:
1.8 链表转红黑树的源码 static final int TREEIFY_THRESHOLD = 8; if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break;
4、不断增加对象,是否需要扩容resize?
了解一下API里hashmap的构造方法,里面有initialCapacity和loadFactor两个名词;
initialCapacity是哈希表的数组的初识大小,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍;loadFactor是加载因子;HashMap的默认大小是16,那么他的数组长度是0-15;默认加载因子是0.75;threshold:扩容的阈值,等于 capacity * loadFactor
所以,当容量达到threshold时,数组会自动扩容到原来大小的两倍;比如,当前我们的数组的大小是16,当存储到12个元素时,数组会自动扩容到32.
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); }
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]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; transfer(newTable, rehash); table = newTable; threshold = (int)(newCapacity * loadFactor); }
5、key为null时
public V put(K key, V value) { 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; } 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; }
当key为null时,如果数组中有key为null的,遍历table[0]链表(key为null的元素放在了数组的第0位),如果找到,将传入的value重新赋值给这个元素的value,并返回原来的value。如果没有找到,就将元素添加到table[0]链表的表头。所以,key为null时,在hashmap的链表中只有一个值。
二、get
1、与put相同,先根据key,算出hash,算出数组下标,定位到数组元素。
2、遍历该元素处的链表
取出传进来的key与链表中entry对象的key值相等的value或传进来的key和entry对象的key连重写后的equals后都一样的value;
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //先定位到数组元素,再遍历该元素处的链表 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.equals(k))) return e.value; } return null; } private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }
3、当key为null时?
由put的过程可知,hashmap将key为null的元素放到了数组第0个元素的链表中。根据getForNullKey()的实现代码可知。