一 特性

  • 键之间的比较不是食用equals 而是使用==也就是比较内存地址
  • 可以使用这个存储代理对象
  • 支持null值的key和value
  • 是非线程安全的，可以借助Collections.synchronizedMap 来获得线程安全的实例

  • 采用开放寻址方式解决hash冲突

    二 属性

    1. /**
    2.    * The initial capacity used by the no-args constructor.
    3.    * MUST be a power of two.  The value 32 corresponds to the
    4.    * (specified) expected maximum size of 21, given a load factor
    5.    * of 2/3.  无参数构造函数使用这个默认值初始化
    6.    */
    7.   private static final int DEFAULT_CAPACITY = 32;
    9.   /**
    10.    * The minimum capacity, used if a lower value is implicitly specified
    11.    * by either of the constructors with arguments.  The value 4 corresponds
    12.    * to an expected maximum size of 2, given a load factor of 2/3.
    13.    * MUST be a power of two.  最小的容量
    14.    */
    15.   private static final int MINIMUM_CAPACITY = 4;
    17.   /**
    18.    * The maximum capacity, used if a higher value is implicitly specified
    19.    * by either of the constructors with arguments.
    20.    * MUST be a power of two <= 1<<29.
    21.    *
    22.    * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
    23.    * because it has to have at least one slot with the key == null
    24.    * in order to avoid infinite loops in get(), put(), remove()
    25.    */
    26.   private static final int MAXIMUM_CAPACITY = 1 << 29;
    28.   /**
    29.    * The table, resized as necessary. Length MUST always be a power of two.
    30.    */
    31.   transient Object[] table; // non-private to simplify nested class access
    33.   /**
    34.    * The number of key-value mappings contained in this identity hash map.
    35.    *
    36.    * @serial
    37.    */
    38.   int size;
    40.   /**
    41.    * The number of modifications, to support fast-fail iterators
    42.    */
    43.   transient int modCount;
    45.   /**
    46.    * Value representing null keys inside tables.
    47.    */
    48.   static final Object NULL_KEY = new Object();

    三 重要方法

  • hash

    • 计算hash值的方法 ((h << 1) - (h << 8)) & (length - 1)
  • nextKeyIndex
    • 计算给定位置的hash冲突的解决为止，采用开放寻址方式解决hash冲突

  • resize

    • 扩容方法 扩容的大小是原来大小的两倍，会创建一个新的数组并将每个元素重进进行hash

      四 添加

      1. public V put(K key, V value) {
      2.    final Object k = maskNull(key);
      4.    retryAfterResize: for (;;) {
      5.        final Object[] tab = table;
      6.        final int len = tab.length;
      7.        int i = hash(k, len);
      9.        //这里的循环的为开放寻址法的地址  i = nextKeyIndex(i, len) 来控制的
      10.        for (Object item; (item = tab[i]) != null;
      11.             i = nextKeyIndex(i, len)) {
      12.            if (item == k) {
      13.                @SuppressWarnings("unchecked")
      14.                    V oldValue = (V) tab[i + 1];
      15.                tab[i + 1] = value;
      16.                return oldValue;
      17.            }
      18.        }
      20.        final int s = size + 1;
      21.        // Use optimized form of 3 * s.
      22.        // Next capacity is len, 2 * current capacity.
      23.        //判断当前已经存在的元素的 2.5倍是否大于数组的长度  扩容后重新retryAfterResize
      24.        if (s + (s << 1) > len && resize(len))
      25.            continue retryAfterResize;
      27.        modCount++;
      28.        tab[i] = k;
      29.        tab[i + 1] = value;
      30.        size = s;
      31.        return null;
      32.    }
      33. }

      五 删除

      1. public V remove(Object key) {
      2.    Object k = maskNull(key);
      3.    Object[] tab = table;
      4.    int len = tab.length;
      5.    int i = hash(k, len);
      7.    //具体的删除过程
      8.    while (true) {
      9.        Object item = tab[i];
      10.        if (item == k) {
      11.            modCount++;
      12.            size--;
      13.            @SuppressWarnings("unchecked")
      14.                V oldValue = (V) tab[i + 1];
      15.            tab[i + 1] = null;
      16.            tab[i] = null;
      17.            closeDeletion(i);
      18.            return oldValue;
      19.        }
      20.        if (item == null)
      21.            return null;
      22.        i = nextKeyIndex(i, len);
      23.    }
      24. }

      六 获取

      1. public V get(Object key) {
      2.    Object k = maskNull(key);
      3.    Object[] tab = table;
      4.    int len = tab.length;
      5.    int i = hash(k, len);
      6.    while (true) {
      7.        Object item = tab[i];
      8.        if (item == k)
      9.            return (V) tab[i + 1];
      10.        if (item == null)
      11.            return null;
      12.        //如果都不等于则代表发生了hash冲突，使用开放寻址方式找下一个位置
      13.        i = nextKeyIndex(i, len);
      14.    }
      15. }

      七 resize

      1. private boolean resize(int newCapacity) {
      2.    // assert (newCapacity & -newCapacity) == newCapacity; // power of 2 新大小是原来的两倍
      3.    int newLength = newCapacity * 2;
      5.    Object[] oldTable = table;
      6.    int oldLength = oldTable.length;
      7.    if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
      8.        if (size == MAXIMUM_CAPACITY - 1)
      9.            throw new IllegalStateException("Capacity exhausted.");
      10.        return false;
      11.    }
      12.    if (oldLength >= newLength)
      13.        return false;
      15.    Object[] newTable = new Object[newLength];
      17.    //重新进行更新hash槽位的过程
      18.    for (int j = 0; j < oldLength; j += 2) {
      19.        Object key = oldTable[j];
      20.        if (key != null) {
      21.            Object value = oldTable[j+1];
      22.            oldTable[j] = null;
      23.            oldTable[j+1] = null;
      24.            int i = hash(key, newLength);
      25.            while (newTable[i] != null)
      26.                i = nextKeyIndex(i, newLength);
      27.            newTable[i] = key;
      28.            newTable[i + 1] = value;
      29.        }
      30.    }
      31.    table = newTable;
      32.    return true;
      33. }