java数据结构面试题大全

TheDisguiser 2020-08-17 10:31:19 java常见问答 5717

上几次我们已经深入了解过了java中数据结构及特点,现在就来看一些面试题来巩固一下。

一、什么是数据结构?

简单地说,数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。首先我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。

为什么我们需要数据结构?

数据是计算机科学当中最关键的实体,而数据结构则可以将数据以某种组织形式存储,因此,数据结构的价值不言而喻。

无论你以何种方式解决何种问题,你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单,还是只是简单的电话簿问题。

数据需要根据不同的场景,按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

二、java常见的数据结构有哪些?

set,list,map,Quene.二叉树

set子类:

HashSet:HashSet不能保证元素的排列顺序;使用Hash算法来存储集合中的元素,有良好的存取和查找性能;通过equal()判断两个元素是否相等,并两个元素的hashCode()返回值也相等。

TreeSet是SortedSet接口的实现类,根据元素实际值的大小进行排序;采用红黑树的数据结构来存储集合元素;支持两种排序方法:自然排序(默认情况)和定制排序。前者通过实现Comparable接口中的compareTo()比较两个元素之间大小关系,然后按升序排列;后者通过实现Comparator接口中的compare()比较两个元素之间大小关系,实现定制排列。

list子类:

ArrayList:

底层数据结构是数组,查询快,增删慢。 线程不安全,效率高。 空间不足时,增加原来空间的50%。

Vector:

底层数据结构是数组,查询快,增删慢。 线程安全,效率低。 空间不足时,增加原来空间的一倍。 Vector相对ArrayList查询慢(线程安全的) ,Vector相对LinkedList增删慢(数组结构)

LinkedList: 底层数据结构是链表,查询慢,增删快。 线程不安全,效率高。

Map子类:HashMap、Hashtable、 ConcurrentHashMap,LinkedHashMap、TreeMap

HashMap基于AbstractMap类,实现了Map、Cloneable(能被克隆)、Serializable(支持序列化)接口; 非线程安全;允许存在一个为null的key和任意个为null的value;采用链表散列的数据结构,即数组和链表的结合;初始容量为16,填充因子默认为0.75,扩容时是当前容量翻倍,即2capacity,hashmap采用拉链法解决冲突。

三、怎么保证HashMap线程安全?

ConcurrentHashMap是线程安全的HashMap,它采取锁分段技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。在JDK1.8中对ConcurrentHashmap做了两个改进:

取消segments字段,直接采用transient volatile HashEntry[] table保存数据,将数组元素作为锁,对每一行数据进行加锁,可减少并发冲突的概率

数据结构由“数组+单向链表”变为“数组+单向链表+红黑树”,使得查询的时间复杂度可以降低到O(logN),改进一定的性能。

四、HashMap如何实现有序?

HashMap是无序的,而LinkedHashMap是有序的HashMap,默认为插入顺序,还可以是访问顺序,基本原理是其内部通过Entry维护了一个双向链表,负责维护Map的迭代顺序。

五、HashMap在put、get元素的过程?体现了什么数据结构?

向Hashmap中put元素时,首先判断key是否为空,为空则直接调用putForNullKey(),不为空则计算key的hash值得到该元素在数组中的下标值;如果数组在该位置处没有元素,就直接保存;如果有,还要比较是否存在相同的key,存在的话就覆盖原来key的value,否则将该元素保存在链头,先保存的在链尾。

从Hashmap中get元素时,计算key的hash值找到在数组中的对应的下标值,返回该key对应的value即可,如果有冲突就遍历该位置链表寻找key相同的元素并返回对应的value

由此可看出HashMap采用链表散列的数据结构,即数组和链表的结合,在Java8后又结合了红黑树,当链表元素超过8个将链表转换为红黑树。

二叉树:

B+树:

平衡二叉树(AVL树):各个结点左右子树深度差的绝对值不超过1。

哈夫曼树:带权路径长度最小的二叉树称为最优二叉树。哈夫曼树构造不唯一,但所有叶子结点的带权路径长度之和都是最小的。

红黑树:一种自平衡二叉查找树,它的性质有:

节点是红色或黑色。

根节点是黑色。

每个叶子节点都是黑色的空节点(NIL节点)。

每个红色节点的两个子节点都是黑色。

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

扩展内容:

一般除了基于数据结构的问题外,大多数的编程工作访谈还会询问算法,设计,位操作及基于逻辑的一般问题,这些概念的练习十分重要,因为在实际面试中有时解决它们会很棘手。

1. 如何实现冒泡排序算法?

2. 如何实现迭代快速排序算法?

3. 你如何实现插入排序算法?

4. 如何实现合并排序算法?

5. 如何实现桶排序算法?

6. 你如何实现计数排序算法?

7. 如何实现基数排序算法?

8. 如何在不使用第三个变量的情况下交换两个数字?

9. 如何检查两个矩形是否相互重叠?

10. 你如何设计自动售货机?

以上就是本篇文章的所有内容,更多java面试题内容,敬请关注奇Q工具网了解详情。

推荐阅读:

正则表达式的规则详解

java正则表达式替换,正则表达式是什么?

javascript数组排序怎么编写?JS数组排序三种方法实现