查看原文
其他

Java集合Hashtable源码剖析

2017-03-30 IT哈哈

1、Hashtable简介

(1)Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

(2)Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中。

(3)Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆。


Hashtable 和HashMap 存储结构和解决冲突的方法都是相同的。()


Hashtable继承关系:


public class Hashtable<K,V>      
    extends Dictionary<K,V>      
    implements Map<K,V>, Cloneable, java.io.Serializable   


2、Hashtable 成员变量


// 保存key-value的数组。      
// Hashtable同样采用单链表解决冲突,每一个Entry本质上是一个单向链表      
private transient Entry[] table;      
// Hashtable中键值对的数量      
private transient int count;      
// 阈值,用于判断是否需要调整Hashtable的容量(threshold = 容量*加载因子)      
private int threshold;      
// 加载因子      
private float loadFactor;       
// Hashtable被改变的次数,用于fail-fast机制的实现      
private transient int modCount = 0;       

 // Hashtable的Entry节点,它本质上是一个单向链表。      
   // 也因此,我们才能推断出Hashtable是由拉链法实现的散列表      
   private static class Entry<K,V> implements Map.Entry<K,V> {      
       // 哈希值      
       int hash;      
       K key;      
       V value;      
       // 指向的下一个Entry,即链表的下一个节点      
       Entry<K,V> next;      
       // 构造函数      
       protected Entry(int hash, K key, V value, Entry<K,V> next) {      
           this.hash = hash;      
           this.key = key;      
           this.value = value;      
           this.next = next;      
       }     
....  
}  


3、Hashtable构造函数


// 指定“容量大小”和“加载因子”的构造函数      
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)(initialCapacity * loadFactor);      
}      
// 指定“容量大小”的构造函数      
public Hashtable(int initialCapacity) {      
    this(initialCapacity, 0.75f);      
}      
// 默认构造函数。      
public Hashtable() {      
    // 默认构造函数,指定的容量大小是11;加载因子是0.75      
    this(11, 0.75f);      
}      
// 包含“子Map”的构造函数      
public Hashtable(Map<? extends K, ? extends V> t) {      
    this(Math.max(2*t.size(), 11), 0.75f);      
    // 将“子Map”的全部元素都添加到Hashtable中      
    putAll(t);      
}  


4、Hashtable常用方法


4.1 put方法


// 调整Hashtable的长度,将长度变成原来的2倍+1     
  protected void rehash() {      
      int oldCapacity = table.length;      
      Entry[] oldMap = table;      
   
      //创建新容量大小的Entry数组    
      int newCapacity = oldCapacity * 2 + 1;      
      Entry[] newMap = new Entry[newCapacity];      
   
      modCount++;      
      threshold = (int)(newCapacity * loadFactor);      
      table = newMap;      
          
      //将“旧的Hashtable”中的元素复制到“新的Hashtable”中    
      for (int i = oldCapacity ; i-- > 0 ;) {      
          for (Entry<K,V> old = oldMap[i] ; old != null ; ) {      
              Entry<K,V> e = old;      
              old = old.next;      
              //重新计算index    
              int index = (e.hash & 0x7FFFFFFF) % newCapacity;      
              e.next = newMap[index];      
              newMap[index] = e;      
          }      
      }      
  }      
   
  // 将“key-value”添加到Hashtable中      
  public synchronized V put(K key, V value) {      
      // Hashtable中不能插入value为null的元素!!!  
      if (value == null) {      
          throw new NullPointerException();      
      }      
   
      // 若“Hashtable中已存在键为key的键值对”,      
      // 则用“新的value”替换“旧的value”      
      Entry tab[] = table;      
      int hash = key.hashCode();      
      int index = (hash & 0x7FFFFFFF) % tab.length;      
      for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {      
          if ((e.hash == hash) && e.key.equals(key)) {      
              V old = e.value;      
              e.value = value;      
              return old;      
              }      
      }      
   
      // 若“Hashtable中不存在键为key的键值对”,    
      // 将“修改统计数”+1      
      modCount++;      
      //  若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)      
      //  则调整Hashtable的大小      
      if (count >= threshold) {    
          rehash();      
   
          tab = table;      
          index = (hash & 0x7FFFFFFF) % tab.length;      
      }      
   
      //将新的key-value对插入到tab[index]处(即链表的头结点)    
      Entry<K,V> e = tab[index];             
      tab[index] = new Entry<K,V>(hash, key, value, e);      
      count++;      
      return null;      
  }    


4.2 get 方法


// 返回key对应的value,没有的话返回null      
 public synchronized V get(Object key) {      
     Entry tab[] = table;      
     int hash = key.hashCode();      
     // 计算索引值,      
     int index = (hash & 0x7FFFFFFF) % tab.length;      
     // 找到“key对应的Entry(链表)”,然后在链表中找出“哈希值”和“键值”与key都相等的元素      
     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {      
         if ((e.hash == hash) && e.key.equals(key)) {      
             return e.value;      
         }      
     }      
     return null;      
 }     


4.3 remove 方法


// 删除Hashtable中键为key的元素      
public synchronized V remove(Object key) {      
    Entry tab[] = table;      
    int hash = key.hashCode();      
    int index = (hash & 0x7FFFFFFF) % tab.length;      
        
    //从table[index]链表中找出要删除的节点,并删除该节点。    
    //因为是单链表,因此要保留带删节点的前一个节点,才能有效地删除节点    
    for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {      
        if ((e.hash == hash) && e.key.equals(key)) {      
            modCount++;      
            if (prev != null) {      
                prev.next = e.next;      
            } else {      
                tab[index] = e.next;      
            }      
            count--;      
            V oldValue = e.value;      
            e.value = null;      
            return oldValue;      
        }      
    }      
    return null;      
}   


5、Hashtable的Iterator



6、总结


Hashtable和HashMap不同之处

1、继承不同。我们从他们的定义就可以看出他们的不同,HashTable基于Dictionary类,而HashMap是基于AbstractMap。


2、默认容量及扩容方式不同。HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。


3、Hashtable中key和value都不允许为null,而HashMap中key和value都允许为null(key只能有一个为null,而value则可以有多个为null)。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。如下:当HashMap遇到为null的key时,它会调用putForNullKey方法来进行处理。对于value没有进行任何处理,只要是对象都可以。


4、hash值的计算方式不同。Hashtable计算hash值,直接用key的hashCode(),而HashMap重新计算了key的hash值,Hashtable在求hash值对应的位置索引时,用取模运算,而HashMap在求位置索引时,则用与运算,且这里一般先用hash&0x7FFFFFFF后,再对length取模,&0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号外改变,而后面的位都不变。


5、线程安全性不同。Hashtable的很多方法是同步的,线程安全的。HashMap未经同步,非线程安全。


6、两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式 。


相同之处:

Hashtable和HashMap对象可以让你把一个key和一个value结合起来,并用put() 方法把这对key/value输入到表中。然后你可以通过调用get()方法,把key作为参数来得到这个value(值)。二者的存储结构和解决冲突的方法都是相同的。



您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存