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<K, V>[] table; Node(int hash, K key, V value, HashMap.Node<K, V> 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<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
2. 初始化大小
2.1 HashMap
对于HashMap来说，其源码中直接定义了DEFAULT_INITIAL_CAPACITY，初始化大小为1<<4 即 24=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<K, V>[] resize()
{
HashMap.Node<K, V>[] 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<K, V> old = (Hashtable.Entry<K, V>) oldMap[i]; old != null; )
{
Hashtable.Entry<K, V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Hashtable.Entry<K, V>) 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<K,V> extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable
-
HashMap基于AbstractMap类（Map类）
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, java.io.Serializable
6. 线程安全
这两者其实最大的不同就在于 Hashtable 是线程安全，而 HashMap 则非线程安全，Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些。
但是由于历史原因，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。那么如何保证线程安全问题的同时还能使用HashMap呢？
6. 线程安全
这两者其实最大的不同就在于 Hashtable 是线程安全，而 HashMap 则非线程安全，Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些。
但是由于历史原因，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。那么如何保证线程安全问题的同时还能使用HashMap呢？
JDK为我们提供了线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。