【Java集合】Hashtable

2021-09-26 本文已影响0人 Guxxxd

继承结构

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

数据存储结构

数组 + 单项链表（线程安全）

写在前面的一些方法、说明

!!! key和value都不可为null
protected void rehash() 扩容

     protected void rehash() {
        int oldCapacity = table.length;
        HashtableEntry<?,?>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1; // 2倍+1
        if (newCapacity - MAX_ARRAY_SIZE > 0) { // 保证table桶的大小不超过 MAX_ARRAY_SIZE
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        // 实例化新容量的HashtableEntry数组
        HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];

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

        // 两层遍历，第一层遍历数组
        for (int i = oldCapacity ; i-- > 0 ;) {
            // 第二层遍历链表
            for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
                HashtableEntry<K,V> e = old;
                old = old.next;

                // 重新计算当前元素应处于新table中的位置
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                // 如果index相同位置上插入节点，总是插在队头
                e.next = (HashtableEntry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

private void addEntry(int hash, K key, V value, int index)添加元素

    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        HashtableEntry<?,?> tab[] = table;
        if (count >= threshold) { // 存储的元素大小到达阀值，触发扩容
            // Rehash the table if the threshold is exceeded
            rehash();

            // 扩容之后，重新key的hash值和index
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        // 新添加的元素总是插入在对头位置
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
        tab[index] = new HashtableEntry<>(hash, key, value, e);
        count++;
    }

一、增

public synchronized V put(K key, V value)

     public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) { // value不可null
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
        // 遍历链表查找元素，找到即修改key对应的value值
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        // 找不着即创建新对象插入
        addEntry(hash, key, value, index);
        return null;
    }

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

     public synchronized void putAll(Map<? extends K, ? extends V> t) {
        // 遍历入参map的Map.Entry,逐一put
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }

public synchronized V putIfAbsent(K key, V value) 如果存在key-value键值对，且value为null，才会赋值新value

    @Override
    public synchronized V putIfAbsent(K key, V value) {
        Objects.requireNonNull(value);

        // Makes sure the key is not already in the hashtable.
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
        for (; entry != null; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                // 如果Map中存在key对应的value值，且不为null，不会覆盖老值，为null，则赋值新value
                if (old == null) {
                    entry.value = value;
                }
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

二、删

public synchronized V remove(Object key)匹配key移除

    public synchronized V remove(Object key) {
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
        for(HashtableEntry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
            // 找到key对应存储的节点
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;// 移除key对应节点，链接前后节点
                } else { // key对应节点在队头位置
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null; // 释放资源 help gc
                return oldValue;
            }
        }
        return null;
    }

public synchronized boolean remove(Object key, Object value)同时匹配key-value移除，也可用作查找当前Map中是否包含某对key-value

    @Override
    public synchronized boolean remove(Object key, Object value) {
        Objects.requireNonNull(value); // value不可null

        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
        for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
            // 同时比较key 和 value
            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;
            }
        }
        return false;
    }

三、改

public synchronized V replace(K key, V value)将key对应的老value替换为入参value

    @Override
    public synchronized V replace(K key, V value) {
        Objects.requireNonNull(value);
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
        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;
    }

public synchronized boolean replace(K key, V oldValue, V newValue)将key-oldValue对应的oldValue替换为newValue

    @Override
    public synchronized boolean replace(K key, V oldValue, V newValue) {
        Objects.requireNonNull(oldValue);
        Objects.requireNonNull(newValue);
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
        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;
                }
            }
        }
        return false;
    }

public synchronized void clear()清空所有

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

四、查

public synchronized V get(Object key)key 取 value

    public synchronized V get(Object key) {
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

public synchronized boolean contains(Object value)是否包含此value

    public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }

        HashtableEntry<?,?> tab[] = table;
        for (int i = tab.length ; i-- > 0 ;) {
            for (HashtableEntry<?,?> e = tab[i] ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

public boolean containsValue(Object value)

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

public synchronized boolean containsKey(Object key)是否包含此key

    public synchronized boolean containsKey(Object key) {
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }

private <T> Enumeration<T> getEnumeration(int type)，type = KEYS、VALUES

    private <T> Enumeration<T> getEnumeration(int type) {
        if (count == 0) {
            return Collections.emptyEnumeration();
        } else {
            return new Enumerator<>(type, false);
        }
    }

    private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
              ·················
            public boolean hasMoreElements() {
            HashtableEntry<?,?> e = entry;
            int i = index;
            HashtableEntry<?,?>[] t = table;
            /* Use locals for faster loop iteration */
            while (e == null && i > 0) {
                e = t[--i];
            }
            entry = e;
            index = i;
            return e != null;
        }

        @SuppressWarnings("unchecked")
        public T nextElement() {
            HashtableEntry<?,?> et = entry;
            int i = index;
            HashtableEntry<?,?>[] t = table;
            /* Use locals for faster loop iteration */
            while (et == null && i > 0) {
                et = t[--i];
            }
            entry = et;
            index = i;
            if (et != null) {
                HashtableEntry<?,?> e = lastReturned = entry;
                entry = e.next;
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
            }
            throw new NoSuchElementException("Hashtable Enumerator");
        }
          ·····················
    }

public synchronized Enumeration<K> keys()

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

public synchronized Enumeration<V> elements()

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

public Set<K> keySet() 获取key的Set集合

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

    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()获取存储Entry对象的Set集合

   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();
            HashtableEntry<?,?>[] tab = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (HashtableEntry<?,?> 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();
            HashtableEntry<?,?>[] tab = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

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

public Collection<V> values() 获取存储所有value的集合

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

【Java集合】Hashtable

继承结构

数据存储结构

写在前面的一些方法、说明

一、增

二、删

三、改

四、查

猜你喜欢

热点阅读