回味集合(十三)之HashTable

祝大家新年快乐，虎年大吉；

HashTable的继承体系

Dictionary 是JDK1.0出的一个接口，Dictionary 类是任何类的抽象父类，例如 Hashtable，它将键映射到值。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键最多与一个值相关联。给定一个字典和一个键，可以查找相关的元素。任何非空对象都可以用作键和值。通常，此类的实现应使用 equals 方法来确定两个键是否相同。感觉是Map(JDK 1.2)接口的前世，定义了一些简单的集合操作方法：

public abstract class Dictionary {
     // 构造器
    public Dictionary() {
    }
    // 返回此字典中的条目数（不同的键）
    abstract public int size();
    // 测试此字典是否没有将键映射到值。isEmpty 方法的一般约定是，
    // 当且仅当此字典不包含条目   时，结果才为真。
    abstract public boolean isEmpty();
    // 返回此字典中键的枚举。 keys 方法的一般约定是返回一个 
    // Enumeration 对象，该对象将生成该字典包含条目的所有键。
    abstract public Enumeration keys();
    // 返回此字典中值的枚举。 elements 方法的一般约定是返回一个 
    // Enumeration ，它将生成该字典中条目中包含的所有元素
    abstract public Enumeration elements();
    // 返回此字典中键映射到的值。 isEmpty 方法的一般约定是，
    // 如果此字典包含指定键的条目，则返回关联的值；否则，返回 null。
    abstract public V get(Object key);
    // 将指定的键映射到此字典中的指定值。键和值都不能为空。如果
    // 此字典已包含指定键的条目，则在修改条目以包含新元素后，返
    // 回此字典中已存在的该键的值。如果此字典还没有指定键的条目，
    // 则为指定的键和值创建一个条目，并返回 null。可以通过使用与
    // 原始键相同的键调用 get 方法来检索该值。
    abstract public V put(K key, V value);
    // 从此字典中删除键（及其对应的值）。如果键不在此字典中，则此方法不执行任何操作。
    abstract public V remove(Object key);
}

成员变量

// 哈希表
private transient Entry[] table;
// 哈希表 Entry结点数量
private transient int count;
// 哈希表扩容的阙值(容量 * 负载因子)
private int threshold;
// 负载因子，默认为0.75
private float loadFactor;
// 记录哈希表结构变化的次数
private transient int modCount = 0;
// 哈希表最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造器

 // 指定容量和负载因子
 // 初始化哈希表和下次扩容的阙值
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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }
    // 指定容量，使用默认的负载因子 0.75
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    // 使用默认容量11和负载因子0.75
  public Hashtable() {
        this(11, 0.75f);
    }
    // jdk 1.2
    // 使用Map的信息初始化hashTable
    // 将Map中的结点添加到hashTable
   public Hashtable(Map t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

重要方法

// 哈希表扩容，重新计算哈希值，分配哈希散列
protected void rehash() {
        int oldCapacity = table.length;
        Entry[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 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[] newMap = new Entry[newCapacity];

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

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
                Entry e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry)newMap[index];
                newMap[index] = e;
            }
        }
    }

常用方法（方法都是同步的，使用synchronized修饰）

  // 获取当前哈希表结点数量
  public synchronized int size() {
        return count;
    }
  // 判断当前哈希表是否为空
   public synchronized boolean isEmpty() {
        return count == 0;
    }  
    // 判断哈希表中是否包含指定value
    public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }

        Entry tab[] = table;
        for (int i = tab.length ; i-- > 0 ;) {
            for (Entry e = tab[i] ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 判断哈希表中是否包含指定value
      public boolean containsValue(Object value) {
        return contains(value);
    }

     // 判断哈希表中是否包含指定key
      public synchronized boolean containsKey(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }
 
    // 通过key获取value
       public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }
  
  // 向哈希表中添加
    public synchronized V put(K key, V value) {
        // value不能为空
        if (value == null) {
            throw new NullPointerException();
        }

        // 哈希表
        Entry tab[] = table;
        // 计算key的内存地址hashCode
        int hash = key.hashCode();
        // 使用哈希算法计算哈希值(除留余数法)
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        // 获取当前哈希值对应位置的Entry
        Entry entry = (Entry)tab[index];
        // 不为空则进行value的替换并返回旧的value
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        // entry为空添加新的entry
        addEntry(hash, key, value, index);
        return null;
    }

    // 添加新的entry结点
      private void addEntry(int hash, K key, V value, int index) {
      // 操作数加1
        modCount++;

        Entry tab[] = table;
        // 判断当前哈希表中的entry结点数是否大于哈希表扩容阙值
        if (count >= threshold) {
            // 扩容
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry e = (Entry) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }
 
    // 移除哈希表中key对应的结点
      public synchronized V remove(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry e = (Entry)tab[index];
        for(Entry 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到HashTable中
     public synchronized void putAll(Map t) {
        for (Map.Entry e : t.entrySet())
            put(e.getKey(), e.getValue());
    }
 
 // 清除哈希表中所有的结点
  public synchronized void clear() {
        Entry tab[] = table;
        modCount++;
        for (int index = tab.length; --index >= 0; )
            tab[index] = null;
        count = 0;
    }
 
  // 获取哈希表中所有的key
      public synchronized Enumeration keys() {
        return this.getEnumeration(KEYS);
    }  
  // 获取哈希表中所有的value
   public synchronized Enumeration elements() {
        return this.getEnumeration(VALUES);
    }  
  // 根据type获取相应的枚举器
    private  Enumeration getEnumeration(int type) {
        if (count == 0) {
            return Collections.emptyEnumeration();
        } else {
            return new Enumerator<>(type, false);
        }
    }
  

静态内部类Entry

 private static class Entry implements Map.Entry {
        // 哈希值
        final int hash;
        // key
        final K key;
        // value
        V value;
        // 下一个结点
        Entry next;
        // 构造器
        protected Entry(int hash, K key, V value, Entry next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry) next.clone()));
        }

        // 返回key
        public K getKey() {
            return key;
        }
        // 返回value
        public V getValue() {
            return value;
        }
        // 设置value
        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }

枚举器(个人感觉有点类似于Iterator(jdk1.2))

// jdk 1.0
public interface Enumeration {
    // 测试此枚举是否包含更多元素。返回： 当且仅当此枚举
    // 对象包含至少一个要提供的元素时，才返回 true；否则为假
    boolean hasMoreElements();
    // 如果此枚举对象至少还有一个要提供的元素，则返回此枚举的下一个元素
    E nextElement();
}

// 在hashtable中实现的内部类Enumerator
    // 用于获取哈希表中的key或者value时指定一个类型
    // 返回相应的枚举器
    private static final int KEYS = 0;
    private static final int VALUES = 1;
    private static final int ENTRIES = 2;
    
private class Enumerator implements Enumeration, Iterator {
        Entry[] table = Hashtable.this.table;
        int index = table.length;
        Entry entry;
        Entry lastReturned;
        int type;

        
        boolean iterator;

        
        protected int expectedModCount = modCount;

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

        public boolean hasMoreElements() {
            Entry e = entry;
            int i = index;
            Entry[] t = table;
            
            while (e == null && i > 0) {
                e = t[--i];
            }
            entry = e;
            index = i;
            return e != null;
        }

        @SuppressWarnings("unchecked")
        public T nextElement() {
            Entry et = entry;
            int i = index;
            Entry[] t = table;
            
            while (et == null && i > 0) {
                et = t[--i];
            }
            entry = et;
            index = i;
            if (et != null) {
                Entry e = lastReturned = entry;
                entry = e.next;
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
            }
            throw new NoSuchElementException("Hashtable Enumerator");
        }

        // Iterator methods
        public boolean hasNext() {
            return hasMoreElements();
        }

        public T next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return nextElement();
        }

        public void remove() {
            if (!iterator)
                throw new UnsupportedOperationException();
            if (lastReturned == null)
                throw new IllegalStateException("Hashtable Enumerator");
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            synchronized(Hashtable.this) {
                Entry[] tab = Hashtable.this.table;
                int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

                @SuppressWarnings("unchecked")
                Entry e = (Entry)tab[index];
                for(Entry prev = null; e != null; prev = e, e = e.next) {
                    if (e == lastReturned) {
                        modCount++;
                        expectedModCount++;
                        if (prev == null)
                            tab[index] = e.next;
                        else
                            prev.next = e.next;
                        count--;
                        lastReturned = null;
                        return;
                    }
                }
                throw new ConcurrentModificationException();
            }
        }
    }