夜深了，快睡吧-HashMap和HashTable

作者: 一个喜欢烧砖的人 | 来源:发表于2018-08-07 23:48 被阅读35次

首先，今天主要说说hashMap和hashTable的使用和不同，至于还有个ConcurrentHashMap，明晚再说吧...|

大家总是对map来说比较熟一点，那就先说map再说table把

HashMap

基本使用

public class MyTest {

    public static void main(String[] args){

        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cn", "中国");
        hashMap.put("jp", "日本");
        hashMap.put("fr", "法国");
        hashMap.put("cn", "中国2号");
        System.out.println(hashMap);
        System.out.println("****");
        System.out.println("cn:" + hashMap.get("cn"));
        System.out.println(hashMap.containsKey("cn"));

        System.out.println(hashMap.keySet());
        System.out.println(hashMap.isEmpty());

        hashMap.remove("cn");
        System.out.println(hashMap);
        //采用Iterator遍历HashMa
        Iterator it = hashMap.keySet().iterator();
        while(it.hasNext()) {
            String key = (String)it.next();
            System.out.println("key:" + key);
            System.out.println("value:" + hashMap.get(key));
        }

        //遍历HashMap的另一个方法
        Set<Map.Entry<String, String>> sets = hashMap.entrySet();
        for(Map.Entry<String, String> entry : sets) {
            System.out.print(entry.getKey() + ", ");
            System.out.println(entry.getValue());
        }
    }
}

运行结果

{jp=日本, cn=中国2号, fr=法国}
****
cn:中国2号
true
[jp, cn, fr]
false
{jp=日本, fr=法国}
key:jp
value:日本
key:fr
value:法国
jp, 日本
fr, 法国

hashMap 总结

hashMap是以键值对存储的（并不是里面有很短键值对），hashMap内部维护一个entry数组，每一个entry是由key-value组成的单向链表构成的（单向链表可解决冲突）；
hashMap是非线程安全的，如果想多线程使用，请使用util.concurrenr包下的concurrentHashMap
hashMap内部维护一个entry数组，hashMap采用链表解决冲突，每个entry是一个链表，当准备添加一个key-value时，首先通过hash(key)计算出hash值，然后通过indexFor（hash,lenght）求出key-value的储存位置，（计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头）
hashMap内部储存数据的entry数组默认是16（如果储存的k-v多的话，链表就会很长，所以肯定会有自己的扩容机制）
变量 size(hashMap底层数组中已用槽的个数)
变量 threshold(hashMap的阀值 threshold = 容量*加载因子)
变量 DEFAULT_LOAD_FACTOR = 0.75f，默认加载因子为0.75
hashMap 的扩容条件：当size > threshold时，则hashMap开始扩容
扩容是是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16），加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）
如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的
无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方

HashTable

基本使用

private static void initHashTable() {
        Hashtable<String, String> table = new Hashtable<String, String>();

        //[1]添加元素
        table.put("cn", "中国");
        table.put("jp", "日本");
        table.put("fr", "法国");
        table.put("cn", "中国2号");
        //[2]toString()方式打印
        System.out.println(table.toString());
        //都可以 
        System.out.println(table);
        //[3]Iterator遍历方式1--键值对遍历entrySet()
        Iterator<Map.Entry<String, String>> iter = table.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry<String, String> entry = (Map.Entry<String, String>)iter.next();
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println("entrySet:"+key+" "+value);
        }

        System.out.println("====================================");

        //[4]Iterator遍历方式2--key键的遍历
        Iterator<String> iterator = table.keySet().iterator();
        while(iterator.hasNext()){
            String key = (String)iterator.next();
            String value = table.get(key);
            System.out.println("keySet:"+key+" "+value);
        }

        System.out.println("====================================");

        //[5]通过Enumeration来遍历Hashtable
        Enumeration<String> enu = table.keys();
        while(enu.hasMoreElements()) {
            System.out.println("Enumeration:"+table.keys()+" "+enu.nextElement());
        }
    }

运行结构

{jp=日本, fr=法国, cn=中国2号}
{jp=日本, fr=法国, cn=中国2号}
entrySet:jp 日本
entrySet:fr 法国
entrySet:cn 中国2号
====================================
keySet:jp 日本
keySet:fr 法国
keySet:cn 中国2号
====================================
Enumeration:java.util.Hashtable$Enumerator@4554617c jp
Enumeration:java.util.Hashtable$Enumerator@74a14482 fr
Enumeration:java.util.Hashtable$Enumerator@1540e19d cn

两者的不同

1、作者不同

hashmap:

* @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter

hashtbale

 * @author  Arthur van Hoff
 * @author  Josh Bloch
 * @author  Neal Gafter

总结：map比table多了一个人，而dl也是util.concurrent包的作者

2、产生时间

hashmap产生于jdk1.2
hashTable产生于jdk1.0

3、继承的父类不同

hashTable

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

备注：Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。

NOTE: This class is obsolete. New implementations should
implement the Map interface, rather than extending this class.
hashMap

public class HashMap<K,V> 
          extends AbstractMap<K,V>
          implements Map<K,V>, Cloneable, Serializable {

4、对外接口不同

Hashtable比HashMap多提供了elments() 和contains() 两个方法。
elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。

   * @see     #keys()
     * @see     #values()
     * @see     Map
     */
    public synchronized Enumeration<V> elements() {
        return this.<V>getEnumeration(VALUES);
    }
    /**
     * Tests if some key maps into the specified value in this hashtable.
     * This operation is more expensive than the {@link #containsKey
     * containsKey} method.

contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。

   * @param value value whose presence in this hashtable is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     * @throws NullPointerException  if the value is <code>null</code>
     * @since 1.2
     */
    public boolean containsValue(Object value) {
        return contains(value);
    }
    /**
     * Tests if the specified object is a key in this hashtable.
     *
     * @param   key   possible key
     * @return  <code>true</code> if and only if the specified object

5、对null key 和 null value 的支持不同

hashTable:

//        table.put(null,"fsdfd");//会报空指针
//        table.put("cdcd",null);//也会报空指针

hashMap:

rivate static void initHashMap() {
        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cn", "中国");
        hashMap.put("jp", "日本");
        hashMap.put("fr", "法国");
        hashMap.put("cn", "中国2号");
        hashMap.put(null,"空");
        hashMap.put("nu",null);
        System.out.println(hashMap);

运行结构

{null=空, jp=日本, nu=null, cn=中国2号, fr=法国}

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

6、线程安全不同

Hashtable是线程安全的，它的每个方法中都加入了Synchronize方法(锁住了整个hashTable)。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步,
HashMap不是线程安全的，在多线程并发的环境下，可能会产生死锁等问题。具体的原因在下一篇文章中会详细进行分析。使用HashMap时就必须要自己增加同步处理
虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。这样设计是合理的。在我们的日常使用当中，大部分时间是单线程操作的。HashMap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

7、遍历实现的内部方式不同

Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式。

HashMap的Iterator是fail-fast迭代器。当有其它线程改变了HashMap的结构（增加，删除，修改元素），将会抛出ConcurrentModificationException。不过，通过Iterator的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。

JDK8之前的版本中，Hashtable是没有fast-fail机制的。在JDK8及以后的版本中，HashTable也是使用fast-fail的，源码如下：
modCount的使用类似于并发编程中的CAS（Compare and Swap）技术。我们可以看到这个方法中，每次在发生增删改的时候都会出现modCount++的动作。而modcount可以理解为是当前hashtable的状态。每发生一次操作，状态就向前走一步。设置这个状态，主要是由于hashtable等容器类在迭代时，判断数据是否过时时使用的。尽管hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候，则无法保证边迭代，边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变，则会快速抛出一个异常，终止迭代行为。

8、初始容量大小和每次扩充容量大小的不同

Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。

创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。

之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同

hashMap为什么是2的n次幂？
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；
这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方；
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；
jdk1.8对hashMap做的优化
这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
当插入新元素时，对于红黑树的判断如下：
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向下面；
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

9、计算hash值的方法不同

为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。

Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。

Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。
HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。

HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高，而计算位运算

为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2 的幂次方带来的效率提升给抵消掉。