java篇 - java集合类框架详解 - 《JAVA技术开发》

HashMap实现原理
Hashtable实现原理

HashMap实现原理

参考文献来自于：https://segmentfault.com/a/1190000017362670?utm_source=tag-newest

public V put(K key, V value) {
    //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间）
    //入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
    if (table == EMPTY_TABLE) {
      inflateTable(threshold);
    }
    //如果key为null，存储位置为table[0]或table[0]的冲突链上
    if (key == null)
      return putForNullKey(value);
    //对key的hashcode进一步计算，确保散列均匀
    int hash = hash(key);
    //获取在table中的实际位置
    int i = indexFor(hash, table.length);
    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;
      }
    }
    //保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    modCount++;
    //新增一个entry
    addEntry(hash, key, value, i);
    return null;
}
//如果key为null,会把数组第0个位置的value进行替换
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;
}

modCount字段的作业

ArrayList、LinkedList、HashMap中都有一个字段叫modCount 结构上的修改指的是那些改变了list的长度大小或者使得遍历过程中产生不正确的结果的其它方式。该字段被Iterator以及ListIterator的实现类所使用，如果该值被意外更改，Iterator或者ListIterator 将抛出ConcurrentModificationException异常这是jdk在面对迭代遍历的时候为了避免不确定性而采取的快速失败原则。子类对此字段的使用是可选的，如果子类希望支持快速失败，只需要覆盖该字段相关的所有方法即可

使用hash函数通过>>>(位移) 和 ^(异或) 获取h(哈希值)

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

通过h(哈希值)和length（数组长度）获取下标，

static int indexFor(int h, int length) {
    return h & (length-1);
}

其中 h&（length-1）保证获取的index一定在数组范围内举例： 10010 & 01111=00010 也就是 18 & 16 = 2 最终计算出的index=2。有些版本的对于此处的计算会使用取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些

所以最终存储位置的确定流程是这样的：

当发生哈希冲突的并且size大于阀值的时候,需要进行扩容，扩容新建一个长度位之前数组的2倍新数组，如果将当前的Entry数组全部传过去，扩容后的数组长度为之前的两倍，所以扩容相对于来说，是一个比较耗资源的操作。

void addEntry(int hash, K key, V value, int bucketIndex) {
    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);
}

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:哈希值 threshold:阈值当table == {}时，该值为初始容量（初始容量默认为16）,当table被填充了,也就是为table分配内存空间后,threshold一般为capacity*loadFactory。HashMap在进行扩容时需要参考threshold bucketIndex:数组下标

数组长度一定是2的次幂

void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }
  Entry[] newTable = new Entry[newCapacity];
  //重新计算下标
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  //新的扩容数组
  table = newTable;
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

如果数组进行扩容，数组长度发生了变化，而存储位置 h & (length-1) -> index 也可能发生变化需要重新计算index

void transfer(Entry[] newTable, boolean rehash) {
  int newCapacity = newTable.length;
  for (Entry<K,V> e : table) {
    while(null != e) {
      Entry<K,V> next = e.next;
      if (rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
      }
      int i = indexFor(e.hash, newCapacity);
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
    }
  }
}

transfer 这个方法会将老数据逐个遍历,扔到新的扩容数组中，我们的数组索引位置是通过对key的hashcode进行 hash扰乱运算后,再通过和length-1进行位运算得到最终数组索引位置

扩容前： 16(十进制) = 10000(二进制) length -1 = 15 15(十进制) = 1111(二进制) 扩容后： 32(十进制) = 100000(二进制) length -1 = 31 31(十进制) = 11111(二进制)

get方法通过key值返回对应value，如果key为null，直接去table[0]处检索

public V get(Object key) {
  ////如果key为null,则直接去table[0]处去检索即可。
  if (key == null)
    return getForNullKey();
  Entry<K,V> entry = getEntry(key);

  return null == entry ? null : entry.getValue();
}

get方法的实现相对简单，key(hashcode)—>hash—>indexFor—>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    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;
}

要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过 equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null

Hashtable实现原理


public synchronized V put(K key, V value) {
    // 确保value不为null
    if (value == null) {
        throw new NullPointerException();
    }

    /*
     * 确保key在table[]是不重复的
     * 处理过程：
     * 1、计算key的hash值，确认在table[]中的索引位置
     * 2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
     */
    Entry tab[] = table;
    int hash = hash(key);    //计算key的hash值
    int index = (hash & 0x7FFFFFFF) % tab.length;     //确认该key的索引位置
    //迭代，寻找该key，替换
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    if (count >= threshold) {  //如果容器中的元素数量已经达到阀值，则进行扩容操作
        rehash();
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // 在索引位置处插入一个新的节点
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    //容器中元素+1
    count++;
    return null;
}

hashSeed是一个与实例相关的随机值，与hashCode进行异或运算，主要解决哈希冲突

private int hash(Object k) {
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

使用取模运算获取下标，如果key和hash相同,进行覆盖

int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
    if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
    }
}

protected void rehash() {
    //当前散列表的容量
    int oldCapacity = table.length;
    //当前散列表
    Entry<K,V>[] oldMap = table;

    //默认每次扩容的大小 = 原容量 * 2 +1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            //如果扩容的容量比限定的容量大，并且原容量等于MAX_ARRAY_SIZE,则返回不做扩容
            return;
        //如果扩容的容量比限定的容量大，并且原容量不等于MAX_ARRAY_SIZE,则修正扩容为限定值的最大值？
        newCapacity = MAX_ARRAY_SIZE;
    }
    //创建一个新的HashtableEntry一维数据,其容量为扩容之后的大小newCapacity
    Entry<K,V>[] newMap = new Entry[newCapacity];
    //HashTable修改此时加1
    modCount++;
    //设置扩容阀值为newCapacity * loadFactor , MAX_ARRAY_SIZE + 1 中的最小值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);

    table = newMap;
    //使用新的扩容大小重新计算数组下标值,并设置新的数组对应值
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

get方法通过key值返回对应value，如果key为null，会出现空指针

public synchronized V get(Object key) {
    //当前散列链表
    Entry tab[] = table;
    //hash值，取的是key的hashcode
    int hash = hash(key);
    //通过 (hash & 0x7FFFFFFF) % tab.length 计算出当前key所对应的散列地址即下标
    int index = (hash & 0x7FFFFFFF) % tab.length;
    //根据下标取出链表，遍历链表找到匹配值
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        //匹配条件是 hash 相等,且检点key相等
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}