本人刚毕业工作不久，初出茅庐，有不对地方望指正，谢谢。
众所周知，HashMap是一个用于存储键值对（key-value），底层是有数组与链表实现的集合。每一个键值对也叫做Entry。这些键值对(Entry)分散存储在一个数组(table)当中。
我们常用的两个方法：put与get
1.put方法的原理
比如我插入一个key为name的元素。
①.根据key计算出hash值，
int hash= hash(key);
②.通过hash值与table数组的长度按（位运算 )计算出插入table位置的索引,假设计算出为2
int i= indexFor(hash, table.length);
如图1：
图1（借用网上的图）
③.因为hashMap长度有限，在所难免计算出来的数组索引会出现冲突，还及得前面说过hashMap底层是通过数组与链表结构组合实现的数据结构吗？此时我们就可以用链表的方式去解决。HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，首先会判断key是否相等，如果相同则替换原来的值（hashCode和equals进行比较两个key是否相同）。如果不相等则会插入到下一个entry节点（使用的头插法，因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。），如图2：
图2
2.Get方法的原理
①.根据key计算出hash值，
int hash= hash(key);
②.通过hash值与table数组的长度按位运算计算出插入table位置的索引,假设计算出为2
int i= indexFor(hash, table.length);
由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这个时候就会顺着对应链表的头节点一个一个往下找，例如：key="name"，头节点显然不是我们想要的结果，则顺着头节点，Next往下找，正式我们想要找的结果
图3
3.我们来看看HashMap的源码(jdk1.7)
图4
1.put方法源码
图5
①:判断key是否为空，如果key为null，则插入table[0](null总是放在数组的第一个链表中)的位置，因为HashMap数组下标是从1开始，预留的索引0则是为了储存空key
图6
②③根据key计算出hash值，通过hash值与table数组的长度按（位运算）计算出插入table位置的索引。
图7
④通过计算出的索引找到对应的数组位置。然后遍历链表。判断该位置的entry是否为null，如果不为空则判断key是否重复，如果重复则替换原来的值。不重复则在链表头结点插入该键值对（entry）
⑤看源码翻译过来的意思：记录该table修改的次数（至于为什么会出现这个这里就不做多说明，有兴趣的同学下来可以去了解下）。
⑥
参数说明
hash：hashCode
key：key
value：value
bucketIndex：table索引（链表所在的数组索引）
void addEntry(int hash, K key, V value, int bucketIndex)；
图8
createEntry(hash, key, value, bucketIndex);
/**
* The number of key-value mappings contained in this map.
*/
transient int size;//包含kery-value 数量
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e= table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);//插入 entry
size++;//
}
2.get源码
图9
如果key==，则直接返回数组的第一个链表中对应的值
如果key!=null 则getEntry(key);
图10
计算key 的hashCode，然后计算出table所在的索引。从头结点next往下查找。
网友评论