可以看到，当我们给put()方法传递键和值时，HashMap会由key来调用hash()方法，返回键的hash值，计算Index后用于找到bucket（哈希桶）的位置来储存Entry对象。
如果两个对象key的hash值相同，那么它们的bucket位置也相同，但equals()不相同，添加元素时会发生hash碰撞，也叫hash冲突，HashMap使用链表来解决碰撞问题。
分析源码可知，put()时，HashMap会先遍历table数组，用hash值和equals()判断数组中是否存在完全相同的key对象， 如果这个key对象在table数组中已经存在，就用新的value代替老的value。如果不存在，就创建一个新的Entry对象添加到table[ i ]处。
如果该table[ i ]已经存在其他元素，那么新Entry对象将会储存在bucket链表的表头，通过next指向原有的Entry对象，形成链表结构（hash碰撞解决方案）。
Entry数据结构源码如下（HashMap内部类）：
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; /** 指向下一个元素的引用 */ Entry<K,V> next; int hash; /** * 构造方法为Entry赋值 */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } ... ... }
形成单链表的核心代码如下：
/** * 将Entry添加到数组bucketIndex位置对应的哈希桶中，并判断数组是否需要扩容 */ void addEntry(int hash, K key, V value, int 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); } /** * 在链表中添加一个新的Entry对象在链表的表头 */ 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++; }
（put方法执行过程）
get方法如果两个不同的key的hashcode相同，两个值对象储存在同一个bucket位置，要获取value，我们调用get()方法，HashMap会使用key的hashcode找到bucket位置，因为HashMap在链表中存储的是Entry键值对，所以找到bucket位置之后，会调用key的equals()方法，按顺序遍历链表的每个 Entry，直到找到想获取的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那HashMap必须循环到最后才能找到该元素。
get()方法源码如下：
public V get(Object key) { // 若key为null，遍历table[0]处的链表（实际上要么没有元素，要么只有一个Entry对象），取出key为null的value if (key == null) return getForNullKey(); // 若key不为null，用key获取Entry对象 Entry<K,V> entry = getEntry(key); // 若链表中找到的Entry不为null，返回该Entry中的value return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } // 计算key的hash值 int hash = (key == null) ? 0 : hash(key); // 计算key在数组中对应位置，遍历该位置的链表 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; // 若key完全相同，返回链表中对应的Entry对象 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } // 链表中没找到对应的key，返回null return null; }
三、hash算法