HashMap原理解析

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;
    }