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

╰+哭是因爲堅強的太久メ 2022-05-25 22:56 154阅读 0赞

## 前言 ##

看完了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(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小时不到，更多的是记录对比