新手读源码__HashTable和HashMap，青年人和老年人的碰撞

程序员文章站 2022-05-12 11:09:37

...

前言

看完了HashMap之后又来到了HashTable，感觉集合也是新手一大不得不迈出去的坎哈～不过最骚的是JDK9里面HashMap和HashTable的实现不大一样 - -，又得重头开始读源码咯～

HashTable

hashTable也是键值对的散列表，大方向上和HashMap差不多，究竟是什么地方不一样呢？让我们先看看源码，看看底层实现。注意HashTable属于老牌了，并没有对它优化，但是之前的HashMap已经优化了！所以HashTable还是旧的实现方法

维护的属性

    private transient Entry<?,?>[] table;//hash表
    private transient int count;         //表容纳的元素个数
    private int threshold;               //阀值
    private float loadFactor;           //装载因子
    private transient int modCount = 0;

构造函数

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

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

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

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

和hashMap第一点不一样：容量！

默认的容量是11，而不是16
初始指定的容量是多少就是多少，不需要经过转变成为2的倍数
装载因子是初始容量的0.75，但是阀值是0.75×容量并且取整数，但是不超过最大值

put加入键值对

    public synchronized V put(K key, V value) {
        // 保证值不能为空
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        // 直接用的Hash值加求余计算的 index，看出HashMap在这方面的优化
        int hash = key.hashCode();
        // 对hash取正
        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;
    }

0.0 不得不说这里面的实现比HashMap简单多了

全链表，没有树结构
键值对，键值都不能为空，但是hashmap可以
索引求法用的简单取正然后求余，hashmap用了一系列的hash运算来获得索引

    private void addEntry(int hash, K key, V value, int index) {
        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // 扩容rehash
            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];
        //  这里好像是链表的头插法，hashMap是尾插
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }

从链表而言链表的添加方法和HashMap有点不一样，HashMap是尾插，它是头插

扩容

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

        // 新容量2*old+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;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        // 新阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        // 将table指向新的table
        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;
            }
        }
    }

和HashMap做对比

hashMap是容量*2, 阀值*2，HashTable是容量*2+1,阀值0.75*新容量
hashMap通过高位来再散列旧表的元素，hashTable对新容量重新计算index，hashMap在这方面还是做了优化的

get

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

和HashMap差不多，也是算index然后遍历，返回，别的方法个人觉得不用追究了，新手嘛，先掌握一些重要的

对比！终极PK

继承什么的- -，反正我是记不住了！暂时不谈～
1、线程安全
HashTable是线程安全的，HashMap不安全，由于楼主是个新手，还没学到安全什么的，暂时放一放

2、初始容量和扩容不同
HashMap：16+12，或者给定一个初始取最近的2的指数然后阀值取0.75，扩容都是2倍

HashTable：11+(int) 0.75*11，给定一个容量就用这个容量阀值取其(int)0.75,扩容2*oldCap+1,阀值0.75

3、hash计算index不同，hashMap先进一些，具体参照上文

4、数据结构
HashMap ：数组+链表+红黑树
HashTable：数组+链表

5、链表的插法
HashMap：尾插
HashTable：头插

6、null
HashMap允许null
HashTable都不允许null

7、历史遗留，HashTable还用了Enumeration

总的来说，hashMap的性能不用说肯定比HashTable，明显HashTable年纪大了，也偏繁重了一些，但是线程安全，之后还有HashMap安全的优化Map，期待把～今天学习完成～源码面前，了无秘密，HashMap我看了两条- -才理解过来了，它我只看了3小时不到，更多的是记录对比