精华内容
下载资源
问答
  • HashMap和Hashtable的区别

    万次阅读 多人点赞 2019-06-12 22:23:34
    HashMap和Hashtable的区别 一、HashMap简介 HashMap是在JDK1.2中引入的Map的实现类。 1.HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会...

    HashMap和Hashtable的区别
    一、HashMap简介
    HashMap是在JDK1.2中引入的Map的实现类。
    1.HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

     2. HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap。
    
      3.HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。
    
      4.HashMap存数据的过程是:
    
      HashMap内部维护了一个存储数据的Entry数组,HashMap采用链表解决冲突,每一个Entry本质上是一个单向链表。当准备添加一个key-value对时,首先通过hash(key)方法计算hash值,然后通过indexFor(hash,length)求该key-value对的存储位置,计算方法是先用hash&0x7FFFFFFF后,再对length取模,这就保证每一个key-value对都能存入HashMap中,当计算出的位置相同时,由于存入位置是一个链表,则把这个key-value对插入链表头。
    
      5.HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。
    

    在这里插入图片描述
    图中,紫色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的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次方。
    

    二、Hashtable简介

      Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。
    
      Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中。
    
      Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆。
    

    三.分析二者不同

    1、继承的父类不同

    HashMap继承自AbstractMap类。但二者都实现了Map接口。
    Hashtable继承自Dictionary类,Dictionary类是一个已经被废弃的类(见其源码中的注释)。父类都被废弃,自然而然也没人用它的子类Hashtable了。

    2、HashMap线程不安全,HashTable线程安全

      javadoc中关于hashmap的一段描述如下:此实现不是同步的。如果多个线程同时访问一个哈希映射,**而其中至少一个线程从结构上修改了该映射**,则它必须保持外部同步。
      Hashtable 中的方法大多是Synchronize的,而HashMap中的方法在一般情况下是非Synchronize的。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步,但使用HashMap时就必须要自己增加同步处理。HashTable实现线程安全的代价就是效率变低,因为会锁住整个HashTable,而ConcurrentHashMap做了相关优化,因为ConcurrentHashMap使用了分段锁,并不对整个数据进行锁定,效率比HashTable高很多。
      **HashMap底层是一个Entry数组,当发生hash冲突的时候,hashmap是采用链表的方式来解决的,在对应的数组位置存放链表的头结点。对链表而言,新加入的节点会从头结点加入。**
      HashMap的put方法:
    
    void addEntry(int hash, K key, V value, int bucketIndex) { //新增Entry,将“key-value”插入指定位置,bucketIndex是位置索引。
            Entry<K,V> e = table[bucketIndex];  保存“bucketIndex”位置的值到“e”中
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
            if (size++ >= threshold)       // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小2倍
                resize(2 * table.length);
        }
    

    在hashmap的put方法调用addEntry()方法,假如A线程和B线程同时对同一个数组位置调用addEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。
    故解决方法就是使用 使用ConcurrentHashMap。
    这里要说一下 就是HashMap的迭代器(Iterator)是fail-fast迭代器,故当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException异常,而Hashtable的enumerator迭代器不是fail-fast的。但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。

    3.包含的contains方法不同

    HashMap是没有contains方法的,而包括containsValue和containsKey方法;hashtable则保留了contains方法,效果同containsValue,还包括containsValue和containsKey方法。

    4.是否允许null值

    Hashmap是允许key和value为null值的,用containsValue和containsKey方法判断是否包含对应键值对;HashTable键值对都不能为空,否则包空指针异常。

    5.计算hash值方式不同

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

    ①:HashMap有个hash方法重新计算了key的hash值,因为hash冲突变高,所以通过一种方法重算hash值的方法:

    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    注意这里计算hash值,先调用hashCode方法计算出来一个hash值,再将hash与右移16位后相异或,从而得到新的hash值
    **②:Hashtable通过计算key的hashCode()**来得到hash值就为最终hash值。

    它们计算索引位置方法不同:
    HashMap在求hash值对应的位置索引时,index = (n - 1) & hash。将哈希表的大小固定为了2的幂,因为是取模得到索引值,故这样取模时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。

    HashTable在求hash值位置索引时计算index的方法:

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

    &0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号位改变,而后面的位都不变。

    6.扩容方式不同(容量不够)

    当容量不足时要进行resize方法,而resize的两个步骤:
    ①扩容;
    ②rehash:这里HashMap和HashTable都会会重新计算hash值而这里的计算方式就不同了(看5);
    HashMap 哈希扩容必须要求为原容量的2倍,而且一定是2的幂次倍扩容结果,而且每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入;
    而Hashtable扩容为原容量2倍加1;

    7.解决hash冲突方式不同(地址冲突)

    先看jdk8之前:
    在这里插入图片描述
    查找时间复杂度慢慢变高;
    Java8,HashMap中,当出现冲突时可以:

    1.如果冲突数量小于8,则是以链表方式解决冲突。
    2.而当冲突大于等于8时,就会将冲突的Entry转换为**红黑树进行存储。**
    3.而又当数量小于6时,则又转化为链表存储。
    

    而在HashTable中, 都是以链表方式存储。

    展开全文
  • 本文主要介绍HashMap Hashtable的区别,这里整理了相关资料并详细介绍了HashMap Hashtable的区别及其工作原理使用方法,有需要的朋友可以看一下
  • HashMap和Hashtable的区别。 1:hashMap 是非线程安全的。效率高。 hashTable 是线程安全的。效率低。 HashMap是Hashtable的轻量级实现(非线程安全的实现),: 2:他们都完成了Map接口主要区别在于HashMap允许空...

    1.HashMap 与 HashTable的区别:

    • HashMap和Hashtable的区别。
      1:hashMap 是非线程安全的。效率高。
      hashTable 是线程安全的。效率低。
      HashMap是Hashtable的轻量级实现(非线程安全的实现),:
      2:他们都完成了Map接口主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。
      HashMap允许将null作为一个entry的key或者value,而Hashtable不允许。

    3:HashMap把Hashtable的contains方法去掉了,改成containsvalue和containsKey因为contains方法容易让人引起误解。 Hashtable继承自Dictionary类,而HashMap是Java1.2引进的Map interface的一个实现。
    最大的不同是,
    Hashtable的方法是Synchronize的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而HashMap 就必须为之提供外同步。
    Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。

    • @author Administrator
    
    public class HashTableDemo {
    
    	public static void main(String[] args) {
    		HashMap<String,String> hashMap = new HashMap<String,String>();
    		hashMap.put(null, null);
    		hashMap.containsKey("");
    		hashMap.containsValue("");
    		
    		Hashtable<String,String> hashtable = new Hashtable<String,String>();
    		hashtable.put("a", "1");
    		hashtable.put(null, null);// 区别:会出现异常。
    //		hashtable.contains(value) 这个方法容易误解。
    		
    		
    		
    		
    	}
    
    }
    
    展开全文
  • HashMap和HashTable的区别

    2021-03-07 21:18:08
    HashMap和HashTable的区别 HashMap和HashTable的区别 (条理上还需要整理,也是先说相同点,再说不同点),HashMap是HashTable的轻量级实现(非线程安全的实现) ,他们都完成了Map接口,主要区别在于HashMap允许空( null...

    HashMap和HashTable的区别

    HashMap和HashTable的区别

    (条理上还需要整理,也是先说相同点,再说不同点),HashMap是HashTable的轻量级实现(非线程安全的实现) ,他们都完成了Map接口,主要区别在于HashMap允许空( null )键值( key ),由于非线程安全,在只有一个线程访问的情况下,效率要高于Hashtable,HashMap允许将null作为一个entry的key或者value ,而Hashtable不允许。

    HashMap把Hashtable的contains方法去掉了,改成containsvalue和containsKey,因为contains方法容易让人引起误解。Hashtable继承自Dictionary类,而HashMap是Javal.2引进的Map interface的一个实现。

    最大的不同是, Hashtable的方法是Synchronize 的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而HashMap就必须为 之提供外同步。
    Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。就HashMap与HashTable主要从三方面来说:

    一·历史原因:Hashtable是基于陈旧的Dictionary
    类的, HashMap是Java 1.2引进的Map
    接口的一个实现

    二、同步性:Hashtable是线程安全的,也就是说是同
    步的,而HashMap是线程序不安全的,不是同步的。

    三、
    值:只有HashMap可以让你将空值作为一个表的条目的
    key或value.

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,262
精华内容 2,904
关键字:

hashmap和hashtable的区别