搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 青梅竹码 > Java面经整理(一)---HashMap

Java面经整理(一)---HashMap

青梅竹码 2019-02-13
举报

1.1 HashMap特性?

HashMap的特性:HashMap存储键值对,实现快速存取数据;允许null键/值;非同步;不保证有序(比如插入的顺序)。实现map接口。



1.2 HashMap的原理,内部数据结构?

HashMap是基于hashing的原理,底层使用哈希表(数组 + 链表)实现。里边最重要的两个方法put、get,使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。 

存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。



1.3 讲一下 HashMap 中 put 方法过程?

1.对key的hashCode做hash操作,然后再计算在bucket中的index(1.5 HashMap的哈希函数); 

2.如果没碰撞直接放到bucket里; 

3.如果碰撞了,以链表的形式存在buckets后; 

4.如果节点已经存在就替换old value(保证key的唯一性) 

5.如果bucket满了(超过阈值,阈值=loadfactor*current capacity,load factor(负载因子)默认0.75),就要resize。



1.4 get()方法的工作原理?

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表中查找对应的节点。



1.5 HashMap中hash函数怎么是是实现的?还有哪些 hash 的实现方式?

1. 对key的hashCode做hash操作(高16bit不变,低16bit和高16bit做了一个异或); 

2. h & (length-1); //通过位操作得到下标index。

还有数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。



1.6 HashMap 怎样解决冲突?



1.6.1 扩展问题1:当两个对象的hashcode相同会发生什么?

因为两个对象的Hashcode相同,所以它们的bucket位置相同,会发生“碰撞”。HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。



1.6.2 扩展问题2:抛开 HashMap,hash 冲突有那些解决办法?



1.7 如果两个键的hashcode相同,你如何获取值对象?

重点在于理解hashCode()与equals()。 

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。两个键的hashcode相同会产生碰撞,则利用key.equals()方法去链表或树(java1.8)中去查找对应的节点。



1.8 针对 HashMap 中某个 Entry 链太长,查找的时间复杂度可能达到 O(n),怎么优化?

将链表转为红黑树,实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。



1.9 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

扩容。这个过程也叫作rehashing,因为它重建内部数据结构,并调用hash方法找到新的bucket位置。 

大致分两步: 

1.扩容:容量扩充为原来的两倍(2 * table.length); 

2.移动:对每个节点重新计算哈希值,重新计算每个元素在数组中的位置,将原来的元素移动到新的哈希表中。 

   

补充: 

loadFactor:加载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f; 

capacity:容量; 

threshold:阈值=capacity*loadFactor。

当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍(capacity*2); 

size:HashMap的大小,它是HashMap保存的键值对的数量。



1.10 为什么String, Interger这样的类适合作为键?

String, Interger这样的类作为HashMap的键是再适合不过了,而且String最为常用。 

因为String对象是不可变的,而且已经重写了equals()和hashCode()方法了。 

1.不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。 

注:String的不可变性可以看这篇文章《【java基础】浅析String》。 

2.因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。



1.11、HashMap与HashTable区别

Hashtable可以看做是线程安全版的HashMap,两者几乎“等价”(当然还是有很多不同)。Hashtable几乎在每个方法上都加上synchronized(同步锁),实现线程安全。


1.HashMap继承于AbstractMap,而Hashtable继承于Dictionary; 

2.线程安全不同。Hashtable的几乎所有函数都是同步的,即它是线程安全的,支持多线程。而HashMap的函数则是非同步的,它不是线程安全的。若要在多线程中使用HashMap,需要我们额外的进行同步处理; 

3.null值。HashMap的key、value都可以为null。Hashtable的key、value都不可以为null; 

4.迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException。 

5.容量的初始值和增加方式都不一样:HashMap默认的容量大小是16;增加容量时,每次将容量变为“原始容量x2”。Hashtable默认的容量大小是11;增加容量时,每次将容量变为“原始容量x2 + 1”; 

6.添加key-value时的hash值算法不同:HashMap添加元素时,是使用自定义的哈希算法。Hashtable没有自定义哈希算法,而直接采用的key的hashCode()。 

7.速度。由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。



1.12 能否让HashMap同步?

HashMap可以通过下面的语句进行同步:

Map m = Collections.synchronizeMap(hashMap);



1.13“你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存Entry对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。



1.14 什么是HashSet?

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

public boolean add(Object o)方法用来在Set中添加元素,当元素值重复时则会立即返回false,如果成功添加的话会返回true。



1.15“你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

HashMap实现了Map接口,Map接口对键值对进行映射。Map中不允许重复的键。Map接口有两个基本的实现,HashMap和TreeMap。TreeMap保存了对象的排列次序,而HashMap则不能。HashMap存储的是键值对,允许键和值为null。HashMap是非synchronized的,但collection框架提供方法能保证HashMap synchronized,这样多个线程同时访问HashMap时,能保证只有一个线程更改Map。

public Object put(Object Key,Object value)方法用来将元素添加到map中。



1.16 HashSet与HashMap的区别?

1.17.关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法?

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

因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。



1.18如果两个键的hashcode相同,你如何获取值对象?

当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。

注意:面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。

一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。



1.19如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。



1.20你了解重新调整HashMap大小存在什么问题吗?

当多线程的情况下,可能产生条件竞争。

当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

注意,jdk1.8阈值是8。



1.21.为什么String, Interger这样的wrapper类适合作为键?

String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。



1.22我们可以使用自定义的对象作为键吗? 

这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。



1.23我们可以使用CocurrentHashMap来代替Hashtable吗?

我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。



1.24 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]为头结点的链表中。



1.25 HashMap扩容问题?

扩容是是新建了一个HashMap的底层数组,而后调用transfer方法,将就HashMap的全部元素添加到新的HashMap中(要重新计算元素在新的数组中的索引位置)。 很明显,扩容是一个相当耗时的操作,因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此,我们在用HashMap的时,最好能提前预估下HashMap中元素的个数,这样有助于提高HashMap的性能。

HashMap共有四个构造方法。构造方法中提到了两个很重要的参数:初始容量和加载因子。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中槽的数量(即哈希数组的长度),初始容量是创建哈希表时的容量(从构造函数中可以看出,如果不指明,则默认为16),加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。

默认加载因子为0.75,如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。



1.26什么是hash,什么是碰撞,什么是equals ?

Hash:是一种信息摘要算法,它还叫做哈希,或者散列。我们平时使用的MD5,SHA1都属于Hash算法,通过输入key进行Hash计算,就可以获取key的HashCode(),比如我们通过校验MD5来验证文件的完整性。

 碰撞:好的Hash算法可以出计算几乎出独一无二的HashCode,如果出现了重复的hashCode,就称作碰撞;

就算是MD5这样优秀的算法也会发生碰撞,即两个不同的key也有可能生成相同的MD5。

equals与==是相同的。



1.27如何减少碰撞?

使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《Java面经整理(一)---HashMap》的版权归原作者「青梅竹码」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注青梅竹码微信公众号

青梅竹码微信公众号:qmzm2019

青梅竹码

手机扫描上方二维码即可关注青梅竹码微信公众号

青梅竹码最新文章

精品公众号随机推荐

举报