HashMap和HashTable简单总结 - 程序员大晖 Blog

HashMap可以有一个null key 可以有多个null value,但是在hashtable中,null key和null value都会抛出空指针异常,所以在hashmap中不能使用 get(key)的结果是否为null来判断是否存在该键值,因为可能这个key存储的数据就是null
HashTable是线程安全的,使用方法级别的synchronized上锁,大大降低了效率

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

HashTable在jdk1.8及以后都加入了fail-fast机制,和hashmap一样了
HashTable的扩容和hash函数使用的策略和hashmap不一样:

构造方法,就是直接按照指定的容量初始化数组大小的

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

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;
        //计算hash值,直接使用hashCode,没有进行右移异或  
        int hash = key.hashCode();
        //使用的就是取余操作来定位hash槽位置,这里先与0x7FFFFFFF,是为了去除最高位的符号位  
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        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;
    }

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

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //如果超出阈值,则扩容,重新hash
            rehash();

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

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

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

        // overflow-conscious code
        //扩容方法不是扩大为原来的两倍,而是直接变为2n+1
        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;
        }
        .......

HashTable这样的扩容方式,使得数组长度是奇数,并且其自身又是采用的取余操作来作为hash函数的策略(hash & 0x7FFFFFFF) % tab.length,所以这样相比于hashmap的与2的n次幂-1进行&操作,虽然速度比不上二进制&操作,但是使数据分布更加均匀;
扩容方式也不一样,hashtable每次扩容就是扩大为2n+1 int newCapacity = (oldCapacity << 1) + 1;,

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/09/16 15:14