Java 8 容器源码-Hashtable(2)

扫码关注公众号:Java 技术驿站

发送:vip
将链接复制到本浏览器,永久解锁本站全部文章

【公众号:Java 技术驿站】 【加作者微信交流技术,拉技术群】

作者:潘威威 出处:https://blog.csdn.net/panweiwei1994


上一篇文章翻译了Hashtable源码顶部注释,本文将详细讲解Hashtable的各个方法的实现。

Hashtable层次结构图

先来看看Hashtable的定义:

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable

从中我们可以了解到:

  • Hashtable<K,V>:HashMap是以key-value形式存储数据的
  • extends Dictionary<K,V>:Dictionary 类是一个抽象类,用来存储键/值对,作用和Map类相似。
  • implements Map<K,V>:实现了Map,实现了Map中声明的操作和default方法。
  • implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。
  • implements java.io.Serializable:表明该类是可以序列化的。

部分全局变量

下面是部分的全局变量,关于迭代器和枚举类相关的全局变量,在对应的方法或内部类类旁会给出。

    /**
     * hashtable存放的数据.
     */
    private transient Entry<?,?>[] table;

    /**
     * hashtable存放的entry的个数.
     */
    private transient int count;

    /**
     * hashtable进行扩容的临界值(这个值等于(int)(capacity * loadFactor))
     *
     * @serial
     */
    private int threshold;

    /**
     * 负载因子.
     *
     * @serial
     */
    private float loadFactor;

    /**
     * hashtable被结构型修改的次数。
     */
    private transient int modCount = 0;

Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

构造函数

Hashtable有四个构造函数

Hashtable( int initialCapacity, float loadFactor)

    /**
     * 使用指定参数初始化容量和指定参数负载因子来构造一个空的hashtable.
     *
     * @param      initialCapacity   指定参数初始化容量
     * @param      loadFactor        指定参数负载因子
     * @exception  IllegalArgumentException  如果initialCapacity小于0或者负载因子为非正数。
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        //如果指定参数初始化容量小于0,抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        //如果指定参数负载因子为非正数,抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
        //初始化hashtable的loadFactor、table、threshold属性
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        //如果initialCapacity * loadFactor超出了MAX_ARRAY_SIZE,就使用MAX_ARRAY_SIZE 作为threshold
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

Hashtable( int initialCapacity)

    /**
     * 使用指定参数初始化容量和默认负载因子(0.75)来构造一个空的hashtable.
     *
     * @param     initialCapacity   指定参数初始化容量
     * @exception IllegalArgumentException 如果initialCapacity小于0
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

Hashtable()

    /**
     * 使用默认初始化容量(11)和默认负载因子(0.75)来构造一个空的hashtable.
     *
     * 这里可以看到,Hashtable默认初始化容量为16,而HashMap的默认初始化容量为11。
     */
    public Hashtable() {
        this(11, 0.75f);
    }

**Hashtable( Map t)** ``` /** * 使用指定的键值对集合t来构造hashtable。 * * @param t 指定的键值对集合 * @throws NullPointerException 如果指定的键值对集合为null * @since 1.2 */ public Hashtable(Map t) { //初始hashMap this(Math.max(2*t.size(), 11), 0.75f); //将t中的键值对插入到hashtable中 putAll(t); } ``` ## 常用方法 **size()** ``` /** * 返回hashtable中key的个数 * * @return 返回hashtable中key的个数 */ public synchronized int size() { return count; } ``` **isEmpty()** ``` /** * 判断hashtable中是否有键值对映射. * * @return hashtable中没有键值对映射,返回true,否则返回false */ public synchronized boolean isEmpty() { return count == 0; } ``` **keys()** ``` /** * 返回hashtable中key的枚举. * * @return 返回hashtable中key的枚举. * @see Enumeration * @see #elements() * @see #keySet() * @see Map */ public synchronized Enumeration keys() { return this.getEnumeration(KEYS); } ``` **elements()** ``` /** * 返回hashtable中value的枚举. * * @return 返回hashtable中value的枚举 * @see java.util.Enumeration * @see #keys() * @see #values() * @see Map */ public synchronized Enumeration elements() { return this.getEnumeration(VALUES); } ``` **contains( Object value)** ``` /** * 返回hashtable中是否含有指定参数value。 * 这个方法比containsKey方法代价更昂贵 * * @param value 指定参数value * @return hashtable中含有指定参数value * @exception NullPointerException value为null */ public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); } Entry tab[] = table; //需要遍历hashtable的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; }


**containsValue( Object value)**
/**
 * 返回hashtable中是否含有指定参数value。
 * 这个方法比containsKey方法代价更昂贵
 *
 * @param      value   指定参数value
 * @return     hashtable中含有指定参数value
 * @exception  NullPointerException  value为null
 * @since 1.2
 */
public boolean containsValue(Object value) {
    return contains(value);
}

**containsKey( Object key)**
/**
 * Tests if the specified object is a key in this hashtable.
 * 判断hashtable是否含有指定参数key
 * @param   key   指定参数key
 * @return  hashtable含有指定参数key,返回true,否则返回false
 * @throws  NullPointerException  如果key为null
 * @see     #contains(Object)
 */
public synchronized boolean containsKey(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //因为不需要从头开始遍历table,所以代价比containsValue要小
    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;
}

因为不需要从头开始遍历table,所以代价比containsValue要小。 这里可以看到,Hashtable和HashMap确认key在数组中的索引的方法不同。 - Hashtable 通过index = (hash & 0x7FFFFFFF) % tab.length;来确认 - HashMap 通过i = (n - 1) & hash;来确认 **get( Object key)**
/**
 * 返回指定参数key映射的value,如果没有对应映射,返回null
 *
 * @param key 指定参数
 * @return 返回指定参数key映射的value,如果没有对应映射,返回null
 * @throws NullPointerException 如果指定参数key为null
 * @see     #put(Object, Object)
 */
@SuppressWarnings("unchecked")
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;
}

**常量MAX\_ARRAY\_SIZE**
/**
 * 分派给arrays的最大容量
 * 为什么要减去8呢?
 * 因为某些VM会在数组中保留一些头字,尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

**rehash()**
/**
 * 增加hashtable的容量,为了更有效地存放和找到它的entry。
 * 当键值对的数量超过了临界值(capacity*load factor)这个方法自动调用
 * 长度变为原来的2倍+1
 *
 */
@SuppressWarnings("unchecked")
protected void rehash() {
    //记录旧容量
    int oldCapacity = table.length;
    //记录旧桶的数组
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //新的容量为旧的容量的2倍+1
    int newCapacity = (oldCapacity << 1) + 1;
    //如果新的容量大于容量的最大值MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        //如果旧容量为MAX_ARRAY_SIZE,容量不变,中断方法的执行
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        //如果旧容量不为MAX_ARRAY_SIZE,新容量变为MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    //创建新的数组,容量为新容量
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    //结构性修改次数+1
    modCount++;
    //计算扩容的临界值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //将旧的数组中的键值对转移到新数组中
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

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

看完代码,我们可以总结出rehash的总体思路为: 1. 新建变量_新的容量_,值为旧的容量的2倍+1 2. 如果新的容量大于容量的最大值MAX\_ARRAY\_SIZE 1. 如果旧容量为MAX\_ARRAY\_SIZE,容量不变,中断方法的执行 2. 如果旧容量不为MAX\_ARRAY\_SIZE,新容量变为MAX\_ARRAY\_SIZE 3. 创建新的数组,容量为新容量 4. 将旧的数组中的键值对转移到新数组中 这里可以看到,一般情况下,HashMap扩容后容量变为原来的两倍,而Hashtable扩容后容量变为原来的两倍+1。 **addEntry( int hash, K key, V value, int index)**
/**
 * 根据指参数向table中添加entry
 * put方法会使用此方法
 */
private void addEntry(int hash, K key, V value, int index) {
    //结构性修改次数+1
    modCount++;
    //记录现在的table
    Entry<?,?> tab[] = table;
    //如果现在的entry数量大于临界值
    if (count >= threshold) {
        // 扩容
        rehash();
        //记录新的table
        tab = table;
        //重新计算key的hash
        hash = key.hashCode();
        //重新计算index
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // 创建一个新的entry
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //将entry添加到table中
    tab[index] = new Entry<>(hash, key, value, e);
    //table大小+1
    count++;
}

**put(K key, V value)**
/**
 * 添加指定键值对到hashtable中
 * 被添加的键值对中的key和value都不能为null
 *
 * value可以通过get方法被取出。
 *
 * @param      key     the hashtable key
 * @param      value   the value
 * @return     如果hashtable中已经存在key,则返回原来的value
 * @exception  NullPointerException  如果key或者value为null
 * @see     Object#equals(Object)
 * @see     #get(Object)
 */
public synchronized V put(K key, V value) {
    // 确认value不为null
    if (value == null) {
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //找到key在table中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //获取key所在索引的entry
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    //遍历entry,判断key是否已经存在
    for(; entry != null ; entry = entry.next) {
        //如果key已经存在
        if ((entry.hash == hash) && entry.key.equals(key)) {
            //保存旧的value
            V old = entry.value;
            //替换value
            entry.value = value;
            //返回旧的value
            return old;
        }
    }
    //如果key在hashtable不是已经存在,就直接将键值对添加到table中,返回null
    addEntry(hash, key, value, index);
    return null;
}

从代码中可以总结出Hashtable的put方法的总体思路: 1. 确认value不为null。如果为null,则抛出异常 2. 找到key在table中的索引,获取key所在位置的entry 3. 遍历entry,判断key是否已经存在 4. 如果key已经存在,替换value,返回旧的value 5. 如果key在hashtable不是已经存在,就直接添加,否则直接将键值对添加到table中,返回null 在方法中可以看到,在遍历桶中元素时,是按照链表的方式遍历的。可以印证,HashMap的桶中可能为链表或者树。但Hashtable的桶中只可能是链表。 **remove( Object key)**
/**
 * 删除hashtable中参数key映射的键值对。如果参数key在hashtable不存在,方法不做任何操作。
 *
 * @param   key   参数key
 * @return  参数key映射的value,如果不存在对应的映射,返回null。
 * @throws  NullPointerException  如果key为null
 */
public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历entry,如果entry中存在key为参数key的键值对,就删除键值对,并返回键值对的value
    for(Entry<K,V> 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;
        }
    }
    //如果不存在key为参数key的键值对,返回value
    return null;
}

从代码中可以总结出Hashtable的remove方法的总体思路: 1. 找到key在table中的索引,获取key所在位置的entry 2. 遍历entry,判断key是否已经存在 3. 如果key存在,删除key映射的键值对,返回旧的value 4. 如果key在hashtable不存在,返回null **putAll( Map<? extends K, ? extends V> t)**
/**
 * 将指定t中所有的键值对复制到hashtable中。
 * 如果t中的键值对的key在hashtable中已经存在,就替换。
 *
 * @param t 指定参数t
 * @throws NullPointerException 如果指定参数t为null
 * @since 1.2
 */
public synchronized void putAll(Map<? extends K, ? extends V> t) {
    //遍历参数t中所有的键值对,将其复制到hashtable中
    for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
        put(e.getKey(), e.getValue());
}

**clear()**
/**
 * 清空hashtable中所有的键值对
 */
public synchronized void clear() {
    Entry<?,?> tab[] = table;
    modCount++;
    //遍历hashtable中所有的entry,将其置为null,
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    //修改hashtable大小为0
    count = 0;
}

**clone()**
/**
 * 创建一个hashtable的浅拷贝。
 * hashtable所有的结构都被拷贝,但键值对没有拷贝。
 * 这是个相对来说代价比较大的操作。
 *
 * @return  一个hashtable的浅拷贝
 */
public synchronized Object clone() {
    try {
        //调用父类的clone方法,浅拷贝一个HashTable对象t
        Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
        //给table属性赋值
        t.table = new Entry<?,?>[table.length];
        //遍历原散列数组,单独地拷贝并生成每个桶的链表。
        for (int i = table.length ; i-- > 0 ; ) {
            t.table[i] = (table[i] != null)
                ? (Entry<?,?>) table[i].clone() : null;
        }
        //给keySet属性赋值
        t.keySet = null;
        //给entrySet属性赋值
        t.entrySet = null;
        //给values 属性赋值
        t.values = null;
        //给modCount 属性赋值
        t.modCount = 0;
        //返回浅拷贝
        return t;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

**toString()**
/**
 * 返回hashtable的字符串表现形式。
 *
 * @return  hashtable的字符串表现形式。
 */
public synchronized String toString() {
    int max = size() - 1;
    //如果hashtable大小为0,返回"{}"
    if (max == -1)
        return "{}";

    //使用StringBuilder
    StringBuilder sb = new StringBuilder();
    //获取entry迭代器
    Iterator<Map.Entry<K,V>> it = entrySet().iterator();

    sb.append('{');
    //遍历hashtable
    for (int i = 0; ; i++) {
        Map.Entry<K,V> e = it.next();
        K key = e.getKey();
        V value = e.getValue();
        //组装hashtable的字符串表示
        sb.append(key   == this ? "(this Map)" : key.toString());
        sb.append('=');
        sb.append(value == this ? "(this Map)" : value.toString());

        //i=max=size() - 1,到了最后一个entry
        if (i == max)
            return sb.append('}').toString();
        sb.append(", ");
    }
}

**getEnumeration( int type)**
/**
 * 获取Hashtable的枚举类对象
 *
 * @param type 0——返回key的枚举类对象/迭代器;1——返回values的枚举类对象/迭代器,2——返回entry的枚举类对象/迭代器
 */
private <T> Enumeration<T> getEnumeration(int type) {
    if (count == 0) {
        return Collections.emptyEnumeration();
    } else {
        //false,意味着不是迭代器,如果为true,说明返回的是迭代器
        return new Enumerator<>(type, false);
    }
}

// Enumerations/Iterations的类型。
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;

**getIterator( int type)**
/**
 * 获取Hashtable的迭代器
 *
 * @param type 0——返回key的枚举类对象/迭代器;1——返回values的枚举类对象/迭代器,2——返回entry的枚举类对象/迭代器
 */
private <T> Iterator<T> getIterator(int type) {
    if (count == 0) {
        return Collections.emptyIterator();
    } else {
        //true,意味着是迭代器,如果为false,说明返回的不是迭代器
        return new Enumerator<>(type, true);
    }
}

// Enumerations/Iterations的类型。
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;

## 集合视图 **视图全局变量**
/**
 * 每个域在第一次视图被请求时被初始化。
 * 视图是无状态的,所以每一种视图,没有理由去创建第二个。
 */
private transient volatile Set<K> keySet;
private transient volatile Set<Map.Entry<K,V>> entrySet;
private transient volatile Collection<V> values;

**keySet()方法和KeySet类**
/**
 * 返回hashtable中包含的所有key的set视图。
 *
 * set视图是由hashtable返回的,所以改变hashtable会改变set,反之亦然。
 *
 * 如果迭代器在遍历set时,hashtable被修改(除了该迭代器自己的remove方法修改),迭代器的结果是不确定的。
 *
 * set支持元素的删除,删除操作会删除hashtable中对应的键值对,删除操作包括Iterator.remove、Set.remove、removeAll、retainAll、clear。不支持add或者addAll方法。
 *
 * @since 1.2
 */
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();
    }
}

**entrySet()方法和EntrySet类**
/**
 * 返回hashtable中包含的所有entry的set视图。
 *
 * set视图是由hashtable返回的,所以改变hashtable会改变set,反之亦然。
 *
 * 如果迭代器在遍历set时,hashtable被修改(除了该迭代器自己的remove方法修改),迭代器的结果是不确定的。
 *
 * set支持元素的删除,删除操作会删除hashtable中对应的键值对,删除操作包括Iterator.remove、Set.remove、removeAll、retainAll、clear。不支持add或者addAll方法。
 *
 * @since 1.2
 */
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 = key.hashCode();
        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<?,?> entry = (Map.Entry<?,?>) o;
        Object key = entry.getKey();
        Entry<?,?>[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

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

**values()方法和ValueCollection类**
/**
 * 返回hashtable中包含的所有value的collection视图。
 *
 * collection视图是由hashtable返回的,所以改变hashtable会改变collection,反之亦然。
 *
 * 如果迭代器在遍历collection时,hashtable被修改(除了该迭代器自己的remove方法修改),迭代器的结果是不确定的。
 *
 * collection支持元素的删除,删除操作会删除hashtable中对应的键值对,删除操作包括Iterator.remove、Collection.remove、removeAll、retainAll、clear。不支持add或者addAll方法。
 *
 * @since 1.2
 */
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();
    }
}

## 比较和哈希 **equals( Object o)**
/**
 * 由Map接口的定义比较指定参数和hashtable是否相等。
 *
 * @param  o 指定参数
 * @return 如果相等,返回true
 * @see Map#equals(Object)
 * @since 1.2
 */
public synchronized boolean equals(Object o) {
    //如果参数就是hashtable,返回true
    if (o == this)
        return true;

    //如果参数o不是map,返回false
    if (!(o instanceof Map))
        return false;
    Map<?,?> t = (Map<?,?>) o;
    //如果大小不同,返回false
    if (t.size() != size())
        return false;

    try {
        //遍历hashtable,如果所有的key和value在参数o中有一条没有对应,说明不等,返回false。
        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;
    }
    //所有的key和value都能对应上,返回true
    return true;
}

**hashCode()**
/**
 * 根据Map接口的定义返回哈希值
 *
 * @see Map#hashCode()
 * @since 1.2
 */
public synchronized int hashCode() {
    /*
     * 负的负载因子表明hashcode的计算还在进行中。
     */
    int h = 0;
    //当hashtable大小为0或者负载因子小于0
    if (count == 0 || loadFactor < 0)
        //返回0
        return h;  // Returns zero

    //将loadFactor变为负数
    loadFactor = -loadFactor;  // Mark hashCode computation in progress
    Entry<?,?>[] tab = table;
    //遍历hashtable中所有的entry
    for (Entry<?,?> entry : tab) {
        //如果entry不为null
        while (entry != null) {
            //hashcode加entry的hashcode
            h += entry.hashCode();
            //准备entry的下个entry
            entry = entry.next;
        }
    }
    //将loadFactor变为正数
    loadFactor = -loadFactor;  // Mark hashCode computation complete
    //返回hashcode
    return h;
}
## 其他方法

**getOrDefault( Object key, V defaultValue)**

/**
 * 返回指定参数key映射的value,如果没有对应映射,返回默认值defaultValue
 *
 * @param key 指定参数key
 * @param defaultValue 默认值
 * @return 返回指定参数key映射的value,如果没有对应映射,返回默认值
 * @throws NullPointerException 如果指定参数key为null
 * @see     #put(Object, Object)
 * @see     #get()
 */
 @Override
public synchronized V getOrDefault(Object key, V defaultValue) {
    V result = get(key);
    return (null == result) ? defaultValue : result;
}

待补充forEach( BiConsumer<? super K, ? super V> action) 待补充replaceAll( BiFunction<? super K, ? super V, ? extends V> function) **putIfAbsent( K key, V value)**
/**
 * 在hashtable中插入参数key和value组成的键值对,如果key已经存在,返回旧value,如果旧value为null,则用参数value替换旧value
 *
 * @return 如果key在hashtable中存在,返回旧value
 */
@Override
public synchronized V putIfAbsent(K key, V value) {
    //判断value是否为null,如果为null,抛出NullPointerException
    Objects.requireNonNull(value);

    // 确认key是不是已经才hashtable中存在
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //获取key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //根据key在hashtable中的索引获取对应entry
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    //遍历entry中的所有键值对,如果key已经存在,返回旧value,如果旧value为null,则用参数value替换旧value
    for (; entry != null; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            if (old == null) {
                entry.value = value;
            }
            return old;
        }
    }
    //如果,key在entry中不存在,添加entry,返回null
    addEntry(hash, key, value, index);
    return null;
}

**remove( Object key, Object value)**
/**
 * 在hashtable中删除key和value都和参数key和参数value匹配的键值对
 *
 * @return 如果删除成功,返回true
 */
@Override
public synchronized boolean remove(Object key, Object value) {
    //如果value为null,抛出空指针异常
    Objects.requireNonNull(value);

    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //根据key在hashtable中的索引获取对应entry
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历entry,如果entry中存在和参数value和参数key都存在的键值对,则删除这个键值对,并返回true
    for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            e.value = null;
            return true;
        }
    }
    //如果entry中不存在和参数value和参数key都存在的键值对,返回false
    return false;
}

**replace( K key, V oldValue, V newValue)**
/**
 * 在hashtable中查找key和value都和参数key和参数oldValue都匹配的键值对,如果找到,将键值对的value替换为参数newValue
 *
 * @return 如果替换成功,返回true
 */
@Override
public synchronized boolean replace(K key, V oldValue, V newValue) {
    //如果oldValue或者newValue为null,抛出空指针异常
    Objects.requireNonNull(oldValue);
    Objects.requireNonNull(newValue);
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //根据key在hashtable中的索引获取entry
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历entry,如果key和value都和参数key和参数oldValue都匹配的键值对,如果找到,将键值对的value替换为参数newValue,返回true。如果都不匹配,返回false
    for (; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            if (e.value.equals(oldValue)) {
                e.value = newValue;
                return true;
            } else {
                return false;
            }
        }
    }
    //如果都不匹配,返回false
    return false;
}

**replace( K key, V value)**
/**
 * 在hashtable中查找key和参数key匹配的键值对,如果找到,将键值对的value替换为参数value
 *
 * @return 如果替换成功,返回键值对的旧value
 */
@Override
public synchronized V replace(K key, V value) {
    //如果value为null,抛出空指针异常
    Objects.requireNonNull(value);
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //根据key在hashtable中的索引获取entry
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历entry,如果存在key和参数key匹配的键值对,将键值对的value替换为参数value,返回true。如果都不匹配,返回null
    for (; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    return null;
}

## 序列化和反序列化 **writeObject( java.io.ObjectOutputStream s)**
/**
 * 序列化hashtable到ObjectOutputStream中
 * 将hashtable的总容量table.length、实际容量count、键值对映射写入到ObjectOutputStream中。键值对映射序列化时是无序的。
 */
private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
    Entry<Object, Object> entryStack = null;

    synchronized (this) {
        // 写入临界值和负载因子
        s.defaultWriteObject();

        // 写入总容量和实际大小
        s.writeInt(table.length);
        s.writeInt(count);

        //
        for (int index = 0; index < table.length; index++) {
            Entry<?,?> entry = table[index];

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

    // 写入hashtable键值对到ObjectOutputStream中
    while (entryStack != null) {
        s.writeObject(entryStack.key);
        s.writeObject(entryStack.value);
        entryStack = entryStack.next;
    }
}

**readObject( java.io.ObjectInputStream s)**
/**
 * 反序列化
 */
private void readObject(java.io.ObjectInputStream s)
     throws IOException, ClassNotFoundException
{
    // 读出临界值和负载因子
    s.defaultReadObject();

    // 验证负载因子,忽略临界值,因为它会被重新计算
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new StreamCorruptedException("Illegal Load: " + loadFactor);

    // 读出hashtable总容量和实际大小
    int origlength = s.readInt();
    int elements = s.readInt();

    // 验证实际大小
    if (elements < 0)
        throw new StreamCorruptedException("Illegal # of Elements: " + elements);

    // 重新计算总容量,使其大于(实际大小/负载因子)+1
    origlength = Math.max(origlength, (int)(elements / loadFactor) + 1);

    // Compute new length with a bit of room 5% + 3 to grow but
    // no larger than the clamped original length.  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 + elements / 20) / loadFactor) + 3;
    if (length > elements && (length & 1) == 0)
        length--;
    length = Math.min(length, origlength);
    table = new Entry<?,?>[length];
    threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
    count = 0;

    // 读出所有的key-value键值对,并将其添加到table中
    for (; elements > 0; elements--) {
        @SuppressWarnings("unchecked")
            K key = (K)s.readObject();
        @SuppressWarnings("unchecked")
            V value = (V)s.readObject();
        // sync is eliminated for performance
        reconstitutionPut(table, key, value);
    }
}

**reconstitutionPut( Entry<?,?>\[\] tab, K key, V value)**
/**
 * 此方法被readObject方法使用。
 * 提供该方法是因为put方法是可重写的,不应该被readObject调用。
 *
 * 该方法和put方法在以下几个方面不同:
 * 从hashtable容量被初始化开始,不扩容。
 * modCount不增长
 * 不同步,因为我们在创建一个新的实例
 * 不需要返回值
 */
private void reconstitutionPut(Entry<?,?>[] 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 = 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)) {
            throw new java.io.StreamCorruptedException();
        }
    }
    // Creates the new entry.
    @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

```

总结

Hashtable与HashMap不同点

关于Hashtable的源码就看到这,从代码中我们可以总结出Hashtable与HashMap的几个不同点:

不同点 HashMap Hashtable
数据结构 数组+链表+红黑树 数组+链表
继承的类不同 继承AbstractMap 继承Dictionary
是否线程安全
性能高低
默认初始化容量 16 11
扩容方式不同 原始容量x2 原始容量x2 + 1
底层数组的容量为2的整数次幂 要求一定为2的整数次幂 不要求
确认key在数组中的索引的方法不同 i = (n - 1) & hash; index = (hash & 0x7FFFFFFF) % tab.length;
遍历方式 Iterator(迭代器) Iterator(迭代器)和Enumeration(枚举器)
Iterator遍历数组顺序 索引从小到大 索引从大到小

Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

赞(1) 打赏
版权归原创作者所有,任何形式的转载请联系博主:daming_90:Java 技术驿站 » Java 8 容器源码-Hashtable(2)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    一针见血

    1113周前 (10-30)回复

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏