Hashtable简介

Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表办理斗嘴问题,容量不敷(高出了阀值)时,同样会自动增长。

Hashtable也是JDK1.0引入的类,是线程安详的,能用于多线程情况中。

Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆。

HashTable源码分解

Hashtable的源码的许多实现都与HashMap差不多,源码如下(插手了较量具体的注释):

package java.util;    
import java.io.*;    
       
public class Hashtableextends Dictionaryimplements Map, Cloneable, java.io.Serializable {    
       
    // 生存key-value的数组。    
    // Hashtable同样回收单链表办理斗嘴,每一个Entry本质上是一个单向链表    
    private transient Entry[] table;    
       
    // Hashtable中键值对的数量    
    private transient int count;    
       
    // 阈值,用于判定是否需要调解Hashtable的容量(threshold = 容量*加载因子)    
    private int threshold;    
       
    // 加载因子    
    private float loadFactor;    
       
    // Hashtable被改变的次数,用于fail-fast机制的实现    
    private transient int modCount = 0;    
       
    // 序列版本号    
    private static final long serialVersionUID = 1421746759512286392L;    
       
    // 指定“容量巨细”和“加载因子”的结构函数    
    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;    
        this.loadFactor = loadFactor;    
        table = new Entry[initialCapacity];    
        threshold = (int)(initialCapacity * loadFactor);    
    }    
       
    // 指定“容量巨细”的结构函数    
    public Hashtable(int initialCapacity) {    
        this(initialCapacity, 0.75f);    
    }    
       
    // 默认结构函数。    
    public Hashtable() {    
        // 默认结构函数,指定的容量巨细是11;加载因子是0.75    
        this(11, 0.75f);    
    }    
       
    // 包括“子Map”的结构函数    
    public Hashtable(Map t) {    
        this(Math.max(2*t.size(), 11), 0.75f);    
        // 将“子Map”的全部元素都添加到Hashtable中    
        putAll(t);    
    }    
       
    public synchronized int size() {    
        return count;    
    }    
       
    public synchronized boolean isEmpty() {    
        return count == 0;    
    }    
       
    // 返回“所有key”的列举工具    
    public synchronized Enumerationkeys() {    
        return this.getEnumeration(KEYS);    
    }    
       
    // 返回“所有value”的列举工具    
    public synchronized Enumerationelements() {    
        return this.getEnumeration(VALUES);    
    }    
       
    // 判定Hashtable是否包括“值(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 (Entrye = tab[i] ; e != null ; e = e.next) {    
                if (e.value.equals(value)) {    
                    return true;    
                }    
            }    
        }    
        return false;    
    }    
       
    public boolean containsValue(Object value) {    
        return contains(value);    
    }    
       
    // 判定Hashtable是否包括key    
    public synchronized boolean containsKey(Object key) {    
        Entry tab[] = table;    
        //计较hash值,直接用key的hashCode取代  
        int hash = key.hashCode();      
        // 计较在数组中的索引值   

        int index = (hash & 0x7FFFFFFF) % tab.length;    
        // 找到“key对应的Entry(链表)”,然后在链表中找出“哈希值”和“键值”与key都相等的元素    
        for (Entrye = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                return true;    
            }    
        }    
        return false;    
    }    
       
    // 返回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 (Entrye = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                return e.value;    
            }    
        }    
        return null;    
    }    
       
    // 调解Hashtable的长度,将长度酿本钱来的2倍+1   
    protected void rehash() {    
        int oldCapacity = table.length;    
        Entry[] oldMap = table;    
       
        //建设新容量巨细的Entry数组  
        int newCapacity = oldCapacity * 2 + 1;    
        Entry[] newMap = new Entry[newCapacity];    
       
        modCount++;    
        threshold = (int)(newCapacity * loadFactor);    
        table = newMap;    
              
        //将“旧的Hashtable”中的元素复制到“新的Hashtable”中  
        for (int i = oldCapacity ; i-- > 0 ;) {    
            for (Entryold = oldMap[i] ; old != null ; ) {    
                Entrye = old;    
                old = old.next;    
                //从头计较index  
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;    
                e.next = newMap[index];    
                newMap[index] = e;    
            }    
        }    
    }    
       
    // 将“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 (Entrye = 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的键值对”,  
        // 将“修改统计数”+1    
        modCount++;    
        //  若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)    
        //  则调解Hashtable的巨细    
        if (count >= threshold) {  
            rehash();    
       
            tab = table;    
            index = (hash & 0x7FFFFFFF) % tab.length;    
        }    
       
        //将新的key-value对插入到tab[index]处(即链表的头结点)  
        Entrye = tab[index];           
        tab[index] = new Entry(hash, key, value, e);    
        count++;    
        return null;    
    }    
       
    // 删除Hashtable中键为key的元素    
    public synchronized V remove(Object key) {    
        Entry tab[] = table;    
        int hash = key.hashCode();    
        int index = (hash & 0x7FFFFFFF) % tab.length;    
              
        //从table[index]链表中找出要删除的节点,并删除该节点。  
        //因为是单链表,因此要保存带删节点的前一个节点,才气有效地删除节点  
        for (Entrye = 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;    
    }    
       
    // 将“Map(t)”的中全部元素逐一添加到Hashtable中    
    public synchronized void putAll(Map t) {    
        for (Map.Entry e : t.entrySet())    
            put(e.getKey(), e.getValue());    
    }    
       
    // 清空Hashtable    
    // 将Hashtable的table数组的值全部设为null 
// 本栏目
		 

JAVA 教程

2017-12-28


Hashtable简介 Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表办理斗嘴问题,容量不敷(高出了阀值)时,同样会自动