HashMap和Hashtable区别

上次我们介绍过了集合类中ArrayList和linkedList的区别，这次介绍一下集合类中映射存储映射关系的HashMap和Hashtable区别

同样，我们从源码进行分析

1. 基础结构 1.1 HashMap

HashMap的底层存储为Node类型的数组，每个数组元素记录了每个Node链表的第一个节点
Node中保存每个元素的以下内容
- hash ：key的哈希值
- key ：节点的key，类型和定义HashMap时的key相同
- value ：节点的value，类型和定义HashMap时的value相同
- next ：该节点的下一节点
```
transient Node[] table;

Node(int hash, K key, V value, HashMap.Node next)
{
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}
```
这种数组+链表的数据结构，使得HashMap可以较为高效的管理每一个节点

1.2 HashTable

HashTable底层以Entry数组存储每一个键值对

private transient Entry[] table;

protected Entry(int hash, K key, V value, Entry next) {
    this.hash = hash;
    this.key =  key;
    this.value = value;
    this.next = next;
}

2. 初始化大小 2.1 HashMap

对于HashMap来说，其源码中直接定义了DEFAULT_INITIAL_CAPACITY，初始化大小为1<<4 即 2⁴=16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

如果HashMap初始化的时候指定了容量，HashMap会把这个容量修改为2的倍数，具体分析请看代码注释

//HashMap最大容量为1<<30=1073741824(约为11亿)
static final int MAXIMUM_CAPACITY = 1 << 30

public HashMap(int initialCapacity, float loadFactor)
{
    //如果初始化容量小于0报错
    if (initialCapacity < 0)
    {
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    }
    //如果初始化容量大于最大容量，将容量设置为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
    {
        initialCapacity = MAXIMUM_CAPACITY;
    }
    //如果加载因子小于0或者不是浮点数
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
    {
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    }
    this.loadFactor = loadFactor;
    //调用优化数组大小的方法(调整为2的倍数)
    this.threshold = tableSizeFor(initialCapacity);
}

//优化数组大小   将其变为2的倍数
static final int tableSizeFor(int cap)
{
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //如果优化容量大于最大容量，将容量设置为最大值，否则设置为n+1
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2.2 Hashtable

对于Hashtable来说，其在默认构造函数中直接进行初始化大小定义，值为11，如下所示

public Hashtable() 
{
    this(11, 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);
}

其最大容量为 Integer.MAX_VALUE - 8 =2147483639（约为21亿）

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3. 动态扩容

我们首先需要知道什么时候要进行动态扩容，当集合中元素数超过容量×加载因子即临界值threshold 时，Map类就会进行扩容。

这两个集合类的默认扩容因子均为0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;//动态扩容因子默认为0.75

3.1 HashMap

由于其方法过长，这里只截取其中一部分

final HashMap.Node[] resize()
{
    HashMap.Node[] oldTab = table;
    //获取当前map大小，如果为空大小为0，如果不为空，就为其数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //扩容临界值 当实际KV个数超过threshold时，HashMap会将容量扩容，threshold＝容量*加载因子
    int oldThr = threshold;
    //定义扩容后容量即临界值
    int newCap, newThr = 0;
    //如果扩容前容量大于0，修改临界值
    if (oldCap > 0)
    {
        //如果扩容前大小已经大于最大容量
        if (oldCap >= MAXIMUM_CAPACITY)
        {
            //将临界值设置为最大容量
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果扩容前容量的容量的二倍小于最大容量，并且大于默认容量，那么扩容后大小就为扩容前的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
        {
            //新的临界值变为扩容前的2倍
            newThr = oldThr << 1; // double threshold
        }
    }
    //如果扩容前容量小于0，并且旧的临界值大于0，将新容量为旧的临界值
    else if (oldThr > 0) // initial capacity was placed in threshold
    {
        newCap = oldThr;
    }
    //否则将新容量设置为默认值，新的临界值设置为默认值
    else
    {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
}

通过以上源码分析，我们可以知道，在扩容后容量不超过最大容量1073741824时，HashMap将扩容为以前的2倍

3.2 HashTable

protected void rehash()
{
    //获取扩容前大小
    int oldCapacity = table.length;
    Hashtable.Entry[] oldMap = table;

    // overflow-conscious code
    //新容量为旧容量的2倍+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.Entry[] newMap = new Hashtable.Entry[newCapacity];
    modCount++;
    //调整旧的临界值为新临界值和最大容量+1的较小值
    threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //采用头插法复制到新数组
    for (int i = oldCapacity; i-- > 0; )
    {
        for (Hashtable.Entry old = (Hashtable.Entry) oldMap[i]; old != null; )
        {
            Hashtable.Entry e = old;
            old = old.next;
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Hashtable.Entry) newMap[index];
            newMap[index] = e;
        }
    }
}

通过以上源码分析，我们可以知道，在扩容后容量不超过最大容量Integer.MAX_VALUE - 8时，HashTable将扩容为以前的2倍+1

4. put 4.1 HashMap

这里由于源码较为复杂，只给出结论

HashMap允许将null作为一个entry的key或者value，但是只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。

4.2 HashTable

当value为null值时，Hashtable对其做了限制，运行到下面这步也会抛出空指针异常。

if (value == null) 
{
    throw new NullPointerException();
}

当key为Null时，调用put() 方法，运行到下面这一步就会抛出空指针异常。因为拿一个Null值去调用方法了。

int hash = key.hashCode();

Hashtable不允许空值插入，一旦插入就将抛出空指针异常

5. 历史原因

Hashtable基于陈旧的Dictionary类

public class Hashtable extends Dictionaryimplements Map, Cloneable, java.io.Serializable

HashMap基于AbstractMap类（Map类）

public class HashMap extends AbstractMap implements Map, Cloneable, java.io.Serializable

6. 线程安全

这两者其实最大的不同就在于 Hashtable 是线程安全，而 HashMap 则非线程安全，Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些。

但是由于历史原因，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。那么如何保证线程安全问题的同时还能使用HashMap呢？

6. 线程安全

JDK为我们提供了线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

HashMap和Hashtable区别

Java相关栏目本月热门文章