Saturday, June 14, 2014

[电面基础]Java基于Map/Hashtable的问题讨论



电面基础:Java基于Map/Hashtable的问题讨论


前言:电话面试(简称电面)以知识点考察为主,在数据结构方面,对于Map/Hashtable的考察绝对是必不可少的一部分。Java作为一门被业界广为应用的语言,在集合类方面有非常全面成熟的解决方案,因此我们用一个专题的形式来讨论在Java中有关Map/Hashtable题和解答。


通常在面试中,面试官会以比较简单的问题开始,比如


“Have you used HashMap before?”  or “What is HashMap? why do we use it?”


简单问题的背后主要考察candidate是否了解和使用过Hash相关的数据结构。那么根据HashMap在java中的实现,以下几点应该在回答中准确的表达:
  • Hash相关的数据结构本质上都是key value pair;
  • Hash中不能存在duplicate key;
  • HashMap提供非常快速查找时间复杂度;
  • 在HashMap具体实现中,Null可以作为key或者value存在;
  • HashMap不是线程安全;


由于Java中和Hash相关的类比较多,我们帮助大家梳理一下,比如


“What’s the difference between Hashtable and HashMap?”


回到最基本的知识,Java中有一个非常重要的Interface叫做Map,其定义: An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. 像我们平时讨论Hash时经常提到的方法”get(), put(), containsKey(), entrySet()”等其实都是定义在Map这个interface中。而Hashtable和HashMap都实现了Map interface,这是他们最大的共同点。


包子tip: 在我们培训和面试的过程中,很多同学认为Map等同于HashMap,这其实是很不准确的。Map定义了key-value pair操作的基本接口;而HashMap只是Map的一种Hash实现,事实上还有很多其他的数据结构,比如TreeMap,用完全不同的方式实现Map interface。不同的Map实现方式都有相对应的使用场景,之后我们也会聊到。在面试中使用正确的terminology是很重要的细节,如果不注意会非常影响面试官的印象。


具体对于Hashtable和HashMap的不同之处,主要有以下几点:
  • HashMap不提供线程安全,而Hashtable是线程安全;同样,在单线程环境下,HashMap的性能要比Hashtable好一些;(对于有线程安全需求的场景,可以使用Collections.synchronizedMap(HashMap) 来返回一个线程安全的HashMap)
  • HashMap允许Null作为key或者value, Hashtable不允许;
  • HashMap不保证内部元素的存储顺序;(遍历时无序)
  • HashMap中的iterator是fast-fail iterator,Hashtable的不是;(具体讨论请参考下节Iterater/Emumeration)


接下来,问题就开始针对Hash的细节,比如


"How HashMap works in Java?” or "How does get()/put() method of HashMap works in Java?"


HashMap自然是基于Hash实现的key-value pair。具体实现,一个HashMap在内部会维护一个key-value类型(Map.Entry<K, V>) 的数组。在get()/put()中,它使用定义好的hash()算出key object在内部数组中的索引,然后在get()/put()中做相应的存取。如果HashMap中的元素能够相对均匀的分布在数组中的时候,get()/put()是可以达到非常好的常数时间复杂度。


再细致一些,对于非String类型的key,hash()使用key的hashCode()计算出该key-value pair对应在数组的索引(String类型的key有另一套计算hash()的方法,再次不做赘述),在get()方法中会使用key的equal()方法判断数组中的<key, value>中的key是否与传入的key相等。由此可见,在HashMap的使用中,key类型中定义的hashCode()和equal()方法都是非常重要的。假设key内部的值发生变化,导致hashCode()/equal()的结果改变,那么该key在HashMap中的存取则会产生问题。

再接下来,问一下exception case,比如


"What will happen if two different objects have same hashcode?” or "How will you retrieve Value object  if two keys will have same hashcode?”


如上一个问题所说,hash()会直接使用key的hashCode()结果,如果两个key的hashCode()结果相同,那么意味着他们对应的<key, value>被hash到数组中的同一个索引位置,产生所谓的hash collision。处理hash collision,主要有separate chain和open address两种方法。HashMap中使用的是separate chain的方法,即把所有map到同一个数组位置的元素用链表的形式存储,这样的后果就是查询的复杂度会相对上升低(因为需要遍历链表)。值得一提的是,每一个HashMap的Entry中都存有Key, Value, Pointer to next Entry, hashValueOfKey(想一想为什么)。

问一些failure case,比如


“What happens On HashMap in Java if the size of the HashMap  exceeds a given threshold defined by load factor?” or “do you see any problem with resizing of HashMap  in Java?”


Load factor(default to 75%)和Initial capacity(default to 16)是HashMap表的两个重要属性,如果HashMap中entry数量超过了threshold(loadfactor *capacity) ,那么HashMap就不得不扩充capacity(否则hash collison发生的概率就会大大增加,导致整个HashMap性能下降),扩充capacity是一件比较麻烦的事情,因为数组的连续性,HashMap不得不开辟一块更大数组,还要把原来的entries全部transfer到新的数组中,在某些情况下还需要重新计算key的hash()结果。另一方面,HashMap的capacity也不是越大越好,事实上HashMap的遍历本质上是基于内部数组的遍历,如果内部数组是无意义的大,那么遍历HashMap相对来说不是特别高效。


No comments:

Post a Comment