据说面试时讲自己读过源码会很不一样
个人理解散列表大概就是可以通过某些函数计算出不同key在存储的数组中对应的index，刷题的时候我们也会经常遇到需要存储26个字母的情况，于是新建数组
int[] letter = new int[26];
letter[(char)item- 'a']++;
从而实现对字母的计数。这里字母letter对应的index可以由letter-'a'计算得到，a对应0,b对应1.......也算是一个散列表吧。。后来读了书、 算法导论上叫他直接寻址表
在刚才特定场景下，我们知道这个数组只需要存储26个数字，因此能够直接新建数组，但是当全域非常大时，这样的直接寻址表明显会很浪费。于是推出主角散列表。
散列表中需要有散列函数将key值全域映射到存储散列表的数组的各个位置上。
于是首要的问题就变成了
可能不同的key值会被映射到相同的位置上
plan A 链接法：将存储数组变为List[ ]的形式，使用散列函数得到在数组中的index后，将当前key-value对插入该List中。数组中每个元素都是一个可长可短的链表。查询一个key值最多需要遍历最长的那个链表一次
plan B 开放寻址法（散列函数2.0）：将散列函数的输入扩充为key值和访问次数，当数组对应的index中key值与要查找的不同时，下次会生成新的index。
基础知识就到这里吧。。散列函数怎么写。。目前我感觉是一个过于算法的问题了。。书上也讲了很多
HashMap 继承AbstractMap， 实现Map<K,V>, Cloneable, Serializable 三个接口
/**
* The number of key-value mappings contained in this map.
*/
transient int size; // 所有key-value对的个数
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
这个table的length程序写的一定要是2的整数幂，至于为什么之后会提到。
使用HashMapEntry类型的数组
这个类型中有key、value、next、hash。这里明显用到了书上讲的第一个方法了，使用链表存储
get(Object key) 方法
对于get(Object key) 方法，会调用getForNullKey（key == null） 或getEntry(key);
在getEntry(key)中
/**
* 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 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//一个感觉带了人名的hash函数
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) { //当前HashMapEntry的next
Object k;
if (e.hash == hash && //判断hash值
((k = e.key) == key || (key != null && key.equals(k))))//判断key值
return e;
}
return null;
}
如果return e说明找到了Entry<K,V>，顺利返回。
这个判断key值的环节
(k = e.key) == key 可以判断出e.key与 当前key是否== 如果两者本就是相同的引用，则会返回true。因此很明显不要更改一个引用再把它多次作为key赋值。。会出事情的，像下面这样。我们会觉得aa和bb其实不相等的。
StringBuilder aa = new StringBuilder("a");
StringBuilder bb = aa;
bb.setCharAt(0, 'b');
System.out.println(aa == bb); // true
不过真实情况下还有hash值同样作为判断条件
put(K key, V 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 = 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; //找到了需要更改key值对应value
}
}
modCount++;
addEntry(hash, key, value, i); // 没找到，增加这个key-val对。这里面会size++的
return null;
}
我们关心一下indexFor函数
/**
* 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);// length为2的整数幂
}
在这里length为2的整数幂可以保证不论hash值具体为多少，访问数组总不会越界。（比如当length为8（1000）,length-1 为（111） h & (length-1)返回h的低三位）另一个信息就是即使在同一个index下，他们的hash值不会完全相同。只是低位相同
但是这个indexFor函数还是让人挺不放心的
int i = indexFor(hash, table.length);
当前元素的index是随着hash值以及table.length变化的。。。这个问题还是挺尴尬的。。毕竟hash值我们认为只要函数不变每个key生成的hash值就一定不变。。但是table.length得要变的。。
当添加key-value对到达门限，会进行resize(2 * table.length);直接将table扩充一倍
/**
* 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) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
其中ransfer(HashMapEntry[] newTable) 将原表内数据迁移，根据HashMapEntry中的hash重新计算在新表中的index，构造新的链表数组进行存储。
/**
* Transfers all entries from current table to newTable.
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //存储element时必须保存hash值
e.next = newTable[i]; //将当前元素放在该index的头部，放在尾部会增加时间复杂度
newTable[i] = e;
e = next;
}
}
}
