登录 立即注册
安币:

安卓巴士 - 安卓开发 - Android开发 - 安卓 - 移动互联网门户

查看: 915|回复: 7

经常被问到的有深度有内涵的数据结构面试题

[复制链接]

89

主题

597

帖子

1万

安币

码皇(巴士元老)

Rank: 8Rank: 8

QQ
发表于 2017-4-17 13:57:11 | 显示全部楼层 |阅读模式
本帖最后由 cqkxzsxy 于 2017-4-17 14:00 编辑

    数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构通常称为Java集合框架。
    Java工具包提供了强大的数据结构,在开发中一般都离不开Java集合框架,主要包括Collection和Map两个主要接口,而程序中最终使用的数据结构是继承自这两个接口的数据结构类。
    从上面的Java集合框架图可以看到,主要分为Set、 List、Queue和Map四大体系,然而有很多开发者理不清他们之间的区别和联系,特别是对于一些小白来说如意混淆。这也是Java习惯工作面试时经常被考的知识点,那么我们今天来一起温习一下。
    List接口通常表示一个列表(数组、队列、链表、栈等),其中的元素可以重复,常用实现类为ArrayList和LinkedList,另外还有不常用的Vector。同时LinkedList还是实现了Queue接口,因此也可以作为队列使用。
    Set接口通常表示一个集合,其中的元素不允许重复(通过hashcode和equals方法保证),常用实现类有HashSet和TreeSet,HashSet是通过Map中的HashMap实现的,而TreeSet是通过Map中的TreeMap实现的。另外,TreeSet还实现了SortedSet接口,因此是有序的集合。
    Queue接口通常表示一个队列,是一种先进先出的数据结构,元素在队列末尾添加,在队列头部删除。Queue接口扩展自Collection,并提供插入、提取、检验等操作。
    Map是一个映射接口,其中的每个元素都是一个key-value键值对。
    小编一般都是这样来理解记忆其大致区别的:
    Set代表无序、不可重复的集合,
    List代表有序、重复的集合,
    Map代表具有映射关系的集合,
    Queue代表一种队列集合。

    关于集合框架的内容特别多,这里就不一一进行说明,后续再逐一分解,今天先来一起温习一下有关Java集合框架有关的面试题。
ArrayList和LinkedList的区别?
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
    2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
    3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
    4.查找操作indexOf,lastIndexOf,contains等,两者差不多。
    5.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
ArrayList的扩容机制如何?
    如果在初始化ArrayList的时候没有指定初始化长度的话,默认的长度为10。在增加新元素的时候如果超过了原始的容量的话,新容量=原始容量*3/2+1。
    这个问题非常简单,稍微看一下源码就知道了。
  • public void ensureCapacity(int minCapacity) {  
  •     modCount++;  
  •     int oldCapacity = elementData.length;  
  •     if (minCapacity > oldCapacity) {  
  •         Object oldData[] = elementData;  
  •         int newCapacity = (oldCapacity * 3)/2 + 1;  
  •         if (newCapacity < minCapacity)  
  •             newCapacity = minCapacity;  
  •         // minCapacity is usually close to size, so this is a win:  
  •         elementData = Arrays.copyOf(elementData, newCapacity);  
  •     }  
  • }  

Vector和ArrayList的区别?
相同之处:
    1.它们都是List
    2.它们都实现了RandomAccess和Cloneable接口,都支持快速随机访问,能克隆自己。
    3.它们都是通过数组实现的,本质上都是动态数组。
    4.它们的默认数组容量是10。
    5.它们都支持Iterator和listIterator遍历。
不同之处:
    1.线程安全性不一样。ArrayList是非线程安全的,而Vector是线程安全的; ArrayList适用于单线程,Vector适用于多线程。
    2.对序列化支持不同。ArrayList支持序列化,而Vector不支持。
    3.构造方法个数不同。ArrayList有3个构造方法,而Vector有4个构造方法。Vector除类似的3个构造方法之外,另外的一个构造方法可以指定容量增加系数。
    4.容量增加方式不同。逐个添加元素时,若ArrayList容量不足时,“新的容量”=“(原始容量x3)/2 + 1”。而Vector的容量增长与“增长系数有关”,若指定了“增长系数”,且“增长系数有效(即,大于0)”;那么,每次容量不足时,“新的容量”=“原始容量+增长系数”。若增长系数无效(即,小于/等于0),则“新的容量”=“原始容量 x 2”。
    5.对Enumeration的支持不同。Vector支持通过Enumeration去遍历,而List不支持。
Set 和List的区别?
    1.List和Set都是继承自Collection接口。
    2.List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的) 。
    3.List接口有三个实现类:LinkedList,ArrayList,Vector ,Set接口有两个实现类:HashSet(底层由HashMap实现),LinkedHashSet。
HashMap和HashSet的区别。
    1.HashMap实现了Map接口,HashSet实现了Set接口。
    2.HashMap储存键值对,HashSet仅仅存储对象(且无重复对象)。
    3.HashMap使用put()方法将元素放入map中,HashSet使用add()方法将元素放入set中。
    4.HashMap中使用键对象来计算hashcode值,HashSet使用成员对象来计算hashcode值。对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false。
    5.HashMap比较快,因为是使用唯一的键来获取对象;HashSet比HashMap来说更慢。
HashMap与HashTable的区别?
    1.HashTable的方法是同步的,HashMap未经同步,所以HashMap效率更高。
    2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
    3.HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样,HashMap没有contains方法。
    4.HashTable使用Enumeration,HashMap使用Iterator。
    5.HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
    6.哈希值的使用不同,HashTable直接使用对象的hashCode。
HashMap的工作原理?HashMap的get()方法的工作原理?
    “HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”
    这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。
  • public V put(K key, V value) {  
  •     if (key == null)  
  •         return putForNullKey(value); //null总是放在数组的第一个链表中  
  •     int hash = hash(key.hashCode());  
  •     int i = indexFor(hash, table.length);  
  •     //遍历链表  
  •     for (Entry<K,V> e = table; e != null; e = e.next) {  
  •         Object k;  
  •         //如果key在链表中已存在,则替换为新value  
  •         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  •             V oldValue = e.value;  
  •             e.value = value;  
  •             e.recordAccess(this);  
  •             return oldValue;  
  •         }  
  •     }  
  •     modCount++;  
  •     addEntry(hash, key, value, i);  
  •     return null;  
  • }


  • public V get(Object key) {  
  •     if (key == null)  
  •         return getForNullKey();  
  •     int hash = hash(key.hashCode());  
  •     //先定位到数组元素,再遍历该元素处的链表  
  •     for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {  
  •         Object k;  
  •         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
  •             return e.value;  
  •     }  
  •     return null;  
  • }  

当两个对象的hashcode相同会发生什么?
    从这里开始,真正的困惑开始了,一些面试者会回答因为hashcode相同,所以两个对象是相等的,HashMap将会抛出异常,或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法,并告诉他们两个对象就算hashcode相同,但是它们可能并不相等。一些面试者可能就此放弃,而另外一些还能继续挺进,他们回答“因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。
    但故事还没有完结,面试官会继续问:
如果两个键的hashcode相同,你如何获取值对象?
    面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。
    其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。完美的答案!
    许多情况下,面试者会在这个环节中出错,因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现,而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。
    如果你认为到这里已经完结了,那么听到下面这个问题的时候,你会大吃一惊。
如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
    除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。如果你能够回答这道问题,下面的问题来了:
你了解重新调整HashMap大小存在什么问题吗?
    你可能回答不上来,这时面试官会提醒你当多线程的情况下,可能产生条件竞争(race condition)。
    当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)
为什么String、 Interger这样的wrapper类适合作为键?
    String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
我们可以使用自定义的对象作为键吗?
    这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
我们可以使用CocurrentHashMap来代替Hashtable吗?
    这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。
Collection和Collections的区别。
    Collection 是一个集合接口,它提供了对集合对象进行基本操作的通用接口方法。
    Collections 是一个包装类,它包含有各种有关集合操作的静态多态方法,此类不能实例化。
a.hashCode() 有什么用?与 a.equals(b) 有什么关系?
    hashCode() 方法是相应对象整型的 hash 值。它常用于基于 hash 的集合类,如 Hashtable、HashMap、LinkedHashMap等等。它与 equals() 方法关系特别紧密。根据 Java 规范,两个使用 equal() 方法来判断相等的对象,必须具有相同的 hash code。
为什么在重写 equals 方法的时候需要重写 hashCode 方法?
    因为有强制的规范指定需要同时重写 hashcode 与 equal 是方法,许多容器类,如 HashMap、HashSet 都依赖于 hashcode 与 equals 的规定。

    以上这些经常被问到的有深度有内涵的数据结构面试题,现在你掌握了多少?

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

27

主题

9627

帖子

1884

安币

Android大神

Rank: 6Rank: 6

发表于 2017-4-17 14:02:41 | 显示全部楼层
mark,收藏了

9

主题

9361

帖子

1823

安币

Android大神

Rank: 6Rank: 6

QQ达人

发表于 2017-4-17 14:06:24 | 显示全部楼层
写的真的很不错

1

主题

9147

帖子

2924

安币

Android大神

Rank: 6Rank: 6

发表于 2017-4-17 14:08:16 | 显示全部楼层
好好 学习了 确实不错

6

主题

9448

帖子

2892

安币

Android大神

Rank: 6Rank: 6

发表于 2017-4-17 14:11:19 | 显示全部楼层
感谢大神~

0

主题

9235

帖子

2412

安币

Android大神

Rank: 6Rank: 6

发表于 2017-4-17 14:15:15 | 显示全部楼层
膜拜大神~

17

主题

9204

帖子

2349

安币

Android大神

Rank: 6Rank: 6

发表于 2017-4-17 14:16:35 | 显示全部楼层
感谢分享,安卓巴士有你更精彩:lol

0

主题

1

帖子

12

安币

初级码农

Rank: 1

发表于 2019-3-2 20:46:33 | 显示全部楼层
本帖最后由 bunnycoder 于 2019-3-2 20:49 编辑

这是很好的信息。 Interviewbit是准备编码面试的重要资源。 该平台被游戏化。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

站长推荐

通过邮件订阅最新安卓weekly信息
上一条 /4 下一条

下载安卓巴士客户端

全国最大的安卓开发者社区
联系我们
关闭
合作电话:
15618560077
Email:
805941275@qq.com
商务市场合作/投稿
问题反馈及帮助
联系我们

广告投放| 广东互联网违法和不良信息举报中心|中国互联网举报中心|下载客户端|申请友链|手机版|站点统计|安卓巴士 ( 粤ICP备15117877号 )

快速回复 返回顶部 返回列表