1、Hashtable-源码分析-底层数据结构

  1. 1、Hashtable-源码分析-底层数据结构：与HashMap底层数据结构一样、
  3. 2、Hashtable-源码中属性字段：
  4.     /**
  5.      * 键值对/Entry数组，每个Entry本质上是一个单向链表的表头
  6.      */
  7.     private transient Entry<?, ?>[] table;
  9.     /**
  10.      * 当前表中的Entry数量，如果超过了阈值，就会扩容，即调用rehash方法
  11.      */
  12.     private transient int count;
  14.     /**
  15.      * rehash阈值
  16.      *
  17.      * @serial
  18.      */
  19.     private int threshold;
  21.     /**
  22.      * 负载因子
  23.      *
  24.      * @serial
  25.      */
  26.     private float loadFactor;
  28.     /**
  29.      * 用来实现"fail-fast"机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行
  30.      * 迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出
  31.      * ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）。
  32.      */
  33.     private transient int modCount = 0;

2、Hashtable-源码分析-构造方法

  1. 1、Hashtable-源码分析-构造方法：有4个构造方法
  3. 2、源代码：
  4.     //默认构造函数,指定的容量大小是11；加载因子是0.75
  5.     public Hashtable() {
  6.         this(11, 0.75f);
  7.     }
  9.     //指定容量大小的构造函数,加载因子是0.75
  10.     public Hashtable(int initialCapacity) {
  11.         this(initialCapacity, 0.75f);
  12.     }
  14.     //指定容量大小和加载因子的构造函数
  15.     public Hashtable(int initialCapacity, float loadFactor) {
  16.         //验证初始容量,初始容量不能小于0
  17.         if (initialCapacity < 0)
  18.             throw new IllegalArgumentException("Illegal Capacity: "+
  19.                                                initialCapacity);
  20.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  21.             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  23.         if (initialCapacity==0)
  24.             initialCapacity = 1;
  25.         this.loadFactor = loadFactor;
  26.         //初始化table，获得大小为initialCapacity的table数组
  27.         table = new Entry<?,?>[initialCapacity];
  28.         //计算阀值
  29.         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  30.     }
  32.     //构造一个与给定的 Map 具有相同映射关系的新哈希表,容量是原来容量的两倍和11的最大值。
  33.     public Hashtable(Map<? extends K, ? extends V> t) {
  34.         //设置table容器大小，其值==t.size * 2 + 1 Vs 11的最大值
  35.         this(Math.max(2*t.size(), 11), 0.75f);
  36.         putAll(t);
  37.     }

3、Hashtable-源码分析-Entry类

  1. 1、Entry类，与其他Map实现类一样，Hashtable中Entry类实现了Map.Entry<K,V>。
  3. 2、源代码：
  4.     /**
  5.      * Hashtable bucket collision list entry
  6.      * 哈希表bucket冲突列表项
  7.      * Hashtable的Entry节点，它本质上是一个单向链表。
  8.      */
  9.     private static class Entry<K,V> implements Map.Entry<K,V> {
  10.         final int hash;
  11.         final K key;
  12.         V value;
  13.         Entry<K,V> next;
  15.         protected Entry(int hash, K key, V value, Entry<K,V> next) {
  16.             this.hash = hash;
  17.             this.key =  key;
  18.             this.value = value;
  19.             this.next = next;
  20.         }
  22.         @SuppressWarnings("unchecked")
  23.         protected Object clone() {
  24.             return new Entry<>(hash, key, value,
  25.                                   (next==null ? null : (Entry<K,V>) next.clone()));
  26.         }
  28.         // Map.Entry Ops
  30.         public K getKey() {
  31.             return key;
  32.         }
  34.         public V getValue() {
  35.             return value;
  36.         }
  38.         // 进行判断value是否为空，即不允许value为空，其实key也不能为空
  39.         public V setValue(V value) {
  40.             if (value == null)
  41.                 throw new NullPointerException();
  43.             V oldValue = this.value;
  44.             this.value = value;
  45.             return oldValue;
  46.         }
  48.         public boolean equals(Object o) {
  49.             if (!(o instanceof Map.Entry))
  50.                 return false;
  51.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  53.             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
  54.                (value==null ? e.getValue()==null : value.equals(e.getValue()));
  55.         }
  57.         public int hashCode() {
  58.             // 直接用hash进行异或，与HashMap不同
  59.             return hash ^ Objects.hashCode(value);
  60.         }
  62.         public String toString() {
  63.             return key.toString()+"="+value.toString();
  64.         }
  65.     }

4、Hashtable-源码分析-添加元素

  1. 1、Hashtable-源码分析-添加元素：.put()方法
  3. 2、源代码：
  4.     //添加元素，要求key和value都不能为null
  5.     public synchronized V put(K key, V value) {
  6.         // Make sure the value is not null
  7.         if (value == null) {
  8.             throw new NullPointerException();
  9.         }
  11.         /*
  12.          * 确保key在table[]是不重复的
  13.          * 处理过程：
  14.          *     1、计算key的hash值，确认在table[]中的索引位置
  15.          *     2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值。
  16.          */
  17.         Entry<?,?> tab[] = table;
  18.         //计算key的hash值
  19.         int hash = key.hashCode();
  20.         //确认该key的索引位置
  21.         //&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而 hash & 0x7FFFFFFF 后，只有符号外改变，而后面的位都不变。
  22.         int index = (hash & 0x7FFFFFFF) % tab.length;
  23.         @SuppressWarnings("unchecked")
  24.         Entry<K,V> entry = (Entry<K,V>)tab[index];
  25.         //迭代，寻找该key，替换
  26.         for(; entry != null ; entry = entry.next) {
  27.             if ((entry.hash == hash) && entry.key.equals(key)) {
  28.                 V old = entry.value;
  29.                 entry.value = value;
  30.                 return old;
  31.             }
  32.         }
  33.         //执行到这里，说明key没有重复，则进行插入操作
  34.         addEntry(hash, key, value, index);
  35.         //如果是插入全新的Entry的话，就返回空
  36.         return null;
  37.     }
  39.     /**
  40.         进行插入操作
  41.     */
  42.     private void addEntry(int hash, K key, V value, int index) {
  43.         modCount++;
  45.         Entry<?,?> tab[] = table;
  46.         //如果容器中的元素数量已经达到阀值，则进行扩容操作
  47.         if (count >= threshold) {
  48.             // Rehash the table if the threshold is exceeded
  49.             //扩容方法，见后续章节简介
  50.             rehash();
  52.             tab = table;
  53.             //计算key的索引
  54.             hash = key.hashCode();
  55.             index = (hash & 0x7FFFFFFF) % tab.length;
  56.         }
  58.         // Creates the new entry.
  59.         @SuppressWarnings("unchecked")
  60.         // 在索引位置处插入一个新的节点
  61.         Entry<K,V> e = (Entry<K,V>) tab[index];
  62.         tab[index] = new Entry<>(hash, key, value, e);
  63.         //容器中元素+1
  64.         count++;
  65.     }
  67. 3、.put()方法，执行过程：
  68.     3-1、计算key的hash值，根据hash值获得key在table数组中的索引位置，然后迭代该key处的Entry链表（我们暂且理解为链表），若该链表中存在一个这个的key对象，那么就直接替换其value值即可，否则在将改key-value节点插入该index索引位置处。
  70. 4、.put()方法，特殊点：
  71.     4-1、在put方法中，如果需要向table[]中添加Entry元素，会首先进行容量校验，如果容量已经达到了阀值，HashTable就会进行扩容处理rehash()。

5、Hashtable-源码分析-扩容方法

  1. 1、Hashtable-源码分析-扩容方法：.rehash();
  2. 2、源代码：
  3.     /**
  4.         在put方法中，如果需要向table[]中添加Entry元素，会首先进行容量校验，如果容量已经达到了阀值，HashTable就会进行扩容处理rehash()。
  5.     */
  6.     @SuppressWarnings("unchecked")
  7.     protected void rehash() {
  8.         //旧容量=链表的长度
  9.         int oldCapacity = table.length;
  10.         //获取旧链表，将老数组赋值给oldMap
  11.         Entry<?,?>[] oldMap = table;
  13.         // overflow-conscious code
  14.         //新容量=旧容量 * 2 + 1
  15.         int newCapacity = (oldCapacity << 1) + 1;
  16.         if (newCapacity - MAX_ARRAY_SIZE > 0) {
  17.             if (oldCapacity == MAX_ARRAY_SIZE)
  18.                 // Keep running with MAX_ARRAY_SIZE buckets
  19.                 return;
  20.             newCapacity = MAX_ARRAY_SIZE;
  21.         }
  22.         //新建一个size = newCapacity 的HashTable
  23.         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
  25.         modCount++;
  26.         //重新计算阀值：在新容量*加载因子和最大值 + 1之间取最小值
  27.         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  28.         table = newMap;
  29.         //将原来的元素拷贝到新的HashTable中
  30.         //双重遍历老数组，第一重遍历是遍历桶上的各个Entry，将老数组的节点移到新数组
  31.         for (int i = oldCapacity ; i-- > 0 ;) {
  32.             //第二重遍历是遍历桶上Entry后面接的链表
  33.             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
  35.                 //将old赋值给e，e代表遍历到的节点
  36.                 Entry<K,V> e = old;
  37.                 //old指向他的后继节点，下次遍历就遍历到后继节点了
  38.                 old = old.next;
  40.                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  41.                 //把新桶上已存在链表节点作为当前节点的后继节点
  42.                 e.next = (Entry<K,V>)newMap[index];
  43.                 //遍历到的节点放到新数组的桶上，[!!!]是链表的头结点
  44.                 newMap[index] = e;
  45.             }
  46.         }
  47.     }

6、Hashtable-源码分析-获取元素

  1. 1、Hashtable-源码分析-获取元素：.get()方法
  3. 2、源代码：
  4.     @SuppressWarnings("unchecked")
  5.     public synchronized V get(Object key) {
  6.         Entry<?,?> tab[] = table;
  7.         int hash = key.hashCode();
  8.         //桶的索引是用key的hash值和0x7FFFFFFF做与运算，最后对数组长度取余
  9.         int index = (hash & 0x7FFFFFFF) % tab.length;
  10.         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
  11.             if ((e.hash == hash) && e.key.equals(key)) {
  12.                 return (V)e.value;
  13.             }
  14.         }
  15.         //如果是插入全新的Entry的话，就返回空
  16.         return null;
  17.     }
  19. 3、.get()方法-执行过程：
  20.     3-1、计算key的hash值，判断在table数组中的索引位置，然后迭代链表，匹配直到找到相对应key的value,若没有找到返回null。

7、Hashtable-源码分析-删除元素

  1. 1、Hashtable-源码分析-删除元素：.remove()方法
  3. 2、源代码：
  4.     public synchronized V remove(Object key) {
  5.         Entry<?,?> tab[] = table;
  6.         //计算key的hash
  7.         int hash = key.hashCode();
  9.         //根据hash计算桶的索引index
  10.         int index = (hash & 0x7FFFFFFF) % tab.length;
  11.         @SuppressWarnings("unchecked")
  12.         Entry<K,V> e = (Entry<K,V>)tab[index];
  13.         //拿到桶的首节点后，往死里遍历首节点后面的链表
  14.         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
  15.             //如果key的hash相等，而且key本身也相等，说明就是要删掉这个节点
  16.             if ((e.hash == hash) && e.key.equals(key)) {
  17.                 //自增
  18.                 modCount++;
  20.                 //如果prev不为空，说明要删除的不是头结点
  21.                 if (prev != null) {
  22.                     //那么将目标节点的头结点指向目标节点的后继节点
  23.                     prev.next = e.next;
  24.                 } else {
  25.                     //如果删除的就是头结点，那么将原来头结点的后继节点指定为头结点
  26.                     tab[index] = e.next;
  27.                 }
  29.                 //元素总数 - 1
  30.                 count--;
  32.                 //取出要删除的节点的value
  33.                 V oldValue = e.value;
  35.                 //将e的value置空(需要吗？)
  36.                 e.value = null;
  38.                 //返回删除节点的value
  39.                 return oldValue;
  40.             }
  41.         }
  42.         return null;
  43.     }

8、Hashtable-源码分析-遍历元素

  1. 1、Hashtable-源码分析-遍历元素：方法有很多种，此处只介绍Enumeration方式
  3. 2、Enumeration类-源代码：
  4.     /**
  5.      * Enumerator的作用是提供了通过elements()遍历Hashtable的接口和通过entrySet()遍历Hashtable的接口。因为，它同时实现了 Enumerator接口和Iterator接口。
  6.      */
  7.     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
  8.         // 指向Hashtable的table
  9.         Entry<?, ?>[] table = Hashtable.this.table;
  10.         // Hashtable的总的大小
  11.         int index = table.length;
  12.         Entry<?, ?> entry;
  13.         Entry<?, ?> lastReturned;
  14.         int type;
  16.         /**
  17.          * Enumerator是 迭代器(Iterator) 还是 枚举类(Enumeration)的标志
  18.          * iterator为true，表示它是迭代器；否则，是枚举类。
  19.          */
  20.         boolean iterator;
  22.         /**
  23.          * 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制。
  24.          */
  25.         protected int expectedModCount = modCount;
  27.         Enumerator(int type, boolean iterator) {
  28.             this.type = type;
  29.             this.iterator = iterator;
  30.         }
  32.         /**
  33.          * 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。
  34.          */
  35.         public boolean hasMoreElements() {
  36.             Entry<?, ?> e = entry;
  37.             int i = index;
  38.             Entry<?, ?>[] t = table;
  39.             /* Use locals for faster loop iteration */
  40.             while (e == null && i > 0) {
  41.                 e = t[--i];
  42.             }
  43.             entry = e;
  44.             index = i;
  45.             return e != null;
  46.         }
  48.         /**
  49.          * 获取下一个元素
  50.          * 注意：从hasMoreElements() 和nextElement() 可以看出Hashtable的elements()遍历方式
  51.          * 首先，从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。
  52.          * 然后，依次向后遍历单向链表Entry。
  53.          */
  54.         @SuppressWarnings("unchecked")
  55.         public T nextElement() {
  56.             Entry<?, ?> et = entry;
  57.             int i = index;
  58.             Entry<?, ?>[] t = table;
  59.             /* Use locals for faster loop iteration */
  60.             while (et == null && i > 0) {
  61.                 et = t[--i];
  62.             }
  63.             entry = et;
  64.             index = i;
  65.             if (et != null) {
  66.                 Entry<?, ?> e = lastReturned = entry;
  67.                 entry = e.next;
  68.                 return type == KEYS ? (T) e.key : (type == VALUES ? (T) e.value : (T) e);
  69.             }
  70.             throw new NoSuchElementException("Hashtable Enumerator");
  71.         }
  73.         // 迭代器Iterator的判断是否存在下一个元素
  74.         // 实际上，它是调用的hasMoreElements()
  75.         public boolean hasNext() {
  76.             return hasMoreElements();
  77.         }
  79.         // 迭代器获取下一个元素
  80.         // 实际上，它是调用的nextElement()
  81.         public T next() {
  82.             if (modCount != expectedModCount)
  83.                 throw new ConcurrentModificationException();
  84.             return nextElement();
  85.         }
  87.         // 迭代器的remove()接口。
  88.         // 首先，它在table数组中找出要删除元素所在的Entry，
  89.         // 然后，删除单向链表Entry中的元素。
  90.         public void remove() {
  91.             if (!iterator)
  92.                 throw new UnsupportedOperationException();
  93.             if (lastReturned == null)
  94.                 throw new IllegalStateException("Hashtable Enumerator");
  95.             if (modCount != expectedModCount)
  96.                 throw new ConcurrentModificationException();
  98.             synchronized (Hashtable.this) {
  99.                 Entry<?, ?>[] tab = Hashtable.this.table;
  100.                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
  102.                 //获取该槽位第一个元素
  103.                 @SuppressWarnings("unchecked")
  104.                 Entry<K, V> e = (Entry<K, V>) tab[index];
  105.                 //从单链表的一端向后遍历
  106.                 for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
  107.                     //当前元素即为上一个返回元素
  108.                     if (e == lastReturned) {
  109.                         modCount++;
  110.                         expectedModCount++;
  111.                         //删除上一个元素
  112.                         if (prev == null)
  113.                             tab[index] = e.next;
  114.                         else
  115.                             prev.next = e.next;
  116.                         count--;
  117.                         lastReturned = null;
  118.                         return;
  119.                     }
  120.                 }
  121.                 throw new ConcurrentModificationException();
  122.             }
  123.         }
  124.     }
  126. 3、Demo
  127.         //通过Enumeration来遍历Hashtable
  128.         Enumeration<String> enu = table.keys();
  129.         while(enu.hasMoreElements()) {
  130.             System.out.println("Enumeration:"+table.keys()+" "+enu.nextElement());
  131.         }