• HashTable与HashMap到底有啥区别？来看看源码分析分析

    看源码之前，我们知道HashTable是同步的，是线程安全的。HashMap是不同步的，也就是线程不安全的。且常见的资料书与八股文中都会讲到二者的默认初始容量与扩容机制。我们来看看源码，看看能找出什么端倪。

    哈希表HashTable继承字典Dictionary，实现Map接口，cloneable克隆接口，serializable序列化接口。

    源码如下：

    1. public class Hashtable
    2.     extends Dictionary
    3.     implements Map, Cloneable, java.io.Serializable {
    4.  
    5.     private transient Entry[] table;
    6.  
    7.     private transient int count;
    8.  
    9.     private int threshold;
    10.  
    11.     private float loadFactor;
    12.    
    13.     private transient int modCount = 0;
    14.  
    15.     /** use serialVersionUID from JDK 1.0.2 for interoperability */
    16.     @java.io.Serial
    17.     private static final long serialVersionUID = 1421746759512286392L;
    18.  
    19.    
    20.     public Hashtable(int initialCapacity, float loadFactor) {
    21.         if (initialCapacity < 0)
    22.             throw new IllegalArgumentException("Illegal Capacity: "+
    23.                                                initialCapacity);
    24.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
    25.             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    26.  
    27.         if (initialCapacity==0)
    28.             initialCapacity = 1;
    29.         this.loadFactor = loadFactor;
    30.         table = new Entry[initialCapacity];
    31.         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    32.     }
    33.  
    34.    
    35.     public Hashtable(int initialCapacity) {
    36.         this(initialCapacity, 0.75f);
    37.     }
    38.  
    39.    
    40.     public Hashtable() {
    41.         this(11, 0.75f);
    42.     }
    43.  
    44.   
    45.     public Hashtable(Map t) {
    46.         this(Math.max(2*t.size(), 11), 0.75f);
    47.         putAll(t);
    48.     }
    49.  
    50.     
    51.     Hashtable(Void dummy) {}
    52.  
    53.     
    54.     public synchronized int size() {
    55.         return count;
    56.     }
    57.  
    58.   
    59.     public synchronized boolean isEmpty() {
    60.         return count == 0;
    61.     }
    62.  
    63.  
    64.     public synchronized Enumeration keys() {
    65.         return this.getEnumeration(KEYS);
    66.     }
    67.  
    68.   
    69.     public synchronized Enumeration elements() {
    70.         return this.getEnumeration(VALUES);
    71.     }
    72.  
    73.     public synchronized boolean contains(Object value) {
    74.         if (value == null) {
    75.             throw new NullPointerException();
    76.         }
    77.  
    78.         Entry tab[] = table;
    79.         for (int i = tab.length ; i-- > 0 ;) {
    80.             for (Entry e = tab[i] ; e != null ; e = e.next) {
    81.                 if (e.value.equals(value)) {
    82.                     return true;
    83.                 }
    84.             }
    85.         }
    86.         return false;
    87.     }
    88.  
    89.    
    90.     public boolean containsValue(Object value) {
    91.         return contains(value);
    92.     }
    93.  
    94.    
    95.     public synchronized boolean containsKey(Object key) {
    96.         Entry tab[] = table;
    97.         int hash = key.hashCode();
    98.         int index = (hash & 0x7FFFFFFF) % tab.length;
    99.         for (Entry e = tab[index] ; e != null ; e = e.next) {
    100.             if ((e.hash == hash) && e.key.equals(key)) {
    101.                 return true;
    102.             }
    103.         }
    104.         return false;
    105.     }
    106. .............此处省略下面的其他方法.........
    107.  
    108. }

    跟着源码看多了的兄弟们肯定了解这其中透露的信息与原理，我们一起研究一下hashtable的构造方法：

    1.  public Hashtable(int initialCapacity, float loadFactor) {
    2.         if (initialCapacity < 0)
    3.             throw new IllegalArgumentException("Illegal Capacity: "+
    4.                                                initialCapacity);
    5.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
    6.             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    7.  
    8.         if (initialCapacity==0)
    9.             initialCapacity = 1;
    10.         this.loadFactor = loadFactor;
    11.         table = new Entry[initialCapacity];
    12.         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    13.     }
    14.  
    15.    
    16.     public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}
    17.     
    18.     public Hashtable() {this(11, 0.75f);}
    19.  
    20.     public Hashtable(Map t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);}
    21.     Hashtable(Void dummy) {}

    源码给出的构造方法总共是五种，其中默认的没有给初始化容量initialCapacity作为构造参数的方法中显示this(11，0.75f)也就是说默认的容量是11，负载系数是0.75f。我们还需要注意的是第一个构造方法中显示出来的

    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

     我们的散列控制阀threshold，负载因子乘以初始化容量的值与

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    也即是Integer能代表的最大数2的31次方减一再加一（就是拿当前可装载的最多数与2的31次方比较）相比较，如果表的大小比他大时整个哈希表会重新散列，这个就是比较有意思的了，因为会涉及扩容，看看源码中的rehash方法：

    1. @SuppressWarnings("unchecked")
    2.     protected void rehash() {
    3.         int oldCapacity = table.length;
    4.         Entry[] oldMap = table;
    5.  
    6.         // overflow-conscious code
    7.         int newCapacity = (oldCapacity << 1) + 1;
    8.         if (newCapacity - MAX_ARRAY_SIZE > 0) {
    9.             if (oldCapacity == MAX_ARRAY_SIZE)
    10.                 // Keep running with MAX_ARRAY_SIZE buckets
    11.                 return;
    12.             newCapacity = MAX_ARRAY_SIZE;
    13.         }
    14.         Entry[] newMap = new Entry[newCapacity];
    15.  
    16.         modCount++;
    17.         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    18.         table = newMap;
    19.  
    20.         for (int i = oldCapacity ; i-- > 0 ;) {
    21.             for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
    22.                 Entry e = old;
    23.                 old = old.next;
    24.  
    25.                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
    26.                 e.next = (Entry)newMap[index];
    27.                 newMap[index] = e;
    28.             }
    29.         }
    30.     }
    31.  
    32.     private void addEntry(int hash, K key, V value, int index) {
    33.         Entry tab[] = table;
    34.         if (count >= threshold) {
    35.             // Rehash the table if the threshold is exceeded
    36.             rehash();
    37.  
    38.             tab = table;
    39.             hash = key.hashCode();
    40.             index = (hash & 0x7FFFFFFF) % tab.length;
    41.         }
    42.  
    43.         // Creates the new entry.
    44.         @SuppressWarnings("unchecked")
    45.         Entry e = (Entry) tab[index];
    46.         tab[index] = new Entry<>(hash, key, value, e);
    47.         count++;
    48.         modCount++;
    49.     }

    其实我们能发现，一般扩容走的都是上面的 

    int newCapacity = (oldCapacity << 1) + 1;

    到

    Entry[] newMap = new Entry[newCapacity];

            modCount++;
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;

    不会超过integer所能代表的最大数的，所以扩容机制就是先比较有没有2的31次方大，没有就扩容成2倍的旧容量加1。

    我们再回头看看除了hashtable的构造方法外的其他方法，基本上独立搓出来的方法都是添加了同步关键字synchronized ：

    1. public synchronized int size() {
    2.         return count;
    3.     }
    4.  
    5.   
    6.     public synchronized boolean isEmpty() {
    7.         return count == 0;
    8.     }
    9.  
    10.  
    11.     public synchronized Enumeration keys() {
    12.         return this.getEnumeration(KEYS);
    13.     }
    14.  
    15.   
    16.     public synchronized Enumeration elements() {
    17.         return this.getEnumeration(VALUES);
    18.     }
    19.  
    20.     public synchronized boolean contains(Object value) {
    21.         if (value == null) {
    22.             throw new NullPointerException();
    23.         }
    24.  
    25.         Entry tab[] = table;
    26.         for (int i = tab.length ; i-- > 0 ;) {
    27.             for (Entry e = tab[i] ; e != null ; e = e.next) {
    28.                 if (e.value.equals(value)) {
    29.                     return true;
    30.                 }
    31.             }
    32.         }
    33.         return false;
    34.     }

    这就是同步的且线程安全的原因，但是同步又会很大的影响速度，在并发要求不高的环境里，它的效率要远远低于hashmap，但是源码里给出了解决方案：

    As of the Java 2 platform v1.2, this class was retrofitted to implement the Map interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Hashtable is synchronized. If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

    从 Java 2 平台 v1.2 开始，该类被改进为实现Map接口，使其成为Java Collections Framework的成员。与新的集合实现不同， Hashtable是同步的。如果不需要线程安全的实现，建议使用HashMap代替Hashtable 。如果需要线程安全的高并发实现，则建议使用java.util.concurrent.ConcurrentHashMap代替Hashtable 。

    对于这个ConcurrentHashMap 的源码以后再说！

    HashMap哈希图继承了AbstractMap抽象图类，实现了Map接口，cloneable接口，serilizable接口。

    源码如下：

    1. public class HashMap extends AbstractMap
    2.     implements Map, Cloneable, Serializable {
    3.  
    4.     @java.io.Serial
    5.     private static final long serialVersionUID = 362498820763181265L;
    6.  
    7.   
    8.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    9.  
    10.    
    11.     static final int MAXIMUM_CAPACITY = 1 << 30;
    12.  
    13.     
    14.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
    15.  
    16.    
    17.     static final int TREEIFY_THRESHOLD = 8;
    18.  
    19.   
    20.     static final int UNTREEIFY_THRESHOLD = 6;
    21.  
    22.    
    23.     static final int MIN_TREEIFY_CAPACITY = 64;
    24.  
    25.     static class Node implements Map.Entry {
    26.         final int hash;
    27.         final K key;
    28.         V value;
    29.         Node next;
    30.  
    31.         Node(int hash, K key, V value, Node next) {
    32.             this.hash = hash;
    33.             this.key = key;
    34.             this.value = value;
    35.             this.next = next;
    36.         }
    37.  
    38.         public final K getKey()        { return key; }
    39.         public final V getValue()      { return value; }
    40.         public final String toString() { return key + "=" + value; }
    41.  
    42.         public final int hashCode() {
    43.             return Objects.hashCode(key) ^ Objects.hashCode(value);
    44.         }
    45.  
    46.         public final V setValue(V newValue) {
    47.             V oldValue = value;
    48.             value = newValue;
    49.             return oldValue;
    50.         }
    51.  
    52.         public final boolean equals(Object o) {
    53.             if (o == this)
    54.                 return true;
    55.  
    56.             return o instanceof Map.Entry e
    57.                     && Objects.equals(key, e.getKey())
    58.                     && Objects.equals(value, e.getValue());
    59.         }
    60.     }
    61.  
    62.  
    63.     static final int hash(Object key) {
    64.         int h;
    65.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    66.     }
    67.  
    68.   
    69.     static Class comparableClassFor(Object x) {
    70.         if (x instanceof Comparable) {
    71.             Class c; Type[] ts, as; ParameterizedType p;
    72.             if ((c = x.getClass()) == String.class) // bypass checks
    73.                 return c;
    74.             if ((ts = c.getGenericInterfaces()) != null) {
    75.                 for (Type t : ts) {
    76.                     if ((t instanceof ParameterizedType) &&
    77.                         ((p = (ParameterizedType) t).getRawType() ==
    78.                          Comparable.class) &&
    79.                         (as = p.getActualTypeArguments()) != null &&
    80.                         as.length == 1 && as[0] == c) // type arg is c
    81.                         return c;
    82.                 }
    83.             }
    84.         }
    85.         return null;
    86.     }
    87.  
    88.   
    89.     @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    90.     static int compareComparables(Class kc, Object k, Object x) {
    91.         return (x == null || x.getClass() != kc ? 0 :
    92.                 ((Comparable)k).compareTo(x));
    93.     }
    94.  
    95.    
    96.     static final int tableSizeFor(int cap) {
    97.         int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    98.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    99.     }
    100.  
    101.     
    102.     transient Node[] table;
    103.  
    104.    
    105.     transient Set> entrySet;
    106.  
    107.  
    108.     transient int size;
    109.  
    110.     transient int modCount;
    111.  
    112.     int threshold;
    113.  
    114.     final float loadFactor;
    115.  
    116.     public HashMap(int initialCapacity, float loadFactor) {
    117.         if (initialCapacity < 0)
    118.             throw new IllegalArgumentException("Illegal initial capacity: " +
    119.                                                initialCapacity);
    120.         if (initialCapacity > MAXIMUM_CAPACITY)
    121.             initialCapacity = MAXIMUM_CAPACITY;
    122.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
    123.             throw new IllegalArgumentException("Illegal load factor: " +
    124.                                                loadFactor);
    125.         this.loadFactor = loadFactor;
    126.         this.threshold = tableSizeFor(initialCapacity);
    127.     }
    128.  
    129.   
    130.     public HashMap(int initialCapacity) {
    131.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    132.     }
    133.  
    134.     public HashMap() {
    135.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    136.     }
    137.  
    138.     public HashMap(Map m) {
    139.         this.loadFactor = DEFAULT_LOAD_FACTOR;
    140.         putMapEntries(m, false);
    141.     }
    142.  
    143.     final void putMapEntries(Map m, boolean evict) {
    144.         int s = m.size();
    145.         if (s > 0) {
    146.             if (table == null) { // pre-size
    147.                 float ft = ((float)s / loadFactor) + 1.0F;
    148.                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
    149.                          (int)ft : MAXIMUM_CAPACITY);
    150.                 if (t > threshold)
    151.                     threshold = tableSizeFor(t);
    152.             } else {
    153.                 // Because of linked-list bucket constraints, we cannot
    154.                 // expand all at once, but can reduce total resize
    155.                 // effort by repeated doubling now vs later
    156.                 while (s > threshold && table.length < MAXIMUM_CAPACITY)
    157.                     resize();
    158.             }
    159.  
    160.             for (Map.Entryextends K, ? extends V> e : m.entrySet()) {
    161.                 K key = e.getKey();
    162.                 V value = e.getValue();
    163.                 putVal(hash(key), key, value, false, evict);
    164.             }
    165.         }
    166.     }
    167. .................
    168.  
    169. }

    我们可以在这段源码里看到许多信息，比如默认的各参数的值：

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 1;
        static final int MAXIMUM_CAPACITY = 1 << 30;
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        static final int TREEIFY_THRESHOLD = 8;
        static final int UNTREEIFY_THRESHOLD = 6;
        static final int MIN_TREEIFY_CAPACITY = 64;

     扩容机制也可以在源码里找到：

    1. final Node[] resize() {
    2.         Node[] oldTab = table;
    3.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
    4.         int oldThr = threshold;
    5.         int newCap, newThr = 0;
    6.         if (oldCap > 0) {
    7.             if (oldCap >= MAXIMUM_CAPACITY) {
    8.                 threshold = Integer.MAX_VALUE;
    9.                 return oldTab;
    10.             }
    11.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    12.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
    13.                 newThr = oldThr << 1; // double threshold
    14.         }
    15.         else if (oldThr > 0) // initial capacity was placed in threshold
    16.             newCap = oldThr;
    17.         else {               // zero initial threshold signifies using defaults
    18.             newCap = DEFAULT_INITIAL_CAPACITY;
    19.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    20.         }
    21.         if (newThr == 0) {
    22.             float ft = (float)newCap * loadFactor;
    23.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    24.                       (int)ft : Integer.MAX_VALUE);
    25.         }
    26.         threshold = newThr;
    27.         @SuppressWarnings({"rawtypes","unchecked"})
    28.         Node[] newTab = (Node[])new Node[newCap];
    29.         table = newTab;
    30.         if (oldTab != null) {
    31.             for (int j = 0; j < oldCap; ++j) {
    32.                 Node e;
    33.                 if ((e = oldTab[j]) != null) {
    34.                     oldTab[j] = null;
    35.                     if (e.next == null)
    36.                         newTab[e.hash & (newCap - 1)] = e;
    37.                     else if (e instanceof TreeNode)
    38.                         ((TreeNode)e).split(this, newTab, j, oldCap);
    39.                     else { // preserve order
    40.                         Node loHead = null, loTail = null;
    41.                         Node hiHead = null, hiTail = null;
    42.                         Node next;
    43.                         do {
    44.                             next = e.next;
    45.                             if ((e.hash & oldCap) == 0) {
    46.                                 if (loTail == null)
    47.                                     loHead = e;
    48.                                 else
    49.                                     loTail.next = e;
    50.                                 loTail = e;
    51.                             }
    52.                             else {
    53.                                 if (hiTail == null)
    54.                                     hiHead = e;
    55.                                 else
    56.                                     hiTail.next = e;
    57.                                 hiTail = e;
    58.                             }
    59.                         } while ((e = next) != null);
    60.                         if (loTail != null) {
    61.                             loTail.next = null;
    62.                             newTab[j] = loHead;
    63.                         }
    64.                         if (hiTail != null) {
    65.                             hiTail.next = null;
    66.                             newTab[j + oldCap] = hiHead;
    67.                         }
    68.                     }
    69.                 }
    70.             }
    71.         }
    72.         return newTab;
    73.     }

    关于扩容方法的文档解释如下：

    Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

    初始化或加倍表大小。如果为空，则按照字段阈值中保存的初始容量目标进行分配。否则，因为我们使用二次幂展开，每个 bin 中的元素必须保持相同的索引，或者在新表中以二次幂的偏移量移动。

    也就是说它的扩容机制就是按照二倍扩容。其实它的源码里也有它底层采用的数据结构，但是这里我主要寻找的是扩容机制，所以就先不聊这个。

  • 相关阅读:
    大数据学习1.1-Centos8网络配置
    SpringBoot 集成RabbitMQ 实现钉钉日报定时发送功能
    NameNode (NN) 和SecondaryNameNode (2NN)工作机制
    mockjs的基本使用和登录跳转到主页加折叠事件
    Ubuntu学习---跟着绍发学linux课程记录（第二部分）
    JQuery+webpack+echarts构建可视化开发环境
    std::make_shared和new初始化智能指针的区别
    运动控制比例随动系统学习笔记
    游戏找不到msvcr100dll怎么办，分享5个有效修复方法
    8.strtok函数
  • 原文地址：https://blog.csdn.net/m0_59588838/article/details/126282172