`
- 浏览:
31210 次
- 性别:
- 来自:
北京
-
HashMap是基于哈希表的Map接口的非同步实现。
数组
数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;
链表
链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。
哈希表
那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。
一些常见的面试题:
1、HashMap的工作原理
HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象,作为Map.Entry。
2、当两个对象的hascode值相同时如何获取对象?
因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。如果有两个值对象储存在同一个bucket,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。
3、如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”
默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。
当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。
4、为什么String, Interger这样的wrapper类适合作为键?
String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
5、我们可以使用自定义的对象作为键吗?
这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
6、我们可以使用CocurrentHashMap来代替Hashtable吗?
这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
详细介绍了hashMap原理,值得一看,对于面试者有很大帮助
hashMap基本工作原理,图解分析,基础Map集合
hashmap的底层及源码解析,很适合大家的学习,不要积分。
动力节点的Java课程适合绝对零基础的观看,教程中讲解了Java开发环境搭建、Java的基础语法、Java的面向对象。每一个知识点都讲解的非常细腻,由浅入深。适合非计算机专业,想转行做Java开发的朋友,或者想让Java基础...
主要介绍了HashMap工作原理_动力节点Java学院整理,需要的朋友可以参考下
HashMap底层原理.md
HashMap底层原理
hashMap基本工作原理,图解分析,基础Map集合
详细分析HashMap的存储原理,key值的hash地址以及扩容
hashmap实现原理.pdf
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了...而Hashtable则不能(原因就是equlas()方法需要对象,因为HashMap是后出的API经过处理才可以)2、HashMap的工作原理是什么?
Hashmap底层原理.md
hashMap基本原理,内存知识
十六、HashMap 底层原理
HashMap的工作原理Java开发Java经验技巧共4页.pdf.zip
基于HashMap的用户标签处理兼Java中HashMap实现原理研究
HashMap原理解析
HashMap的实现原理
大家在面试中,最常见的问题肯定包含对hashmap相关问题,源码、多线程安全、1.7和1.8区别等等,本文详细总结了以上问题,希望对你有帮助!!
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...