import java.util.HashMap;
import java.util.Map;
public class Test2 {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("abc", "abc");
map.put("abc2", "abc");
map.put("abc3", "abc");
map.put("abc4", "abc");
map.put("abc5", "abc");
map.put("abc6", "abc");
map.put("abc7", "abc");
}
}
HashMap.jpg
HashMap底层实际上是一个数组，存储Entry<K，V>这样类型的数据
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;
}
//..........
}
主要的是这个next，它是数组和链表共存结构的关键。
//当我们调用put()方法的时候
public V put(K key, V value) {
//如果table是空的
if (table == EMPTY_TABLE) {
//初始化
inflateTable(threshold);
}
if (key == null) //检查key是否为空
return putForNullKey(value);
int hash = hash(key); //计算hash
int i = indexFor(hash, table.length); //根据指定hash，找出在table中的位置
//table中，同一个位置（也就是同一个hash）可能出现多个元素（链表实现），故此处需要循环
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))) { //如果key已经存在，那么直接设置新值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//key 不存在，就在table指定位置之处新增Entry
addEntry(hash, key, value, i);
return null;
}
/**
* HashMap 添加节点
* @param hash 当前key生成的hashcode
* @param key 要添加到 HashMap 的key
* @param value 要添加到 HashMap 的value
* @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//size：The number of key-value mappings contained in this map.
//threshold：The next size value at which to resize (capacity * load factor)
//数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值
// 2.底层数组的bucketIndex坐标处不等于null
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);
}
/**
* 这地方就是链表出现的地方，有2种情况
* 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦
* 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了
*/
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++;
}
所以当两个对象的hash只相等的时候，他们会以链表的形式存储。
//当我们调用get()方法的时候
public V get(Object key) {
//key为null的时候返回null
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 : hash(key); //计算hash
//通过indexFor()计算出要获取的Entry对像在table数组中的精确位置
//获取到table的索引时候,会迭代链表，调用equals()方法检查key的相等性，
// 如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null
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;
}
