java基础（HashMap理解）
HashMap其原理是底层是一个table数组+链表，数组的每一项是一个链表头。当然不同的jar包对应的HashMap源码还是有点出入的，以下以安卓的为准。
而存入数组中的元素是Entry，Entry可以理解为一个封装了key和value的对象，我们存进入的其实是一个Entry对象，里面包含了key和value值。
image.png
分析一下put方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
new一个HashMap时候，其实并没有创建一片内存地址，只有在put时候才会去判断table是否为空，如果为空才创建。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
put方法里面先判断key值是否为空，如果是空的话，直接返回空值。
if (key == null)
return putForNullKey(value);
如果key不为空的话，通过key计算获取到hash值
然后通过hash值获取到数组中相应的索引，这里要注意一下，如果put多个的话，数组角标i的值是有可能一样的，因为数组存的每一项其实也是一个链表头，如果当期数组已经有put进entry对象的话，那么就通过链表插入值，采用的是头插法。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
获取到数组角标后，通过角标去for循环遍历这个角标下的链表，如果是当前key是之前已经有插入的相同的key，那么就把新值插入之前相同的key中，然后把旧的value return回来
for (HashMapEntry<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;
}
}
如果key是新的key的话，就新增一个entry，当前的hash值，数值角标，key，value值存进去
ddEntry(hash, key, value, i);
分析一下get方法：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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;
}
通过get方法可以看出，调用了getEntry方法，通过key获取到entry对象，如果对象为空，只返回空值，如果对象不为空，则返回相应的value值。
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
重点要看下getEntry方法，通过源码可以看通过key获取到了hash值，然后通过for循环遍历相应数组角标下的链表，判断key值一样，并且hash值一样的话，就返回相应的entry对象。
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;
}
而且遍历是从链表头开始遍历的，这也说明了越后面的put进去的值被找到的时间越短。
关于扩容问题
从源码中可以看出在put里面的addEntry方法进行判断，当数组不为空或者put数量（size）大于16个时候，就会进行扩容，扩容了一倍。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
