Map - HashTable - 《java后端开发学习》

定义
Hashtable的构造函数
需注意的点
继承关系
Hashtable存取数据
Hashtable扩容方法rehash
取数据（get）
Hashtable的主要对外接口
总结

定义

HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。
Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。

Hashtable中的映射不是有序的。

Hashtable的构造函数

public Hashtable(int initialCapacity, float loadFactor) {
     //可指定初始容量和加载因子  
     if (initialCapacity < 0)  
         throw new IllegalArgumentException("Illegal Capacity: "+  
                                            initialCapacity);  
     if (loadFactor <= 0 || Float.isNaN(loadFactor))  
         throw new IllegalArgumentException("Illegal Load: "+loadFactor);  
     if (initialCapacity==0)  
         initialCapacity = 1;//初始容量最小值为1  
     this.loadFactor = loadFactor;  
     table = new Entry[initialCapacity];//创建桶数组  
     threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//初始化容量阈值  
     useAltHashing = sun.misc.VM.isBooted() &&  
             (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
 }  
 /** 
  * 使用指定的初始容量和默认加载因子构造一个新的空哈希表. 
  */  
 public Hashtable(int initialCapacity) {  
     this(initialCapacity, 0.75f);//默认负载因子为0.75  
 }  
 public Hashtable() {  
     this(11, 0.75f);//默认容量为11，负载因子为0.75  
 }  
 /** 
  * 构造一个新的哈希表，该哈希表具有与给定哈希表相同的映射
  * 地图哈希表的初始容量足以
  * 保留给定映射中的映射和默认负载因子（0.75）。
  */  
 public Hashtable(Map<? extends K, ? extends V> t) {  
     this(Math.max(2*t.size(), 11), 0.75f);  
     putAll(t);  
 }

需注意的点

Hashtable的默认容量为11，默认负载因子为0.75.(HashMap默认容量为16，默认负载因子也是0.75)
Hashtable的容量可以为任意整数，最小值为1，而HashMap的容量始终为2的n次方。
为避免扩容带来的性能问题，建议指定合理容量。
跟HashMap一样，Hashtable内部也有一个静态类叫Entry，其实是个键值对对象，保存了键和值的引用。
.HashMap和Hashtable存储的是键值对对象，而不是单独的键或值。

继承关系
Hashtable继承于Dictionary类，实现了Map接口。Map是”key-value键值对”接口，Dictionary是声明了操作”键值对”函数接口的抽象类。Dictionary是个被废弃的抽象类。
Hashtable是通过”拉链法”实现的哈希表。它包括几个重要的成员变量：table, count, threshold, loadFactor, modCount。 table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。 count是Hashtable的大小，它是Hashtable保存的键值对的数量。 threshold是Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=”容量*加载因子”。loadFactor就是加载因子。 modCount是用来实现fail-fast机制的

Hashtable实现的Cloneable接口

// 克隆一个Hashtable，并以Object的形式返回。
public synchronized Object clone() {
  try {
      Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
      t.table = new Entry[table.length];
      for (int i = table.length ; i-- > 0 ; ) {
          t.table[i] = (table[i] != null)? (Entry<K,V>) table[i].clone() : null;
      }
      t.keySet = null;
      t.entrySet = null;
      t.values = null;
      t.modCount = 0;
      return t;
  } catch (CloneNotSupportedException e) {
      // this shouldn't happen, since we are Cloneable
      throw new InternalError();
  }
}

Hashtable实现的Serializable接口 ```java private synchronized void writeObject(java.io.ObjectOutputStream s)
```
 throws IOException
```
{
```
 // Write out the length, threshold, loadfactor
 s.defaultWriteObject();
```

    // Write out length, count of elements and then the key/value objects
    s.writeInt(table.length);
    s.writeInt(count);
    for (int index = table.length-1; index >= 0; index--) {
        Entry entry = table[index];


        while (entry != null) {
        s.writeObject(entry.key);
        s.writeObject(entry.value);
        entry = entry.next;
        }
    }
}


private void readObject(java.io.ObjectInputStream s)
     throws IOException, ClassNotFoundException
{
    // 读入长度、阈值和加载因子
    s.defaultReadObject();


    // 读取数组的原始长度和元素数
    int origlength = s.readInt();
    int elements = s.readInt();


    //计算新尺寸时，有5%的空间增长，但
    //不大于原始尺寸。定长度
    //奇怪的是，如果它足够大，这有助于分发条目。
    //注意长度最后为零，这是无效的。
    int length = (int)(elements * loadFactor) + (elements / 20) + 3;
    if (length > elements && (length & 1) == 0)
        length--;
    if (origlength > 0 && length > origlength)
        length = origlength;


    Entry[] table = new Entry[length];
    count = 0;


    // 读取元素数，然后读取所有键/值对象
    for (; elements > 0; elements--) {
        K key = (K)s.readObject();
        V value = (V)s.readObject();
            // synch could be eliminated for performance
            reconstitutionPut(table, key, value);
    }
    this.table = table;
}


5. 遍历Hashtable的键值对(获取键值集)

第一步：根据entrySet()获取Hashtable的“键值对”的Set集合。<br />第二步：通过Iterator迭代器遍历“第一步”得到的集合。
```java
// 假设table是Hashtable对象
 // table中的key是String类型，value是Integer类型
 Integer integ = null;
 Iterator iter = table.entrySet().iterator();
 while(iter.hasNext()) {
     Map.Entry entry = (Map.Entry)iter.next();
     // 获取key
     key = (String)entry.getKey();
     // 获取value
     integ = (Integer)entry.getValue();
 }

通过Iterator遍历Hashtable的键（获取键集）

第一步：根据keySet()获取Hashtable的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合

// 假设table是Hashtable对象
 // table中的key是String类型，value是Integer类型
 String key = null;
 Integer integ = null;
 Iterator iter = table.keySet().iterator();
 while (iter.hasNext()) {
     // 获取key
     key = (String)iter.next();
     // 根据key，获取value
     integ = (Integer)table.get(key);
 }

通过Iterator遍历Hashtable的值（获取值集）

第一步：根据value()获取Hashtable的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

// 假设table是Hashtable对象
 // table中的key是String类型，value是Integer类型
 Integer value = null;
 Collection c = table.values();
 Iterator iter= c.iterator();
 while (iter.hasNext()) {
     value = (Integer)iter.next();
 }

通过Enumeration遍历Hashtable的键（获取键集）

第一步：根据keys()获取Hashtable的集合。
第二步：通过Enumeration遍历“第一步”得到的集合。

Enumeration enu = table.keys();
while(enu.hasMoreElements()) {
    System.out.println(enu.nextElement());
}

通过Enumeration遍历Hashtable的值（获取值集）

第一步：根据elements()获取Hashtable的集合。
第二步：通过Enumeration遍历“第一步”得到的集合。

Enumeration enu = table.elements();
while(enu.hasMoreElements()) {
    System.out.println(enu.nextElement());
}

Hashtable存取数据

    public synchronized V put(K key, V value) {//向哈希表中添加键值对  
        // Make sure the value is not null  
        if (value == null) {//确保值不能为空  
            throw new NullPointerException();  
        }  
        // Makes sure the key is not already in the hashtable.  
        Entry tab[] = table;  
        int hash = hash(key);//根据键生成hash值---->若key为null，此方法会抛异常  
        int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到其存储位置  
        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 the table if the threshold is exceeded  
            rehash();//重新构建桶数组，并对数组中所有键值对重哈希，耗时！  
            tab = table;  
            hash = hash(key);  
            index = (hash & 0x7FFFFFFF) % tab.length;//这里是取摸运算  
        }  
        // Creates the new entry.  
        Entry<K,V> e = tab[index];  
        //将新结点插到链表首部  
        tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点  
        count++;  
        return null;  
    }

Hasbtable并不允许值和键为空（null），若为空，会抛空指针。
HashMap计算索引的方式是h&(length-1),而Hashtable用的是模运算，效率上是低于HashMap的。
另外Hashtable计算索引时将hash值先与上0x7FFFFFFF,这是为了保证hash值始终为正数。

特别需要注意的是这个方法包括下面要讲的若干方法都加了synchronized关键字，也就意味着这个Hashtable是个线程安全的类，这也是它和HashMap最大的不同点.

Hashtable扩容方法rehash

 protected void rehash() {  
     int oldCapacity = table.length;//记录旧容量  
     Entry<K,V>[] oldMap = table;//记录旧的桶数组  
     // overflow-conscious code  
     int newCapacity = (oldCapacity << 1) + 1;//新容量为老容量的2倍加1  
     if (newCapacity - MAX_ARRAY_SIZE > 0) {  
         if (oldCapacity == MAX_ARRAY_SIZE)//容量不得超过约定的最大值  
             // Keep running with MAX_ARRAY_SIZE buckets  
             return;  
         newCapacity = MAX_ARRAY_SIZE;  
     }  
     Entry<K,V>[] newMap = new Entry[newCapacity];//创建新的数组  
     modCount++;  
     threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
     boolean currentAltHashing = useAltHashing;  
     useAltHashing = sun.misc.VM.isBooted() &&  
             (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
     boolean rehash = currentAltHashing ^ useAltHashing;  
     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;  
         }  
     }  
 }

Hashtable每次扩容，容量都为原来的2倍加1，而HashMap为原来的2倍。

取数据（get）

```java /**

如果你传的参数为null，是会抛空指针的 **/ public synchronized V get(Object key) {//根据键取出对应索引

Entry tab[] = table;  
int hash = hash(key);//先根据key计算hash值  
int index = (hash & 0x7FFFFFFF) % tab.length;//再根据hash值找到索引  
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍历entry链  
    if ((e.hash == hash) && e.key.equals(key)) {//若找到该键  
        return e.value;//返回对应的值  
    }  
}  
return null;//否则返回null

} ```

Hashtable的主要对外接口

clear() 的作用是清空Hashtable。它是将Hashtable的table数组的值全部设为null.

public synchronized void clear() {
 Entry tab[] = table;
 modCount++;
 for (int index = tab.length; --index >= 0; )
     tab[index] = null;
 count = 0;
}

contains() 和 containsValue() 的作用都是判断Hashtable是否包含“值(value)” ```java public boolean containsValue(Object value) { return contains(value); }

public synchronized boolean contains(Object value) { // Hashtable中“键值对”的value不能是null， // 若是null的话，抛出异常! if (value == null) { throw new NullPointerException(); }

// 从后向前遍历table数组中的元素(Entry)
// 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
    for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
        if (e.value.equals(value)) {
            return true;
        }
    }
}
return false;

}


3. containsKey() 的作用是判断Hashtable是否包含key
```java
public synchronized boolean containsKey(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    // 计算索引值，
    // % tab.length 的目的是防止数据越界
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return true;
        }
    }
    return false;
}

elements() 的作用是返回“所有value”的枚举对象 ```java public synchronized Enumeration elements() { return this.getEnumeration(VALUES); }

// 获取Hashtable的枚举类对象 private Enumeration getEnumeration(int type) { if (count == 0) { return (Enumeration)emptyEnumerator; } else { return new Enumerator(type, false); } }

 若Hashtable的实际大小为0,则返回“空枚举类”对象emptyEnumerator；<br />否则，返回正常的Enumerator的对象。<br />EmptyEnumerator对象是如何实现的
```java
private static Enumeration emptyEnumerator = new EmptyEnumerator();

// 空枚举类
// 当Hashtable的实际大小为0；此时，又要通过Enumeration遍历Hashtable时，返回的是“空枚举类”的对象。
private static class EmptyEnumerator implements Enumeration<Object> {


    EmptyEnumerator() {
    }


    // 空枚举类的hasMoreElements() 始终返回false
    public boolean hasMoreElements() {
        return false;
    }


    // 空枚举类的nextElement() 抛出异常
    public Object nextElement() {
        throw new NoSuchElementException("Hashtable Enumerator");
    }
}

Enumerator的作用是提供了“通过elements()遍历Hashtable的接口” 和 “通过entrySet()遍历Hashtable的接口”。

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
    // 指向Hashtable的table
    Entry[] table = Hashtable.this.table;
    // Hashtable的总的大小
    int index = table.length;
    Entry<K,V> entry = null;
    Entry<K,V> lastReturned = null;
    int type;


    // Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志
    // iterator为true，表示它是迭代器；否则，是枚举类。
    boolean iterator;


    // 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制。
    protected int expectedModCount = modCount;


    Enumerator(int type, boolean iterator) {
        this.type = type;
        this.iterator = iterator;
    }


    // 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。
    public boolean hasMoreElements() {
        Entry<K,V> e = entry;
        int i = index;
        Entry[] t = table;
        /* Use locals for faster loop iteration */
        while (e == null && i > 0) {
            e = t[--i];
        }
        entry = e;
        index = i;
        return e != null;
    }

get() 的作用就是获取key对应的value，没有的话返回null

public synchronized V get(Object key) {
 Entry tab[] = table;
 int hash = key.hashCode();
 // 计算索引值，
 int index = (hash & 0x7FFFFFFF) % tab.length;
 // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
     if ((e.hash == hash) && e.key.equals(key)) {
         return e.value;
     }
 }
 return null;
}

put() 的作用是对外提供接口，让Hashtable对象可以通过put()将“key-value”添加到Hashtable中

 public synchronized V put(K key, V value) {
     // Hashtable中不能插入value为null的元素！！！
     if (value == null) {
         throw new NullPointerException();
     }

     // 若“Hashtable中已存在键为key的键值对”，
     // 则用“新的value”替换“旧的value”
     Entry tab[] = table;
     int hash = key.hashCode();
     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;
             }
     }

     // 若“Hashtable中不存在键为key的键值对”，
     // (01) 将“修改统计数”+1
     modCount++;
     // (02) 若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)
     //  则调整Hashtable的大小
     if (count >= threshold) {
         // Rehash the table if the threshold is exceeded
         rehash();
         tab = table;
         index = (hash & 0x7FFFFFFF) % tab.length;
     }

     // (03) 将“Hashtable中index”位置的Entry(链表)保存到e中
     Entry<K,V> e = tab[index];
     // (04) 创建“新的Entry节点”，并将“新的Entry”插入“Hashtable的index位置”，并设置e为“新的Entry”的下一个元素(即“新Entry”为链表表头)。        
     tab[index] = new Entry<K,V>(hash, key, value, e);
     // (05) 将“Hashtable的实际容量”+1
     count++;
     return null;
 }

putAll() 的作用是将“Map(t)”的中全部元素逐一添加到Hashtable中

public synchronized void putAll(Map<? extends K, ? extends V> t) {
 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
     put(e.getKey(), e.getValue());
}

remove() 的作用就是删除Hashtable中键为key的元素

public synchronized V remove(Object key) {
 Entry tab[] = table;
 int hash = key.hashCode();
 int index = (hash & 0x7FFFFFFF) % tab.length;
 // 找到“key对应的Entry(链表)”
 // 然后在链表中找出要删除的节点，并删除该节点。
 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
     if ((e.hash == hash) && e.key.equals(key)) {
         modCount++;
         if (prev != null) {
             prev.next = e.next;
         } else {
             tab[index] = e.next;
         }
         count--;
         V oldValue = e.value;
         e.value = null;
         return oldValue;
     }
 }
 return null;
}

总结

Hashtable是个线程安全的类（HashMap线程安全）；
Hasbtable并不允许值和键为空（null），若为空，会抛空指针（HashMap可以）；
Hashtable不允许键重复，若键重复，则新插入的值会覆盖旧值（同HashMap）；
Hashtable同样是通过链表法解决冲突；
Hashtable根据hashcode计算索引时将hashcode值先与上0x7FFFFFFF,这是为了保证hash值始终为正数;
Hashtable的容量为任意正数（最小为1），而HashMap的容量始终为2的n次方。Hashtable默认容量为11，HashMap默认容量为16；
Hashtable每次扩容，新容量为旧容量的2倍加1，而HashMap为旧容量的2倍；
Hashtable和HashMap默认负载因子都为0.75;

[

](https://blog.csdn.net/dingjianmin/article/details/79774192)

HashTable

定义