Hashtable源码分析

Hashtable是一个比较古老的Map实现类,从它的名称就可以看得出来,因为没有遵循Java语言的驼峰命名规范,这可能是开发者的疏忽导致的吧。它和HashMap很像,同属于散列表,都可以存储K-V键值对,并且都可以实现O(1)的查找时间复杂度。有以下特性:

1、首先就是线程安全,这也估计算是唯一一个优于HashMap的特性了吧;
2、Hashtable不允许key或者value为null;
3、自从JDK1.2开始,Hashtable实现了Map接口,成为了Map容器中的一员。看样子最开始是不属于Map容器的。
4、不建议使用,以后说不定哪天就废掉了。连官方文档也说了,如果在非线程安全的情况下使用,建议使用HashMap替换,如果在线程安全的情况下使用,建议使用ConcurrentHashMap替换。

虽然不建议使用,但是面试的时候当问到HashMap时经常性的会和Hashtable比较,因此我们还是有必要大概研究一下Hashtable源码的,毕竟也不是很难,当读过HashMap源码再来读Hashtable源码就会发现他就是个“di di”!

一、重要的属性方法

/**                                                              
 * The hash table data.     
 * Hashtable存储数据的地方           
 */  
private transient Entry<?,?>[] table;                            
                                                                 
/**                                                              
 * The total number of entries in the hash table. 
 * Hashtable中实际存储的元素的个数
 */                                                              
private transient int count;                                     
                                                                 
/**                                                              
 * The table is rehashed when its size exceeds this threshold.  (The
 * value of this field is (int)(capacity * loadFactor).)         
 * 扩容阈值=capacity*loadFactory                                                       
 */                                                              
private int threshold;                                           
                                                                 
/**                                                              
 * The load factor for the hashtable.                            
 * 加载因子,默认架子啊因子和HashMap一样,都是0.75 
 */                                                              
private float loadFactor;     

//哈希数组的最大容量Integer.MAX_VALUE - 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Hashtable是继承自古老的Dictionary类,而Dictionary类,顾名思义,就是字典类,算是早期的Map,不过该类基本上已经废弃了。为什么废弃呢,大致看下Dictionary的源码就知道了。除了常规的get,put请求外,还提供了一些遍历的方法,返回的是Enumeration类型。而Enumeration接口其实算是被Iterator替换了,因为Iterator提供的功能更多,更方便。所以,就目前而言,Dictionary存在的意义恐怕就只是为了兼容原来继承它的一些类了吧。

二、构造方法

 /**                                                                       
  * Constructs a new, empty hashtable with a default initial capacity (11) 
  * and load factor (0.75).    
  * Hashtable默认初始容量11,默认加载因子0.75
  */                                                                       
 public Hashtable() {                                                      
     this(11, 0.75f);                                                      
 }

//指定初始容量
public Hashtable(int initialCapacity) {  
    this(initialCapacity, 0.75f);        
}                                        

/**
* 最终“干活”的构造方法,这里和HashMap有不同,Hashtable直接在构造方法中就初始化好了Hash数组,而HashMap是在第一次put的时候才初始化,相对来说HashMap的策略更好些
*/
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); 
}    

三、关键源码分析

0、数组结点类型—Entry内部类

Hashtable的结点类型Entry的结构和HashMap的Node的结构类似,每一个节点都会保存自身的hash、key、value、以及下个节点。如下图所示:

1、put方法

put流程很简单,这里大致梳理一下:

  • 1、首先检查key不能为null,如果是null就会抛出NullPointerException异常;
  • 2、如果key!=null,计算出key在哈希表中的桶位index,,然后遍历这个桶位的链表检查是否是值替换,如果是就替换并返回新值;
  • 3、如果不是值替换,那就添加新结点,此时会代用addEntry方法,下面是addEntry源码
  • 3.1、通过tab[index] = new Entry<>(hash, key, value, e);这一行代码,并且根据Entry的构造方法,我们可以知道,Hashtable是在链表的头部添加元素的,而HashMap是尾部添加的,这点可以注意下。

  • 3.2、Hashtable计算数组index的方式和HashMap有点不同,int index = (hash & 0x7FFFFFFF) % tab.length;0x7FFFFFFF也就是Integer.MAX_VALUE,也就是2的32次方-1,二进制的话也就是11111111…,那么(hash&0x7FFFFFFF)的含义看来看去好像只有对符号位有效了,就是负数的时候,应该是为了过滤负数,而后面的取模就很简单了,把index的取值限制在数组的长度之内

2、rehash()方法

rehash流程梳理:

1、首先计算出新容量newCapcity和新的阈值,并且实例化一个newCapcity大小的新Entry数组。newCapcity=(oldCapacity<<1)+1。容量的最大值是Integer.MAX_VALUE-8

2、之后从旧哈希表的尾部开始遍历每个哈希槽位,如果槽位中没有元素直接跳过,有元素则重新hash之后移动到新哈希表中。(元素在新哈希表的index=(e.hash&0x7FFFFFFF)%newCapacity。重新hash的原因是扩容之后哈希表的长度发生变化了,对哈希表取模的值会发生变化)

3、get()方法

get流程梳理:

1、通过(key.hashCode()& 0x7FFFFFFF) % tab.length 获取 当前 keytable 的索引。

2、然后遍历当前链表找到对应的节点,如果没找到返回null。

总结

最后一幅脑图总结Hashtable的重要知识点:

四、HashMap和Hashtable对比

(1)HashMap的父类是AbstractMap,而Hashtable的父类是Dictionary。AbstractMap实现了Map接口,它以最大限度地减少实现此接口所需的工作;而Dictionary 是任何可将键映射到相应值的类的抽象父类;

(2)HashMap的默认初始容量是16,最大容量是2^30,并且HashMap的哈希数组是懒加载的,即调用构造方方法之后不会立即实例化而是在第一次put的时候初始化哈希数组;Hashtable的默认初始容量是11,最大容量是Integer.MAX_VALUE-8,并且Hashtable的哈希数组在调用构造方法后立即实例化的

(3)HashMap的扩容是旧数组大小的2倍,Hashtable的扩容是就数组的大小的2倍+1

(4)HashMap 的 key 和 value 都允许为 null,而 Hashtable的 key和 value 都不允许为 null。HashMap遇到key为null的元素会直接把它放到哈希数组的0号槽位,但是Hashtable遇到key或value为null的元素会抛出NullPointerException异常;

(5)HashMap不是线程安全的,但是Hashtable是线程安全的;即使是在jdk1.8的HashMap中即使解决了多线程下扩容导致的死循环问题,但是在多线程环境下还是会存在数据的共享读写问题;Hashtable几乎所有的public方法都使用synchronize修饰,可以保证数据的安全性问题,但是效率不高,因此想使用线程安全的Map还是推荐使用ConcurrentHashMap;

参考资料

留言区

还能输入500个字符