Java中的HashMap原理分析

  /**
     * Min capacity (other than zero) for a HashMap. Must be a power of two
     * greater than 1 (and less than 1 << 30).
     */
    private static final int MINIMUM_CAPACITY = 4;

    /**
     * An empty table shared by all zero-capacity maps (typically from default
     * constructor). It is never written to, and replaced on first put. Its size
     * is set to half the minimum, so that the first resize will create a
     * minimum-sized table.
     */
    private static final Entry[] EMPTY_TABLE
            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

     /**
     * Constructs a new empty {@code HashMap} instance.
     */
    @SuppressWarnings("unchecked")
    public HashMap() {
        table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
        threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
    }

可见，HashMap的无参构造方法默认会创建一个大小为2的数组。
...版本太旧，就不往下分析了。

JDK1.6源码分析

https://blog.csdn.net/rocksteadypro/article/details/80082822

JDK1.7源码分析

https://www.cnblogs.com/xiaolovewei/p/7993521.html

https://www.cnblogs.com/xiaozhongfeixiang/archive/2019/09/23/11548563.html

需要注意的点：

key是如何计算出数组的下标的

image.png

哈希值求数组下标
```
hash & (tab.length - 1);
```
扩容为啥是2的倍数，和上面这个公式也是相关的：https://blog.csdn.net/ptsx0607/article/details/68945883,保证了散列的均匀性,哈希碰撞的机率就会减小。

头插法与链表
https://blog.csdn.net/insomsia/article/details/88367436
看put方法：

    @Override public V put(K key, V value) {
      if (key == null) {
          return putValueForNullKey(value);
      }

      int hash = secondaryHash(key);
      HashMapEntry<K, V>[] tab = table;
      int index = hash & (tab.length - 1);
      for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
          if (e.hash == hash && key.equals(e.key)) {  
              preModify(e);
              V oldValue = e.value;
              e.value = value;
              return oldValue;
          }
      }

      // No entry for (non-null) key is present; create one
      modCount++;
      if (size++ > threshold) {
          tab = doubleCapacity();
          index = hash & (tab.length - 1);
      }
      addNewEntry(key, value, hash, index);
      return null;
  }

重复元素判断:hash相同，key相同的肯定是同一个元素。

e.hash == hash && key.equals(e.key)

但是可能不同的元素hash值不一样，算出的index却一样，但是又不是同一个元素(这就是哈希碰撞问题，哈希算法无法逃避这个问题)，数组中的这个索引位置已经被占据了，那么我怎么存储这个新的元素呢？
请看HashMapEntry这个类：

image.png
再看添加HashMapEntry的方法：

void addNewEntry(K key, V value, int hash, int index) {
     table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
         this.key = key;
         this.value = value;
         this.hash = hash;
         this.next = next;
     }

对于addNewEntry方法
如果index处本身没有元素占据，此时table[index]就是null。
那么直接就添加一个HashMapEntry元素，它的next指针指向原来Index位置的元素，也就是null；

如果index处本身有元素，也就是哈希冲突了，
那么直接就添加一个HashMapEntry元素，它的next指针指向原来Index位置的元素，也就是哈希冲突的元素。头插法就是这么来的。

对于计算机专业的人来说，得出上面的结论可能不难。但是对于非计算机专业的我来说，慢慢的发现了数据结构之类，简直太美妙了！

哈希冲突
https://www.iteye.com/blog/xiaolu123456-1485349
https://www.nowcoder.com/discuss/151172

并发导致的死循环问题
https://blog.csdn.net/pange1991/article/details/82377980
https://www.jianshu.com/p/61a829fa4e49

Java中的HashMap原理分析

JDK各个版本的源码查看

HashMap的特性

各个版本的HashMap的区别

JDK1.8的HashMap实现

JDK1.7及以下的HashMap实现

JDK1.5源码分析

主干数组初始化

JDK1.6源码分析

JDK1.7源码分析

猜你喜欢

热点阅读