1.7的HashMap是用数组+链表实现的
04-13 HashMap-1.7JDK - 图1

参数

  1.     //默认容量16
  2.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
  4.     //最大容量
  5.     static final int MAXIMUM_CAPACITY = 1 << 30;
  7.     //默认加载因子
  8.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  10.     //空数组实例
  11.     static final Entry<?,?>[] EMPTY_TABLE = {};
  13.     //hashMap存储元素的数组
  14.     transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
  16.     //hashMap存的元素数量（包括链表的元素）
  17.     transient int size;
  19.       //阈值，用在扩容时判断，capacity * load factor
  20.     int threshold;
  22.     //加载因子
  23.     final float loadFactor;

Put方法

  1. public V put(K key, V value) {
  2.         if (table == EMPTY_TABLE) {
  3.             //初始化hashMap
  4.             inflateTable(threshold);
  5.         }
  6.         if (key == null)
  7.             return putForNullKey(value);
  8.         //计算hash值
  9.         int hash = hash(key);
  10.         //计算key在数组的索引index
  11.         int i = indexFor(hash, table.length);
  12.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  13.             Object k;
  14.             //如果put的新值，hash值已经存在，而且key也相同，则替换值，返回旧值
  15.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  16.                 V oldValue = e.value;
  17.                 e.value = value;
  18.                 e.recordAccess(this);
  19.                 return oldValue;
  20.             }
  21.         }
  23.         modCount++;
  25.         addEntry(hash, key, value, i);
  26.         return null;
  27.     }
  29. //计算索引位置
  30. static int indexFor(int h, int length) {
  31.         //用hash值和（数组长度-1）进行与&运行
  32.         //假设数组长度是16，那length-1就是15，转换成2进制就是1111
  33.         // 假设hash值是   1101 1001
  34.         //             & 0000 1111
  35.         //               0000 1001
  36.         //最后得出得index是9，这样可以保证不会数组越界和均匀分布
  37.         return h & (length-1);
  38.     }
  40. //初始化hashMap的数组
  41. private void inflateTable(int toSize) {
  42.         // 要保证长度是2的幂次方，例如8，16，32...
  43.         int capacity = roundUpToPowerOf2(toSize);
  45.         //计算当前的阈值
  46.         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  47.         table = new Entry[capacity];
  48.         initHashSeedAsNeeded(capacity);
  49.     }
  51. //key为null时特殊处理
  52. //key=null，会把null放在hashMap数组的第一个位置，重复会覆盖
  53. private V putForNullKey(V value) {
  54.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  55.             if (e.key == null) {
  56.                 V oldValue = e.value;
  57.                 e.value = value;
  58.                 e.recordAccess(this);
  59.                 return oldValue;
  60.             }
  61.         }
  62.         modCount++;
  63.         addEntry(0, null, value, 0);
  64.         return null;
  65.     }
  67. void addEntry(int hash, K key, V value, int bucketIndex) {
  68.         //判断扩容
  69.         if ((size >= threshold) && (null != table[bucketIndex])) {
  70.             //每次扩容数组容量的一倍
  71.             resize(2 * table.length);
  72.             hash = (null != key) ? hash(key) : 0;
  73.             bucketIndex = indexFor(hash, table.length);
  74.         }
  76.         createEntry(hash, key, value, bucketIndex);
  77.     }
  79. void createEntry(int hash, K key, V value, int bucketIndex) {
  80.         //获取当前索引位置的值
  81.         Entry<K,V> e = table[bucketIndex];
  82.         //创建一个entry，并把entry的next节点指向e（头插法）
  83.         //然后把当前数组索引位置的值赋值为新创建的entry
  84.         table[bucketIndex] = new Entry<>(hash, key, value, e);
  85.         size++;
  86.     }