1、HashMap底层原理分析（put、get方法）
HashMap底层是通过数组加链表的结构来实现的。HashMap通过计算key的hashCode来计算hash值，只要hashCode一样，那hash值就是相同的。当hash值相同时，就会出现hash冲突，HashMap通过链表来解决冲突。
原理图：
实例：
import java.util.HashMap; import java.util.Map; public class HashMapTest { public static void main(String[] args) { Map<String, String> map = new HashMap<>(); map.put("fruit", "apple"); System.out.println(map.get("fruit"));
1、put方法分析
//添加键值对方法 public V put(K key, V value) { //如果key为null，则hash值为0，将这个entry放在索引为0的地方，即table[0] if (key == null) return putForNullKey(value); //key不为null int hash = hash(key.hashCode());//计算key的hashCode的hash值 int i = indexFor(hash, table.length);//返回hash值所在的索引位置 //遍历table[i]处的Entry，若存在key相同并且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))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //修改标记+1,然后进行元素添加操作 modCount++; addEntry(hash, key, value, i);//将包含特定key、value和hash值的entry添加到特定的桶中 return null; } //添加key为null的元素 private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
2、get方法分析
/** * 返回映射的key对应的value值，若map不包含该key，返回null */ public V get(Object key) { if (key == null)//获取key为null的value值 return getForNullKey(); int hash = hash(key.hashCode());//计算key的hashCode的hash值 //遍历数组中对应hash值的Entry链表，若Entry元素的hash值与hashCode的hash值相等并且key与查找的key相等，则返回此Entry元素的value值 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.equals(k))) return e.value; } return null; }
