做我女朋友套路网站,全国的网站建设,wordpress水滴,手机怎么分享wordpressjava面试题29 牛客 以下关于集合类ArrayList、LinkedList、HashMap描述错误的是#xff08;#xff09;
A HashMap实现Map接口#xff0c;它允许任何类型的键和值对象#xff0c;并允许将null用作键或值
B ArrayList和LinkedList均实现了List接口
C 添加和删除元素时
A HashMap实现Map接口它允许任何类型的键和值对象并允许将null用作键或值
B ArrayList和LinkedList均实现了List接口
C 添加和删除元素时ArrayList的表现更佳
D ArrayList的访问速度比LinkedList快
蒙蔽树上蒙蔽果蒙蔽树下你和我我们先看看三者之间的一点使用规则
一、LinkedHashMap
LinkedHashMap会将元素串起来形成一个双链表结构。可以看到其结构在HashMap结构上增加了链表结构。数据结构为数组 单链表 红黑树 双链表图中的标号是结点插入的顺序 在这里插入图片描述 1. 类的继承关系
public class LinkedHashMapK,V extends HashMapK,V implements MapK,V
LinkedHashMap继承了HashMap所以HashMap的一些方法或者属性也会被继承同时也实现了Map结构HashMap原理分析
2. 类的属性相比HashMap新增由于继承HashMap所以HashMap中的非private方法和字段都可以在LinkedHashMap直接中访问
// 链表头结点
transient LinkedHashMap.EntryK,V head;// 链表尾结点
transient LinkedHashMap.EntryK,V tail;// 访问顺序可以指定accessOrder的值从而控制访问顺序
final boolean accessOrder;
二、ArrayList
在这里插入图片描述 1 每个ArrayList实例都有一个容量该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素其容量也自动增长。自动增长会带来数据向新数组的重新拷贝因此如果可预知数据量的多少可在构造ArrayList时指定其容量。在添加大量元素前应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量这可以减少递增式再分配的数量2 transient Object[] elementData底层的数据结构就是数组数组元素类型为Object类型即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的3ArrayList提供了三种方式的构造器可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表这些元素按照该collection的迭代器返回它们的顺序排列的4java 1.7之前ArrayList默认大小为10但是1.8之后默认是空只有当add第一个元素时才设置值默认值为105ArrayList扩容时正常情况下会扩容1.5倍newCapacity oldCapacity (oldCapacity 1特殊情况下新扩展数组大小已经达到了最大值则只取最大值6indexOf是从头开始查找与指定元素相等的元素注意是可以查找null元素的意味着ArrayList中可以存放null元素的。与此函数对应的lastIndexOf表示从尾部开始查找7remove函数用户移除指定下标的元素此时会把指定下标到数组末尾的元素向前移动一个单位并且会把数组最后一个元素设置为null这样是为了方便之后将整个数组不被使用时会被GC可以作为小的技巧使用
三、LinkedList
LinkedList底层使用的双向链表结构有一个头结点和一个尾结点双向链表意味着我们可以从头开始正向遍历或者是从尾开始逆向遍历并且可以针对头部和尾部进行相应的操作 在这里插入图片描述 1. 内部类内部类Node就是实际的结点用于存放实际元素的地方
private static class NodeE {E item; // 数据域NodeE next; // 后继NodeE prev; // 前驱// 构造函数赋值前驱后继Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
2. 类的属性
LinkedList的属性非常简单一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意头结点、尾结点都有transient关键字修饰这也意味着在序列化时该域是不会序列化的
3. 注意点
1add函数用于向LinkedList中添加一个元素并且添加到链表尾部
2在调用remove移除结点时会调用到unlink函数将指定的结点从链表中断开
3LinkedList可以作为双端队列使用这也是队列结构在Java中一种实现当需要使用队列结构时可以考虑LinkedList
四、HashSet和LinkedHashSet
1. HashSet底层是基于HashMap实现的LinkedHashSet基于LinkedHashMap实现所以HashSet、LinkedHashSet数据结构就是HashMap或者LinkedHashMap的数据结构
2. HashSet中由于只包含键不包含值由于在底层具体实现时使用的HashMap或者是LinkedHashMap(可以指定构造函数来确定使用哪种结构)我们知道HashMap是键值对存储所以为了适应HashMap存储HashSet增加了一个PRESENT类域类所有所有的键都有同一个值PRESENT
3. add、contains、remove函数都是基于HashMap或者LinkedHashMap做的操作
4. LinkedHashSet继承自HashSet也实现了一些接口LinkedHashSet会调用HashSet的父类构造函数让其底层实现为LinkedHashMap这样就很好的实现了LinkedHashSet所需要的功能
一、ArrayList 和 LinkedList
1、区别
1ArrayList是基于动态数组的数据结构查询快增删慢线程不安全。
LinkedList是基于链表的数据结构查询慢增删快。线程不安全。
2对ArrayList和LinkedList而言在列表末尾增加一个元素所花的开销都是固定的。
3对ArrayList而言主要开销是在内部数组中增加一项指向所添加的元素偶尔可能会导致对数组重新进行分配而对LinkedList而言这个开销是统一的分配一个内部Entry对象。 4在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动而在LinkedList的中间插入或删除一个元素的开销是固定的。 5LinkedList不支持高效的随机元素访问。 6ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
2、ArrayList和LinkedList的时间复杂度
1ArrayList 是线性表 get() 直接读取第几个下标复杂度 O(1) add(E) 添加元素直接在后面添加复杂度O1 add(index, E) 添加元素在第几个元素后面插入后面的元素需要向后移动复杂度On remove删除元素后面的元素需要逐个移动复杂度O(n)。 2LinkedList 是链表的操作 get() 获取第几个元素依次遍历复杂度O(n) add(E) 添加到末尾复杂度O(1) add(index, E) 添加第几个元素后需要先查找到第几个元素直接指针指向操作复杂度O(n) remove删除元素直接指针指向操作复杂度O(1)。
3、ArrayList为什么是线程不安全的
1在 Items[Size] 的位置存放此元素 2增大 Size 的值 ①在单线程运行的情况下如果 Size 0添加一个元素后此元素在位置 0而且 Size1 ②而如果是在多线程情况下比如有两个线程线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素因为此时 Size 仍然等于 0 注意哦我们假设的是添加一个元素是要两个步骤哦而线程A仅仅完成了步骤1所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行都增加 Size 的值。 那好现在我们来看看 ArrayList 的情况元素实际上只有一个存放在位置 0而 Size 却等于 2。这就是“线程不安全”了。
4、ArrayList能否无限添加元素会抛异常吗
使用ArrayList时可以无限的往里添加元素因为它底层是由数组实现的使用无参构造方法时系统会默认提供默认参数10而使用有参构造函数时我们会指定大小当我们添加的元素个数大于数组的初始化长度时ArrayList会自动为其扩容扩容后的大小是int newCapacity (oldCapacity * 3)/2 1; 自动增加原来的50%
HashMap介绍
1HashMap是基于Map接口的非同步实现结构可以看成数组链表。
HashMap 是一个散列表它存储的内容是键值对映射每一个键值对也叫做EntryEntry的组成Key、value、nextkey和value都可以为null。HashMap中的映射不是有序的。
2HashMap 的实现不是同步的这意味着它不是线程安全的后执行的线程会覆盖先执行线程的修改在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。
Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类这个类实现了Map接口在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步。
3HashMap 的实例有两个参数影响其性能“初始容量” 和 “加载因子”。 容量是哈希表中桶的数量初始容量只是哈希表在创建时的容量容量必须是2的N次幂这是为了提高计算机的执行效率。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时则要对该哈希表进行 resize 操作即重建内部数据结构从而哈希表将具有大约两倍的桶数。创建新表将旧表映射到新表中 通常默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销但同时也增加了查询成本。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子以便最大限度地减少 resize 操作次数。如果初始容量大于最大条目数除以加载因子则不会发生 resize 操作。
4JDK8中HashMap的新特性:如果某个桶中的链表记录过大的话当前是TREEIFY_THRESHOLD 8就会把这个链动态变成红黑二叉树使查询最差复杂度由O(N)变成了O(logN)。
3、一些有关HashMap的问题
1HashMap的get()、put()方法的工作原理 我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时它调用键对象的hashCode()方法来计算hashcode让后找到bucket位置来储存Entry对象。当获取对象时通过键对象的equals()方法找到正确的键值对然后返回值对象。
2为什么String, Interger这样的wrapper类适合作为HashMap键 因为String是不可变的也是final的而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的因为为了要计算hashCode()就要防止键值改变如果键值在放入时和获取时返回不同的hashcode的话那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话那么碰撞的几率就会小些这样就能提高HashMap的性能。 正确答案: C
我是歌谣有什么不合理之处欢迎指出。喜欢敲代码偶尔刷刷题。
阅读目录置顶)(长期更新计算机领域知识
阅读目录置顶)(长期更新计算机领域知识
阅读目录置顶)(长期科技领域知识
歌谣带你看java面试题
