JAVA中HashMap和Hashtable区别

绝地灬酷狼 2022-05-14 15:11 235阅读 0赞

Hashtable和HashMap在Java面试中相当容易被问到，甚至成为了集合框架面试题中最常被考的问题，所以在参加任何Java面试之前，都不要忘了准备这一题。

**我们先看2个类的定义**

public class Hashtable  
        extends Dictionary  
        implements Map, Cloneable, <a href="http://lib.csdn.net/base/javase" class='replace_word' title="Java SE知识库" target='_blank' style='color:#df3434; font-weight:bold;'>Java</a>.io.Serializable

public class HashMap  
        extends AbstractMap  
        implements Map, Cloneable, Serializable

可见Hashtable 继承自 Dictiionary 而 HashMap继承自AbstractMap

**Hashtable的put方法如下**

![复制代码][copycode.gif]

public synchronized V put(K key, V value) {  //###### 注意这里1  
      // Make sure the value is not null  
      if (value == null) { //###### 注意这里 2  
        throw new NullPointerException();  
      }  
      // Makes sure the key is not already in the hashtable.  
      Entry tab[] = table;  
      int hash = key.hashCode(); //###### 注意这里 3  
      int index = (hash & 0x7FFFFFFF) % tab.length;  
      for (Entry 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;  
        }  
      }  
      modCount++;  
      if (count >= threshold) {  
        // Rehash the table if the threshold is exceeded  
        rehash();  
        tab = table;  
        index = (hash & 0x7FFFFFFF) % tab.length;  
      }  
      // Creates the new entry.  
      Entry e = tab[index];  
      tab[index] = new Entry(hash, key, value, e);  
      count++;  
      return null;  
    }

![复制代码][copycode.gif]

注意1 方法是同步的  
注意2 方法不允许value==null  
注意3 方法调用了key的hashCode方法，如果key==null,会抛出空指针异常

HashMap的put方法如下

![复制代码][copycode.gif]

public V put(K key, V value) { //###### 注意这里 1  
      if (key == null)  //###### 注意这里 2  
        return putForNullKey(value);  
      int hash = hash(key.hashCode());  
      int i = indexFor(hash, table.length);  
      for (Entry e = table[i]; e != null; e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
          V oldValue = e.value;  
          e.value = value;  
          e.recordAccess(this);  
          return oldValue;  
        }  
      }  
      modCount++;  
      addEntry(hash, key, value, i);  //###### 注意这里   
      return null;  
    }

![复制代码][copycode.gif]

注意1 方法是非同步的  
注意2 方法允许key==null  
注意3 方法并没有对value进行任何调用，所以允许为null

## 是否提供contains方法 ##

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。

Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

我们看一下Hashtable的ContainsKey方法和ContainsValue的源码：

public boolean containsValue(Object value) {      
         return contains(value);      
     }

![复制代码][copycode.gif]

// 判断Hashtable是否包含“值(value)”      
     public synchronized boolean contains(Object value) {      
         //注意，Hashtable中的value不能是null，      
         // 若是null的话，抛出异常!      
         if (value == null) {      
             throw new NullPointerException();      
         }      
        
         // 从后向前遍历table数组中的元素(Entry)      
         // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value      
         Entry tab[] = table;      
         for (int i = tab.length ; i-- > 0 ;) {      
             for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {      
                 if (e.value.equals(value)) {      
                     return true;      
                 }      
             }      
         }      
         return false;      
     }

![复制代码][copycode.gif]

// 判断Hashtable是否包含key      
     public synchronized boolean containsKey(Object key) {      
         Entry tab[] = table;      
    /计算hash值，直接用key的hashCode代替    
         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 true;      
             }      
         }      
         return false;      
     }

![复制代码][copycode.gif]

下面我们看一下HashMap的ContainsKey方法和ContainsValue的源码：

// HashMap是否包含key      
        public boolean containsKey(Object key) {      
            return getEntry(key) != null;      
        }

![复制代码][copycode.gif]

// 返回“键为key”的键值对      
        final Entry<K,V> getEntry(Object key) {      
            // 获取哈希值      
            // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值      
            int hash = (key == null) ? 0 : hash(key.hashCode());      
            // 在“该hash值对应的链表”上查找“键值等于key”的元素      
            for (Entry<K,V> e = table[indexFor(hash, table.length)];      
                 e != null;      
                 e = e.next) {      
                Object k;      
                if (e.hash == hash &&      
                    ((k = e.key) == key || (key != null && key.equals(k))))      
                    return e;      
            }      
            return null;      
        }

![复制代码][copycode.gif]

// 是否包含“值为value”的元素      
        public boolean containsValue(Object value) {      
        // 若“value为null”，则调用containsNullValue()查找      
        if (value == null)      
                return containsNullValue();      
         
        // 若“value不为null”，则查找HashMap中是否有值为value的节点。      
        Entry[] tab = table;      
            for (int i = 0; i < tab.length ; i++)      
                for (Entry e = tab[i] ; e != null ; e = e.next)      
                    if (value.equals(e.value))      
                        return true;      
        return false;      
        }

![复制代码][copycode.gif]

通过上面源码的比较，我们可以得到如下不同地方：key和value是否允许null值。

其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。通过上面的ContainsKey方法和ContainsValue的源码我们可以很明显的看出：

Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。

HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。

### HashMap和Hashtable的区别 ###

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口。主要的区别有：线程安全性，同步(synchronization)，以及速度。

1.Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。

2.HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。

3.HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。（在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步(Collections.synchronizedMap)）

4.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。fail-fast机制如果不理解原理，可以查看这篇文章：http://www.cnblogs.com/alexlo/archive/2013/03/14/2959233.html

5.由于HashMap非线程安全，在只有一个线程访问的情况下，效率要高于HashTable。

6.HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。

7.Hashtable中hash数组默认大小是11，增加的方式是 old\*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

8..两者通过hash值散列到hash表的算法不一样：

，HashTbale是古老的除留余数法，直接使用hashcode

int hash = key.hashCode();  
    int index = (hash & 0x7FFFFFFF) % tab.length;

而后者是强制容量为2的幂，重新根据hashcode计算hash值，在使用hash 位与 （hash表长度 – 1），也等价取膜，但更加高效，取得的位置更加分散，偶数，奇数保证了都会分散到。前者就不能保证

![复制代码][copycode.gif]

int hash = hash(k);  
    int i = indexFor(hash, table.length);  
      
    static int hash(Object x) {  
    　　int h = x.hashCode();  
      
    　　h += ~(h << 9);  
    　　h ^= (h >>> 14);  
    　　h += (h << 4);  
    　　h ^= (h >>> 10);  
    　　return h;  
    }  
      
    static int indexFor(int h， int length) {  
    　　return h & (length-1);

![复制代码][copycode.gif]

要注意的一些术语：

1.sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁，其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。

2.Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。

3.结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。

代码演示部分如下：

先看个Hashtable正常输出的示例：

Hashtable table = new Hashtable();  
    table.put("a-key", "a-value");  
    table.put("b-key", "b-value");  
    table.put("c-key", "c-value");

输出如下：

a-key - a-value  
    c-key - c-value  
    b-key - b-value

再看个Hashtable拒绝null的示例：

table.put(null, "a-value");

运行之后异常如下：

Exception in thread "main" java.lang.NullPointerException  
    at java.util.Hashtable.put(Hashtable.java:399)  
    at com.darkmi.sandbox.HashtableTest.main(HashtableTest.java:20)

HashMap示例：

HashMap map = new HashMap();  
    map.put(null, "a-value");  
    map.put("b-key", null);  
    map.put("c-key", null);

b-key - null  
    null - a-value  
    c-key - null

PS:从上面的示例我们倒是可以发现Hashtable与HashMap相同的一点：无序存放。

3.两者的遍历方式大同小异，Hashtable仅仅比HashMap多一个elements方法。

Enumeration em = table.elements();  
    while (em.hasMoreElements()) {  
    String obj = (String) em.nextElement();  
    System.out.println(obj);   
    }

HashMap和HashTable都能通过values()方法返回一个 Collection ，然后进行遍历处理：

Collection coll = map.values();  
    Iterator it = coll.iterator();  
    while (it.hasNext()) {  
    String obj = (String) it.next();  
    System.out.println(obj);  
    }

两者也都可以通过 entrySet() 方法返回一个 Set ， 然后进行遍历处理：

![复制代码][copycode.gif]

Set set = table.entrySet();  
    Iterator it = set.iterator();  
    while (it.hasNext()) {  
    Entry entry = (Entry) it.next();  
    System.out.println(entry.getKey() + " - " + entry.getValue());  
      
    }

![复制代码][copycode.gif]

[copycode.gif]: /images/20220504/ed1b0ad609d04d43bb6ee7fef85d2372.png