close

Mr.Muzi

一只很安静的monkey

Java Map 05 - Hashtable

字数统计: 5.9k 阅读时长: 28 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.Hashtable<K, V> 的部分笔记，Hashtable是一个不允许key和value为null的集合实现。和HashMap的功能和应用场景大致相同，但是Hashtable是一个线程安全的实现，可以用于多线程环境中。本文演示代码段的执行环境基于JDK版本1.7。

概述

  Hashtable是一个存储key=value映射的实现类，对键值对的要求是key和value均不能为空。为了可能正确有效的存储和检索Hashtable里的键值对实体，key所属的类型必须要实现hashcode()和equals()方法。

  Hashtable中有两个参数会影响散列表的操作性能：initialCapacity和loadFactor。initialCapacity决定了散列表中桶（存储键值对实体的数组）的大小，而loadFactor决定了当桶填充到什么程度时会执行数组扩容处理。如果执行了扩容操作，那么需要将当前散列表的键值对实体重新计算hashcode值并分配在扩容后数组中的位置。默认的加载因子是0.75，这个值保证了散列表的操作性能可以在时间和空间利用方面达到一个理想的平衡。

  如果在元素插入前就可以估计到元素的数量，那么可以提前指定散列表的空间大小，这样可以在插入过程中避免频繁的重新分配空间而导致性能下降。

  Hashtable的迭代器实现了Enumeration和Iterator两个接口，可以根据应用场景决定采用枚举或者迭代器的方式完成键值对实体的遍历。如果采用Iterator进行遍历，那么Hashtable在移除元素的过程中也会执行快速失败检查。

  Hashtable是一个线程安全的实现类，如果需要在多线程环境中使用键值对映射实现，那么可以考虑采用Hashtable来完成需求。如果不需要考虑多线程场景，那么可以用HashMap来完成需求以提高性能。

 

继承关系

1
2
3
4
// Hashtable<K,V>
--java.lang.Object
  --java.util.Dictionary<K,V>
    --java.util.Hashtable<K,V>

 

实现接口

类名 实现接口
LinkedHashMap<E> Serializable, Cloneable,Map<K,V>

 

Hashtable

Constructor Summary

public Hashtable(int initialCapacity, float loadFactor)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
    initHashSeedAsNeeded(initialCapacity);
}

  初始化一个空Hashtable集合，集合的初始容量和加载因子由initialCapacity和loadFactor确认。如果initialCapacity的值为0，那么指定initialCapacity为1。

初始化底层存储结构table，根据initialCapacity和loadFactor确定扩容限制阈值，最后调用initHashSeedAsNeeded(int capacity)方法初始化散列掩码完成初始化操作。

public Hashtable(int initialCapacity)

1
2
3
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

  初始化一个空Hashtable集合，集合的初始容量由initialCapacity和确认，加载因子默认为0.75。调用构造方法Hashtable(int initialCapacity, float loadFactor)完成初始化操作。

public Hashtable()

1
2
3
public Hashtable() {
    this(11, 0.75f);
}

  初始化一个空Hashtable集合，集合的初始容量默认为11，加载因子默认为0.75。调用构造方法Hashtable(int initialCapacity, float loadFactor)完成初始化操作。

public Hashtable(Map<? extends K, ? extends V> t)

1
2
3
4
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

  初始化一个空Hashtable集合，并将t中的键值对保存到初始化的散列表中。在初始化过程中，集合的容量大小由t存储的键值对数量决定，保证空map集合可以将m中的键值对全部存储下来，且默认加载因子是0.75。调用构造方法Hashtable(int initialCapacity, float loadFactor)完成初始化操作。

  初始化操作完成后，调用putAll(Map<? extends K, ? extends V> t)将集合t中的键值对保存到当前散列表中。

部分方法

public synchronized int size()

1
2
3
public synchronized int size() {
    return count;
}

  返回当前散列表中的含有的key的数量。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

public synchronized boolean isEmpty()

1
2
3
public synchronized boolean isEmpty() {
    return count == 0;
}

  判断当前散列表中是否为空，如果为空返回true，否则返回false。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

public synchronized Enumeration<K> keys()

1
2
3
public synchronized Enumeration<K> keys() {
    return this.<K>getEnumeration(KEYS);
}

  返回当前散列表中存储的所有key的一个枚举形式。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

public synchronized Enumeration<K> elements()

1
2
3
public synchronized Enumeration<V> elements() {
    return this.<V>getEnumeration(VALUES);
}

  返回当前散列表中存储的所有value的一个枚举形式。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

private <T> Enumeration<T> getEnumeration(int type)

1
2
3
4
5
6
7
private <T> Enumeration<T> getEnumeration(int type) {
    if (count == 0) {
        return Collections.emptyEnumeration();
    } else {
        return new Enumerator<>(type, false);
    }
}

  返回一个枚举对象。如果当前散列表为空，那么返回一个空的枚举实例。否则初始化一个枚举器实例。

public synchronized boolean contains(Object value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public synchronized boolean contains(Object value) {
    if (value == null) {
        throw new NullPointerException();
    }

    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;
}

  判断当前散列表中是否存在匹配value的键值对映射。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。该方法的执行性能比containsKey(Object key)差，这是需要注意的地方。

public boolean containsValue(Object value)

1
2
3
public boolean containsValue(Object value) {
    return contains(value);
}

  判断当前散列表中是否存在匹配的value的key存在，如果存在返回true，否则返回false。直接调用方法contains(Object value)实现功能。

public synchronized boolean containsKey(Object key)

1
2
3
4
5
6
7
8
9
10
11
public synchronized boolean containsKey(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    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)) {
            return true;
        }
    }
    return false;
}

  判断当前散列表中是否存在匹配key的键值对映射。如果存在返回true，否则返回false。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

  首先计算key的hashcode，然后根据hashcode和当前散列表长度计算该对象可能位于的数组下标位置值。取得该下标位置的链表集合，遍历该集合找出key值相等元素，返回true。如果没找到，返回false。

public synchronized V get(Object key)

1
2
3
4
5
6
7
8
9
10
11
public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    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)) {
            return e.value;
        }
    }
    return null;
}

  从当前散列表集合中根据key找到可以匹配的键值对映射，如果存在返回键值对的value值，否则返回null。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

  首先计算key的hashcode，并根据hashcode计算该映射在散列表中可能的下标位置。取得该下标位置的链表集合，遍历该集合找出key值相等的元素，返回对应的value值，否则返回null。

protected void rehash()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] 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<K,V>[] newMap = new Entry[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);

    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;
        }
    }
}

  当前散列表需要扩容处理，且将键值对映射保存到扩容后的数组中。

  第6 ~ 12行代码计算扩容后需要的数组长度，并在第13行代码中完成新数组的初始化和空间分配。第16行代码计算新的扩容限制阈值以及是否需要重新计算hashcode值。

  第21 ~ 33行代码遍历旧数组的每个节点上的链表集合以及集合里的每个元素，如果需要重新计算hashcode的话那么就调用hash(Object k)方法完成hashcode的计算，之后根据hashcode和新数组容量确定元素在新数组中的下标位置，最后将该元素加入到该下标位置的链表集合中。

public synchronized V put(K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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);
    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;
        }
    }

    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;
}

  将键值对加入到当前散列表集合中。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

  该方法不允许value为null，所以如果传入的value为null，那么抛出空指针异常。第9 ~ 10行代码计算key的hashcode值和该键值对在散列表中的下标位置。第11 ~ 17行代码中如果该下标位置的链表集合中存在key值相同的键值对映射，那么用value替换原有的值并返回被替换的值。

  如果当前散列表容量超过了扩容限制阈值，那么调用rehash()方法完成扩容以及键值对实体迁移操作，并计算key的hashcode值以及当前key=value在新数组中的下标位置。最后创建一个新的Entry节点并加入到该下标位置的链表集合的首部节点上，并更新count值。

public synchronized void putAll(Map<? extends K, ? extends V> t)

1
2
3
4
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());
}

  将t中的所有键值对映射都加入到当前散列表中。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。底层调用put(K key, V value)完成操作。

public synchronized V remove(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public synchronized V remove(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    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;
}

  从当前散列表中删除可以匹配key的键值对映射。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

  根据key计算对应的hashcode值，以及该key在散列表中的下标位置，得到该下标位置的链表集合，遍历集合中的每个键值对映射实体。如果hashcode一致且key一致，如果prev != null，那么说明匹配的键值对实体不是链表的首部节点，那么直接移除该节点。反之，则将链表首部节点的后继节点指向下标位置实体。最后返回被删除的键值对映射的value值。

public synchronized void clear()

1
2
3
4
5
6
7
public synchronized void clear() {
    Entry tab[] = table;
    modCount++;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    count = 0;
}

  清空当前散列表。synchronized保证了该方法在多线程环境下同一时刻只有一个线程可以访问该方法，满足了多线程环境下的线程安全。

public synchronized Object clone()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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();
    }
}

  将当前散列表克隆一份并返回复制对象。

public synchronized String toString()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public synchronized String toString() {
    int max = size() - 1;
    if (max == -1)
        return "{}";

    StringBuilder sb = new StringBuilder();
    Iterator<Map.Entry<K,V>> it = entrySet().iterator();

    sb.append('{');
    for (int i = 0; ; i++) {
        Map.Entry<K,V> e = it.next();
        K key = e.getKey();
        V value = e.getValue();
        sb.append(key   == this ? "(this Map)" : key.toString());
        sb.append('=');
        sb.append(value == this ? "(this Map)" : value.toString());

        if (i == max)
            return sb.append('}').toString();
        sb.append(", ");
    }
}

  返回当前散列表的String形式表示。

public Set<K> keySet()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Set<K> keySet() {
    if (keySet == null)
        keySet = Collections.synchronizedSet(new KeySet(), this);
    return keySet;
}

private class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return getIterator(KEYS);
    }
    public int size() {
        return count;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return Hashtable.this.remove(o) != null;
    }
    public void clear() {
        Hashtable.this.clear();
    }
}

  返回当前散列表中存储的所有键值对映射的key的set集合。返回的是一个线程安全的集合实例。

private <T> Iterator<T> getIterator(int type)

1
2
3
4
5
6
7
private <T> Iterator<T> getIterator(int type) {
    if (count == 0) {
        return Collections.emptyIterator();
    } else {
        return new Enumerator<>(type, true);
    }
}

  根据类型返回迭代器。

public Set<Map.Entry<K,V>> entrySet()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public Set<Map.Entry<K,V>> entrySet() {
    if (entrySet==null)
        entrySet = Collections.synchronizedSet(new EntrySet(), this);
    return entrySet;
}

private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return getIterator(ENTRIES);
    }

    public boolean add(Map.Entry<K,V> o) {
        return super.add(o);
    }

    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry entry = (Map.Entry)o;
        Object key = entry.getKey();
        Entry[] tab = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry e = tab[index]; e != null; e = e.next)
            if (e.hash==hash && e.equals(entry))
                return true;
        return false;
    }

    public boolean remove(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
        K key = entry.getKey();
        Entry[] tab = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;

        for (Entry<K,V> e = tab[index], prev = null; e != null;
             prev = e, e = e.next) {
            if (e.hash==hash && e.equals(entry)) {
                modCount++;
                if (prev != null)
                    prev.next = e.next;
                else
                    tab[index] = e.next;

                count--;
                e.value = null;
                return true;
            }
        }
        return false;
    }

    public int size() {
        return count;
    }

    public void clear() {
        Hashtable.this.clear();
    }
}

  返回当前散列表中存储的所有键值对映射的set集合。返回的是一个线程安全的集合实例。

public Collection<V> values()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Collection<V> values() {
    if (values==null)
        values = Collections.synchronizedCollection(new ValueCollection(), this);
    return values;
}

private class ValueCollection extends AbstractCollection<V> {
    public Iterator<V> iterator() {
        return getIterator(VALUES);
    }
    public int size() {
        return count;
    }
    public boolean contains(Object o) {
        return containsValue(o);
    }
    public void clear() {
        Hashtable.this.clear();
    }
}

  返回当前散列表中存储的所有键值对映射的value的Collection集合。返回的是一个线程安全的集合实例。

public synchronized boolean equals(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public synchronized boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Map))
        return false;
    Map<K,V> t = (Map<K,V>) o;
    if (t.size() != size())
        return false;

    try {
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext()) {
            Map.Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue();
            if (value == null) {
                if (!(t.get(key)==null && t.containsKey(key)))
                    return false;
            } else {
                if (!value.equals(t.get(key)))
                    return false;
            }
        }
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }

    return true;
}

  判断当前散列表和对象o是否相等。如果o是当前散列表自身，那么返回true。如果o不是一个map实现，那么直接返回false。如果o存储的键值对映射数量和当前散列表的数量不一致，直接返回false。

  遍历当前散列表中的每一个键值对映射实体，如果存在value不一致的映射，那么直接返回false。

public synchronized int hashCode()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public synchronized int hashCode() {
    int h = 0;
    if (count == 0 || loadFactor < 0)
        return h;  // Returns zero

    loadFactor = -loadFactor;  // Mark hashCode computation in progress
    Entry[] tab = table;
    for (Entry<K,V> entry : tab)
        while (entry != null) {
            h += entry.hashCode();
            entry = entry.next;
        }
    loadFactor = -loadFactor;  // Mark hashCode computation complete

    return h;
}

  返回当前散列表的hashcode值。计算的是散列表中每个键值对的hashcode之和。

private void writeObject(java.io.ObjectOutputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private void writeObject(java.io.ObjectOutputStream s)
            throws IOException {
    Entry<K, V> entryStack = null;

    synchronized (this) {
        // Write out the length, threshold, loadfactor
        s.defaultWriteObject();

        // Write out length, count of elements
        s.writeInt(table.length);
        s.writeInt(count);

        // Stack copies of the entries in the table
        for (int index = 0; index < table.length; index++) {
            Entry<K,V> entry = table[index];

            while (entry != null) {
                entryStack =
                    new Entry<>(0, entry.key, entry.value, entryStack);
                entry = entry.next;
            }
        }
    }

    // Write out the key/value objects from the stacked entries
    while (entryStack != null) {
        s.writeObject(entryStack.key);
        s.writeObject(entryStack.value);
        entryStack = entryStack.next;
    }
}

  Hashtable的自定义序列化实现过程。

  第7行代码将Hashtable的threshold和loadFactor写入到流中，第10 ~ 11行代码将当前数组的长度和Hashtable容纳的键值对数量写入到流中。第14 ~ 22行代码取得当前集合中所有的键值对映射实体。最后遍历该集合，按照先key后value的顺序将键值对映射写入到流中。

private void readObject(java.io.ObjectInputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException {
    // Read in the length, threshold, and loadfactor
    s.defaultReadObject();

    // Read the original length of the array and number of elements
    int origlength = s.readInt();
    int elements = s.readInt();

    // Compute new size with a bit of room 5% to grow but
    // no larger than the original size.  Make the length
    // odd if it's large enough, this helps distribute the entries.
    // Guard against the length ending up zero, that's not valid.
    int length = (int)(elements * loadFactor) + (elements / 20) + 3;
    if (length > elements && (length & 1) == 0)
        length--;
    if (origlength > 0 && length > origlength)
        length = origlength;

    Entry<K,V>[] newTable = new Entry[length];
    threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
    count = 0;
    initHashSeedAsNeeded(length);

    // Read the number of elements and then all the key/value objects
    for (; elements > 0; elements--) {
        K key = (K)s.readObject();
        V value = (V)s.readObject();
        // synch could be eliminated for performance
        reconstitutionPut(newTable, key, value);
    }
    this.table = newTable;
}

  Hashtable的自定义反序列实现过程。

private void reconstitutionPut(Entry[] tab, K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
        throws StreamCorruptedException {
    if (value == null) {
        throw new java.io.StreamCorruptedException();
    }
    // Makes sure the key is not already in the hashtable.
    // This should not happen in deserialized version.
    int hash = hash(key);
    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)) {
            throw new java.io.StreamCorruptedException();
        }
    }
    // Creates the new entry.
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

  重新构建反序列得到的键值对实体数据。由于Hashtable不允许key重复，所以不存在key相同的两个及以上的键值对实体。所以如果发生了这种情况，那么就抛出异常。

 

Entry<K,V>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
private static class Entry<K,V> implements Map.Entry<K,V> {
    int hash;
    final K key;
    V value;
    Entry<K,V> next;

    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }

    protected Object clone() {
        return new Entry<>(hash, key, value,
                           (next==null ? null : (Entry<K,V>) next.clone()));
    }

    // Map.Entry Ops

    public K getKey() {
        return key;
    }

    public V getValue() {
        return 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.equals(e.getKey()) && value.equals(e.getValue());
    }

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

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

  Entry是Hashtable集合的内部类，实现了Map.Entry<K,V>接口。实际上散列表内部的存储结构就是一个Entry形式的数组，数组中的每个元素都是一个Entry实体。

  Entry中包含了四个字段：value（map集合中键值对的值内容），key（map集合中键值对的键内容），next（当前entry节点的下一个节点）和hash（map集合中键值对的键的hashcode值）。

  实体自身的hashcode计算方式是将当前实体的key的hashcode和value的hashcode求异或运算得到结果。

  比较两个实体是否相等，首先判断两个实体的类型是否一致，其次分别判断两个实体的key和value是否都相等。

 

Enumerator<T>

  Enumerator是Hashtable内部类，用来完成散列表内键值对实体的遍历。Enumerator实现了Enumeration和Iterator两个接口声明的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
    Entry[] table = Hashtable.this.table;
    int index = table.length;
    Entry<K,V> entry = null;
    Entry<K,V> lastReturned = null;
    int type;

    /**
     * 用来标记当前Enumerator实例是以Iterator还是Enumeration的身份进行遍历。
     * true为Iterator。
     */
    boolean iterator;

    protected int expectedModCount = modCount;

    /**
     * 初始化一个Enumerator实例。
     * type的值决定了遍历的基础：KEYS = 0; VALUES = 1; ENTRIES = 2
     */
    Enumerator(int type, boolean iterator) {
        this.type = type;
        this.iterator = iterator;
    }

    /**
     * 判断是否可以继续向后遍历。
     * 遍历Hashtable的底层数组，看能否找到一个非空的Entry实体，如果找到返回true，否则返回
     * false。
     */
    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;
    }

    /**
     * 遍历获取下一个元素。
     * 在初始化Enumerator时传入的字段type会在这个方法中决定遍历后返回的内容是什么。
     */
    public T nextElement() {
        Entry<K,V> et = entry;
        int i = index;
        Entry[] t = table;
        /* Use locals for faster loop iteration */
        while (et == null && i > 0) {
            et = t[--i];
        }
        entry = et;
        index = i;
        if (et != null) {
            Entry<K,V> 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();
    }

    /**
     * 删除一个元素。
     * 该操作只支持Iterator。
     */
    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;

            for (Entry<K,V> e = tab[index], 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();
        }
    }
}

 

涉及基础知识点

  1. NIL

 

参考文献

  1. NIL

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Map 05 - Hashtable
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-Hashtable.html