您现在的位置是：首页 > Java

当前栏目

【JAVA】七 JAVA Dictionary 一 HashTable

JAVA

2023-02-26 12:32:33 时间

# **【JAVA】七 JAVA Dictionary 一 Hashtable** #

![这里写图片描述][20160529232032016]

# **JDK API** #

java.util  
Class Dictionary

## **Direct Known Subclasses:** ##

Hashtable

--------------------

# **Dictionary** #

abstract class Dictionary 定义 ,如果看过我关于Map的介绍,那么你一定不陌生,此处的方法在java.util.Map中已经见到过.

public abstract
    class Dictionary<K,V> {
        
        public Dictionary() {}
        abstract public int size();
        abstract public boolean isEmpty();
        abstract public Enumeration<K> keys();
        abstract public Enumeration<V> elements();
        abstract public V get(Object key);
        abstract public V put(K key, V value);
        abstract public V remove(Object key);
    }

--------------------

# **Hashtable 属性** #

public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable {
        
    
        /**
         * 大家注意 这里的 Entry class implements java.util.Map.Entry 
         */
        private transient Entry[] table;
    
        /**
         * 哈希表中的条目的总数.
         * 还记的 HashMap吗 , 那里记录总数是用的 size 属性 . 
         */
        private transient int count;
    
        /**
         * 要调整大小的极限值（容量*默认计算阀值参数因子） 
         * (capacity * loadFactor).)
         */
        private int threshold;
    
        /**
         * 阀值参数因子
         */
        private float loadFactor;
    
        /**
         * 这个Hashtable结构修改的次数
         * 结构修改是那些改变的映射
         * Hashtable或修改其内部结构(例如重复)。
         * 这个字段是用来使迭代器的集合视图 Hashtable很快失败。
         * (见ConcurrentModificationException)。
         */
        private transient int modCount = 0;
    }

--------------------

# **Hashtable 构造方法** #

/**
         *  指定Hashtable 的初始大小 , 阀值参数因子
         */
        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);
        }
    
        /**
         * 指定Hashtable 的初始大小
         */
        public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
        }
    
        /**
         * 默认初始大小11     
         * 阀值参数因子 (0.75).
         */
        public Hashtable() {
        this(11, 0.75f);
        }
    
        /**
         * 接收 java.util.Map 子集 , 
         * 如果参数长度大于 11 ,那么新 Hashtable 长度是参数长度的 2 倍 .
         * 阀值参数因子 (0.75).
         */
        public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
        }

--------------------

# **Hashtable put方法** #

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

#### **不允许 null key** ####

> 关于Key不能是null的原因在Hashtable的hash方法中,直接调用了k.hashCode();那么如果k=null就会抛出NullPointerException.

#### **不允许 null value** ####

> null value 是在put方法中通过代码判断.抛出NullPointerException.

#### **int index = (hash & 0x7FFFFFFF) % tab.length** ####

#### **为什么要 hash & 0x7FFFFFFF ?** ####

> 答案是为了保证被模数是正整数,考虑到% tab.length模运算的符号取决于被模数 , int长度为32为,用hash & 0x7FFFFFFF(int最大值)那么得出的结果肯定是一个正整数 .

#### **为什么这里是用的取模运算符,不是向HashMap一样做的优化位运算呢?** ####

> 这里有hashmap的一篇文章可以参考  
> [http://blog.csdn.net/maguochao\_mark/article/details/51496513][http_blog.csdn.net_maguochao_mark_article_details_51496513]
> 
> 答案是不行的.  
> 还记得hashmap中长度的限制吗?  
> MUST be a power of two <= 1<<30 ; 长度必须是2的幂 , 且 size < 1<<30(1073741824).
> 
> 我们来看看1左移动31为值是多少?1<<31 = 2147483648,但是hashmap是用int作为长度size的类型,hashmap根本放不下这么大的数值,所以hashmap将最大size限制在size <= 1<<30(1073741824) .
> 
> 为什么是2的幂 , 这是hashmap做的优化操作,为了在计算hash时不用基本运算符进行取模操作.

--------------------

# **Hashtable hash方法** #

> put方法会调用hash方法计算Key的hashCode(),**当key为null的时候就会抛出 NullPointerException**

private int hash(Object k) {
            // hashSeed will be zero if alternative hashing is disabled.
            return hashSeed ^ k.hashCode();
        }

--------------------

# **Hashtable 扩大容量** #

> 在put方法中判断 count 大于等于 threshold 就会给Hashtable扩大容量,扩大容量和HashMap一样是非常消耗性能的操作,因为要重新计算hash值,元素越多越消耗性能.
> 
> Hashtable 初始情况下,容量11 , 阀值计算因子 0.75 ,阀值 8 .那么当Hashtalbe到达阀值时就会调用 rehash方法, (oldCapacity << 1) + 1 向左移动一位,相当于乘 2 ,+1 保证长度是一个奇数 .

#### **为什么 length \* 2 + 1 / hashtable保证长度是一个奇数** ####

> 先来说hashtable的设计思想,hashtable默认长度是一个奇数(当然,你也可以通过构造方法去指定),默认长度11 , 当发生第一次扩大容量 11 \* 2 + 1 = 23,长度 23 , 如果指定初始长度为 16 , 16 \* 2 + 1 = 33 ,其实hashtable 一直在保证长度是一个奇数 . 任意正整数在 \* 2 后都会成为一个偶数, 那么 +1 会是偶数成为一个奇数 . 奇数有什么效果呢?在做hash是的散列度会更大,hashtable在存储数据更加的分散.

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

--------------------

# **Hashtable 线程安全** #

> 来简单的看几个方法

public synchronized V put(K key, V value) ...
    public synchronized V get(Object key) ...
    public synchronized V remove(Object key) ...
    public synchronized int size() ...
    ...

--------------------

# **key value 容器 Entry实现Map.Entry** #

> 内部静态类Entry与HashMap.Entry一样都是实现了Map.Entry接口

private static class Entry<K,V> implements Map.Entry<K,V> {
        
    ...

--------------------

# **Hashtable添加值 hashCode 相同 / fail-fast机制** #

请参考我的另一篇文章HashMap添加值 hashCode 相同,实现原理相同 .

[http://blog.csdn.net/maguochao\_mark/article/details/51496513][http_blog.csdn.net_maguochao_mark_article_details_51496513]

[20160529232032016]: /images/20220722/aac874a90cd3475f8e65419d4e0278ce.png
[http_blog.csdn.net_maguochao_mark_article_details_51496513]: http://blog.csdn.net/maguochao_mark/article/details/51496513

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

【JAVA】七 JAVA Dictionary 一 HashTable

相关文章