hashmaphashtable基础篇
一、前言 上个月花了点时间研究了一下HashMap的源码，对HashMap的实现原理有了一个较为深入的了解，今天突然想到有一个常考的面试题——HashMap与Hashtable的区别，于是又花了点时间研究了一下Hashtable的源码。今天这篇博客就来简单介绍一下两者的区别，以下内容将主要从Hashtable的角度，描述它和HashMap有什么不同，而且将分两个方面来叙述——使用方面和实现细节方面。如果对HashMap不是很了解的，可以阅读一下这篇博客：HashMap源码解读——深入理解HashMap高效的原因。
二、正文 2.1 使用上的不同 （1）Hashtable线程安全，HashMap线程不安全
这是这两个容器最根本的区别。HashMap是一个线程不安全的容器，它并没有实现线程同步，所以不应该在多线程的环境下使用。而Hashtable实现了线程同步，是一个线程安全的容器，但是它实现同步的方式比较拙劣——直接在大部分的public方法上添加synchronized关键字进行同步，这样对于同一个Hashtable对象，每次只能有一个线程调用它的实例方法。这种拙劣的同步方式使得Hashtable的效率要远远低于HashMap，而且在很多情况下，这种同步是没有意义的，比如在没有写操作发生的情况下，完全可以多个线程同时对Hashtable进行读操作，并不会造成危害。
（2）Hashtable不允许key或value为null，HashMap可以
在Hashtable的很多方法中（比如put方法），特判了value为null的情况，此时将直接抛出一个NullPointerException；而对于key为null的情况却没有特判，但是若在其中加入一个key为null的元素，依旧会抛出NullPointerException，因为Hashtable中获取key的hash值是直接调用key.hashCode方法，所有key不能为null。我们看Hashtable中的put方法即可知晓（多余的代码被删除）：
代码语言：javascript复制public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// ......
int hash = key.hashCode();
// ......
}但是HashMap中，无论是key还是value，都可以为null，因为它对null做了特殊处理。HashMap实现中，判断key为null，则不会调用key.hashCode获取它的hash值，而是将0作为它的hash值；而在get方法获取value时，如果找到的节点为null，则直接返回null，否则返回node.value。同样看HashMap中的两段代码来验证这一点：
// 此方法为HashMap中获取key的hash值的方法，特判了key == null的情况
代码语言：javascript复制 static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// HashMap中的get方法，特判了value为null的情况
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}2.2 实现细节上的不同 （1）Hashtable使用头插法，JDK1.8之后的HashMap使用尾插法
先简单说一说什么是头插和尾插：
头插法：在链表中插入一个新的节点时，将新节点作为链表的头节点，然后将新节点的next指向旧头节点； 尾插法：在链表中插入一个新的节点时，让链表的尾节点的next指向新节点； Hashtable使用的是头插法，而HashMap在JDK1.8之前，使用的也是头插法。但是，有人发现在并发情况下，若没有进行线程同步，头插法有很小的概率会导致死循环（这个问题我就不展开描述了，可以自己去查一查），于是从JDK1.8开始，为HashMap添加节点改为了尾插法。
（2）HashMap的容量必须是2^n，而Hashtable的容量没有这个限制
这是两者之间非常大的一个区别，就这一点，让HashMap和Hashtble在实现上有很大的不同。HashMap的容量一定是2^n，其原因我在前言中推荐的博客里面做了详细的描述，这里就简单说一下。容量定为2^n是为了对取余运算做优化，因为2^n满足一个性质：
代码语言：javascript复制num % 2^n == num & (2^n - 1)不论是HashMap还是Hashtable，要获取节点在数组中的下标，都需要用key的hash值对数组长度取余，而HashMap将数组长度限制为2^n，就是为了用上面公式中的&替代%进行取余操作，因为&的效率要比%更高，而获取下标又是一个频繁的操作，所以这一步优化让HashMap的查找速度有了很大的提升。而在Hashtable中，就是直接用%取余。我们看两者取余的源码：
// HashMap中的取余：tab为存放节点的数组，n为数组长度，hash变量存的是key的哈希值 // 这一步就是获取哈希值为hash的key在tab中的位置 // HashMap中的hash值不会是负数，因为HashMap中自己实现了hash方法求hash值 tab[(n - 1) & hash]
// Hashtable中的取余：hash & 0x7FFFFFFF其实就是取hash的绝对值，然后直接对tab.length取余 // 0x7FFFFFFF转换成二进制就是第一位为0，后31位为1，这个操作也就是将符号位转为0（第一位为符号位）， // 而二进制中，符号位为0表示表示正数，这一步是防止计算出负数的下标，因为hash值可能为负 // 不用Math.abs是因为Math.abs(Integer.MAX_VALUE)越界，结果还是负数 int index = (hash & 0x7FFFFFFF) % tab.length; 而正是这个优化，导致了HashMap和Hashtable的许多其他区别：
HashMap的默认初始容量为16，也就是2^4，如果指定了一个容量，则HashMap不会直接用它，而是先找出第一个大于这个指定容量的2^n；而Hashtable的默认初始容量是11，11是一个质数，根据hash求下标时，质数能够让下标分配更加均匀，Hashtable会直接接收指定的初始容量； HashMap扩容时直接将数组大小乘2，因为（2^n）×2 == 2^(n 1)，仍然满足2^n；而Hashtable扩容是乘2加1，因为这样可以让一个质数很大概率还是一个质数； （3）JDK1.8开始，HashMap结构变为数组 链表 红黑树
在JDK1.7以前，HashMap和Hashtable的结构都是数组 链表的实现，但是从JDK1.8开始，HashMap变成了数组 链表 红黑树。这是因为，在hash取余的结果不均匀的情况下，节点可能集中在数组中的某几条链表上，导致链表过长。比如举一个极端的例子，所有的节点通过hash值计算出的下标都相等，此时所有的节点都在一条链表上，这个时候HashMap或者Hashtable就退化成了一个链表，查询的时间复杂度退化为了O（n）。为了避免这种情况的发生，从JDK1.8开始，HashMap中若某条链表的节点数达到了8个，就会将这条链表转换为红黑树，此时，对这条链表的查询效率就从O（n）提升为O（logn）。而Hashtable作为一个已经过时的容器，自然不会花时间对它进行复杂的优化。
三、总结 Hashtable是一个过时的容器，在开发当中，我们应该少去使用它，甚至根本不要使用它。在单线程的环境下，我们最好使用HashMap，而在多线程的环境下，应该使用ConcurrentHashMap，它的效率要远远高于Hashtable。上面最后提到的几点都和HashMap的实现有关，建议阅读我在前言中推荐的博客，了解HashMap的具体实现。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处 最后编辑时间为: 2021/09/17 10:45
