资讯专栏INFORMATION COLUMN

HashMap、HashSet、Hashtable的区别

zhangxiangliang / 1020人阅读

摘要:这样做的目的是提高取对象的效率。在单线程情况下效率较高在的多线程情况下,同步操作能保证程序执行的正确性。

突然发现整理了很多笔记,应该放这里做备用

Hashtable和HashMap

主要区别:线程安全性,同步(synchronization),以及速度。

HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null。Hashtable是线程安全的,多个线程可以共享一个Hashtable。

HashMap的同步问题可通过Collections的一个静态方法得到解决,Map Collections.synchronizedMap(Map m) 返回一个同步的Map。

HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。fail-fast结构上更改时(删除或者插入一个元素),将会抛出ConcurrentModificationException异常。

HashMap不能保证随着时间的推移Map中的元素次序是不变的。

HashSet和HashMap的区别

HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象。如果我们没有重写这两个方法,将会使用这个方法的默认实现。

Map中不允许重复的键。Map接口有两个基本的实现,HashMap和TreeMap。TreeMap保存了对象的排列次序,而HashMap则不能。HashMap允许键和值为null。

HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算法决定集合元素的存储位置,这样可以保证能快速存、取集合元素;对于 HashMap 而言,系统 key-value 当成一个整体进行处理,系统总是根据 Hash 算法来计算 key-value 的存储位置,这样可以保证能快速存、取 Map 的 key-value 对。

HashMap
public V put(K key, V value) {   
    // 如果 key 为 null,调用 putForNullKey 方法进行处理  
    if (key == null)   
        return putForNullKey(value);   
    // 根据 key 的 keyCode 计算 Hash 值  
    int hash = hash(key.hashCode());   
    // 搜索指定 hash 值在对应 table 中的索引  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素  
    for (Entry e = table[i]; e != null; e = e.next)   
    {   
        Object k;   
        // 找到指定 key 与需要放入的 key 相等(hash 值相同  
        // 通过 equals 比较放回 true)  
        if (e.hash == hash && ((k = e.key) == key   
            || key.equals(k)))   
        {   
            V oldValue = e.value;   
            e.value = value;   
            e.recordAccess(this);   
            return oldValue;   
        }   
    }   
    // 如果 i 索引处的 Entry 为 null,表明此处还没有 Entry   
    modCount++;   
    // 将 key、value 添加到 i 索引处  
    addEntry(hash, key, value, i);   
    return null;   
}  

Map.Entry,每个 Map.Entry 其实就是一个 key-value 对。

当系统决定存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。可以把 Map 集合中的 value 当成 key 的附属。

indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。

根据上面 put 方法的源代码可以看出,当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部。

Map提供了一些常用方法,如keySet()、entrySet()等方法,keySet()方法返回值是Map中key值的集合;entrySet()的返回值也是返回一个Set集合,此集合的类型为Map.Entry,接口中有getKey()、getValue方法。

内部实现

HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结构,但是在jdk1.8里 ,加入了红黑树的实现,当链表的长度大于8时,转换为红黑树的结构。

少于8个的时候,Java中HashMap采用了链地址法。

通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。

而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。

indexFor方法一般想到的是把hash值对数组长度取模运算,但运算较大,因此1.7中使用以下方法,&比%具有更高的效率:

static int indexFor(int h, int length) { 
     return h & (length-1);  //第三步 取模运算
}

在JDK1.8的实现中,优化了高位运算的算法:(h = k.hashCode()) ^ (h >>> 16)

红黑树

红黑树(Red Black Tree) 是一种自平衡二叉查找树。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。除了O(log n)的时间之外,红黑树的持久版本对每次插入或删除需要O(log n)的空间。

equals()和hashCode()

两个obj,如果equals()相等,hashCode()一定相等。
两个obj,如果hashCode()相等,equals()不一定相等(Hash散列值有冲突的情况,虽然概率很低)。

equals()和hashcode()这两个方法都是从object类中继承过来的。equals()是对两个对象的地址值进行的比较(即比较引用是否相同),hashCode()是一个本地方法,它的实现是根据本地机器相关的。

hashCode()在new的用途

JVM每new一个Object,它都会将这个Object丢到一个Hash哈希表中去,这样的话,下次做Object的比较或者取这个对象的时候,它会根据对象的hashcode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。

如果不同的对象确产生了相同的hash值,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。比较两个对象的时候,首先根据他们的hashcode去hash表中找他的对象,当两个对象的hashcode相同,只能根据Object的equal方法来比较这个对象是否equal。

重写equals()的原因

Object的equal方法默认是两个对象的引用的比较,意思就是指向同一内存。

但是,String对象中equals方法是判断值的,而==是地址判断(因为JDK重写了)。

我们很大部分时间都是进行两个对象的比较(而不是比较引用),这个时候Object的equals()方法就不可以了,所以才会有String这些类对equals方法的改写,依次类推Double、Integer、Math等等这些类都是重写了equals()方法的,从而进行的是内容的比较。

重写equals()后要重写hashCode()的理由

java.lnag.Object中对hashCode的约定:

在一个应用程序执行期间,如果一个对象的equals方法做比较所用到的信息没有被修改的话,则对该对象调用hashCode方法多次,它必须始终如一地返回同一个整数。

如果两个对象根据equals(Object o)方法是相等的,则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。

如果两个对象根据equals(Object o)方法是不相等的,则调用这两个对象中任一个对象的hashCode方法,不要求产生不同的整数结果。但如果能不同,则可能提高散列表的性能。

只要改写了就会违约,所以要继续改写。

Hashtable与ConcurrentHashMap区别

ConcurrentHashMap融合了hashtable和hashmap二者的优势。hashmap在单线程情况下效率较高;hashtable在的多线程情况下,同步操作能保证程序执行的正确性。

hashtable每次同步执行的时候都要锁住整个结构:

ConcurrentHashMap锁的方式是稍微细粒度的。

更令人惊讶的是ConcurrentHashMap的读取并发,因为在读取的大多数时候都没有用到锁定,所以读取操作几乎是完全的并发操作,而写操作锁定的粒度又非常细,比起之前又更加快速(这一点在桶更多时表现得更明显些)。只有在求size等操作时才需要锁定整个表。

在迭代时,使用弱一致迭代器,不再是抛出 ConcurrentModificationException,在改变时new新的数据从而不影响原有的数据,iterator完成后再将头指针替换为新的数据。

常见问题 HashMap的工作原理,HashMap的get()方法的工作原理

答:“HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”

关键:HashMap是在bucket中储存键对象和值对象,作为Map.Entry。

当两个对象的hashcode相同会发生什么

因为hashcode相同,所以它们的bucket位置相同,发生冲突,Entry(包含有键值对的Map.Entry对象)会存储在链表中。

hashcode相同如何获取值对象

遍历链表直到找到Entry对象,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点。

超过了负载因子(load factor)定义的容量

默认的负载因子大小为0.75,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小(rehashing)。当多线程的情况下,可能产生条件竞争(race condition),两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。

先这样吧

若有错误之处请指出,更多地关注煎鱼。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69449.html

相关文章

  • HashMapHashSetHashtable,Vector,ArrayList 关系

    摘要:继承的类,泛型为时,注意和其他的类型不同。因为是线程安全简单来说,是个一维数组。同样,指定和,如果中间发生变化则会抛出异常。最后,可以,然后,使用基类可以实现和的快速赋值。线程安全也是线程安全的,和一样,连函数都丧心病狂地同步了。 这么几个比较常用的但是比较容易混淆的概念同出于 java.util 包。本文仅作几个类的浅度解析。 (本文基于JDK1.7,源码来自openjdk1.7。)...

    microcosm1994 评论0 收藏0
  • 这几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0
  • 记一次惨痛面试经历

    摘要:把内存分成两种,一种叫做栈内存,一种叫做堆内存在函数中定义的一些基本类型的变量和对象的引用变量都是在函数的栈内存中分配。堆内存用于存放由创建的对象和数组。 一次惨痛的阿里技术面 就在昨天,有幸接到了阿里的面试通知,本来我以为自己的简历应该不会的到面试的机会了,然而机会却这么来了,我却没有做好准备,被面试官大大一通血虐。因此,我想写点东西纪念一下这次的经历,也当一次教训了。其实面试官大大...

    CoorChice 评论0 收藏0
  • 关于java集合框架总结

    摘要:是哈希表实现的,中的数据是无序的,可以放入,但只能放入一个,两者中的值都不能重复,就如数据库中唯一约束。四和的相同点和区别相同两者都是基于哈希表实现的内部也都是通过单链表解决冲突问题同样实现了序列化和克隆接口区别继承的父类不同。 一.Arraylist与LinkedList有什么区别? 1、ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率...

    Coding01 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<