hashtable和hashmap的区别详解(转) -凯发真人娱乐

一、hashmap简介

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

hashmap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrenthashmap。

hashmap 实现了serializable接口，因此它支持序列化，实现了cloneable接口，能被克隆。

hashmap存数据的过程是：

hashmap内部维护了一个存储数据的entry数组，hashmap采用链表解决冲突，每一个entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexfor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7fffffff后，再对length取模，这就保证每一个key-value对都能存入hashmap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。

hashmap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。

了解了数据的存储，那么数据的读取也就很容易就明白了。

hashmap的存储结构，如下图所示：

　　　　　　　　　　 

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

hashmap内存储数据的entry数组默认是16，如果没有对entry扩容机制的话，当存储的数据一多，entry内部的链表会很长，这就失去了hashmap的存储意义了。所以hasnmap内部有自己的扩容机制。hashmap内部有：

变量size，它记录hashmap的底层数组中已用槽的数量；

变量threshold，它是hashmap的阈值，用于判断是否需要调整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次方

对hashmap想进一步深入了解的朋友推荐看一下hashmap源码剖析：http://blog.csdn.net/ns_code/article/details/36034955

二、hashtable简介

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

hashtable也是jdk1.0引入的类，是线程安全的，能用于多线程环境中。

hashtable同样实现了serializable接口，它支持序列化，实现了cloneable接口，能被克隆。

hashtable和hashmap比较相似，感兴趣的朋友可以看“hashtable源码剖析”这篇博客：http://blog.csdn.net/ns_code/article/details/36191279

三、hashtable和hashmap区别

1、继承的父类不同

　　hashtable继承自dictionary类，而hashmap继承自abstractmap类。但二者都实现了map接口。

2、线程安全性不同

javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
      hashtable 中的方法是synchronize的，而hashmap中的方法在缺省情况下是非synchronize的。在多线程并发的环境下，可以直接使用hashtable，不需要自己为它的方法实现同步，但使用hashmap时就必须要自己增加同步处理。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 collections.synchronizedmap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

map m = collections.synchronizedmap(new hashmap(...));

hashtable 线程安全很好理解，因为它每个方法中都加入了synchronize。这里我们分析一下hashmap为什么是线程不安全的：

hashmap底层是一个entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。

我们来分析一下多线程访问：

（1）在hashmap做put操作的时候会调用下面方法：

// 新增entry。将“key-value”插入指定位置，bucketindex是位置索引。

void addentry(int hash, k key, v value, int bucketindex) {

    // 保存“bucketindex”位置的值到“e”中

    entry e = table[bucketindex];

    // 设置“bucketindex”位置的元素为“新entry”，

    // 设置“e”为“新entry的下一个节点”

    table[bucketindex] = new entry(hash, key, value, e);

    // 若hashmap的实际大小 不小于 “阈值”，则调整hashmap的大小

    if (size   >= threshold)

        resize(2 * table.length);

}  

　　在hashmap做put操作的时候会调用到以上的方法。现在假如a线程和b线程同时对同一个数组位置调用addentry，两个线程会同时得到现在的头结点，然后a写入新的头结点之后，b也写入新的头结点，那b的写入操作就会覆盖a的写入操作造成a的写入操作丢失

　　(2)  删除键值对的代码

final entry removeentryforkey(object key) {

    // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算

    int hash = (key == null) ? 0 : hash(key.hashcode());

    int i = indexfor(hash, table.length);

    entry prev = table[i];

    entry e = prev;    
    // 删除链表中“键为key”的元素

    // 本质是“删除单向链表中的节点”

    while (e != null) {

        entry next = e.next;

        object k;

        if (e.hash == hash &&

            ((k = e.key) == key || (key != null && key.equals(k)))) {

            modcount  ;

            size--;

            if (prev == e)

                table[i] = next;

            else

                prev.next = next;

            e.recordremoval(this);

            return e;

        }

        prev = e;

        e = next;

    }    
    return e;

}

　　当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改

(3)  addentry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作，代码如下：

// 重新调整hashmap的大小，newcapacity是调整后的容量

void resize(int newcapacity) {

    entry[] oldtable = table;

    int oldcapacity = oldtable.length;

    //如果就容量已经达到了最大值，则不能再扩容，直接返回

    if (oldcapacity == maximum_capacity) {

        threshold = integer.max_value;

        return;

    }    
    // 新建一个hashmap，将“旧hashmap”的全部元素添加到“新hashmap”中，

    // 然后，将“新hashmap”赋值给“旧hashmap”。

    entry[] newtable = new entry[newcapacity];

    transfer(newtable);

    table = newtable;

    threshold = (int)(newcapacity * loadfactor);

}

　　这个操作会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。

当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

3、是否提供contains方法

hashmap把hashtable的contains方法去掉了，改成containsvalue和containskey，因为contains方法容易让人引起误解。

hashtable则保留了contains，containsvalue和containskey三个方法，其中contains和containsvalue功能相同。

public boolean containsvalue(object value) {

     return contains(value);

}
// 判断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 e = tab[i] ; e != null ; e = e.next) {    

             if (e.value.equals(value)) {    

                 return true;    

             }    

         }    

     }    

     return false;    

}
// 判断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 e = tab[index] ; e != null ; e = e.next) {    

         if ((e.hash == hash) && e.key.equals(key)) {    

             return true;    

         }    

     }    

     return false;    

}

　　下面我们看一下hashmap的containskey方法和containsvalue的源码：

// hashmap是否包含key

public boolean containskey(object key) {

    return getentry(key) != null;

}
// 返回“键为key”的键值对    

final entry getentry(object key) {    

    // 获取哈希值    

    // hashmap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值    

    int hash = (key == null) ? 0 : hash(key.hashcode());    

    // 在“该hash值对应的链表”上查找“键值等于key”的元素    

    for (entry 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;    

}
// 是否包含“值为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;    

}

　　通过上面源码的比较，我们可以得到第四个不同的地方。

4、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()方法来判断。

5、两个遍历方式的内部实现上不同

hashtable、hashmap都使用了 iterator。而由于历史原因，hashtable还使用了enumeration的方式 。

6、hash值不同

哈希值的使用不同，hashtable直接使用对象的hashcode。而hashmap重新计算hash值。

hashcode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

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

7、内部实现使用的数组初始化和扩容方式不同

hashtable在不指定容量的情况下的默认容量为11，而hashmap为16，hashtable不要求底层数组的容量一定要为2的整数次幂，而hashmap则要求一定为2的整数次幂。
      hashtable扩容时，将容量变为原来的2倍加1，而hashmap扩容时，将容量变为原来的2倍。
      hashtable和hashmap它们两个内部实现方式的数组的初始大小和扩容的方式。hashtable中hash数组默认大小是11，增加的方式是 old*2 1。

hashtable和hashmap的区别详解(转)的相关教程结束。