java基础应用题



Java 集合基础知识

• Java 集合基础知识

• ArrayList
• LinkedList
• HashMap

• 如何计算bucket下标

• map的几种遍历方法
• 方式1：Iterator迭代器
• 方式2：最常见的使用方式，可同时得到key、value值
• 方式3：使用foreach方式（JDK1.8才有）
• 方式4：通过key的set集合遍历

• JDK8中的HashMap底层实现

• 1. 快速失败和安全失败是什么

Java 集合基础知识

参考链接。

ArrayList

• ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入元素，底层通过数组实现。
• 每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。
• 当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。
• size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
• 为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

LinkedList

LinkedList同时实现了list接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。

LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过和引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候和都指向

HashMap

part1：特殊key值处理，key为null；

part2：计算table中目标bucket的下标；

part3：指定目标bucket，遍历Entry结点链表，若找到key相同的Entry结点，则做替换；

part4：若未找到目标Entry结点，则新增一个Entry结点。

****方法是有返回值的，场景区分如下：

• 场景1：若执行put操作前，key已经存在，那么在执行put操作时，会使用本次的新value值来覆盖前一次的旧value值，返回的就是旧value值；
• 场景2：若key不存在，则返回null值。

特殊key值，指的就是key为null。 先说结论：
a) HashMap中，是允许key、value都为null的，且key为null只存一份，多次存储会将旧value值覆盖；
b) key为null的存储位置，都统一放在下标为0的bucket，即：table[0]的位置；

扩容

a) 扩容后大小是扩容前的2倍；

b) 数据搬迁，从旧table迁到扩容后的新table。 为避免碰撞过多，先决策是否需要对每个Entry链表结点重新hash，然后根据hash值计算得到bucket下标，然后使用头插法做结点迁移。

如何计算bucket下标

1. hash值的计算

首先得有key的hash值，就是一个整数，int类型，其计算方式使用了一种可尽量减少碰撞的算式（高位运算），具体计算流程如上代码

问题1：为什么不直接采用经过hashCode（）处理的哈希码作为存储数组table的下标位置？

结论：容易出现 哈希码 与 数组大小范围不匹配的情况，即 计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置，所以为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：哈希码 与运算（&） （数组长度-1）

问题二、为什么采用 哈希码 与运算(&) （数组长度-1） 计算数组下标？

根据HashMapjava基础应用题的容量大小（数组长度），按需取 哈希码一定数量的低位 作为存储的数组下标位置，从而 解决 “哈希码与数组大小范围不匹配” 的问题。

问题3：为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

结论：加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突

2. 取模运算

计算相当简洁：将table的容量与hash值做“与”运算，得到哈希table的bucket下标。

在文档开头，给出了HashMap类中的各个域变量。其中，哈希table的初始大小默认设置为16，为2的次幂数。后面在扩容时，都是以2的倍数来扩容。为什么非要将哈希table的大小控制为2的次幂数？

原因1：降低发生碰撞的概率，使散列更均匀。根据key的hash值计算bucket的下标位置时，使用“与”运算公式：h & (length-1)，当哈希表长度为2的次幂时，等同于使用表长度对hash值取模（不信大家可以自己演算一下），散列更均匀；
原因2：表的长度为2的次幂，那么(length-1)的二进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能为1，也可能为0，换句话说，取模的结果既有偶数，又有奇数。设想若(length-1)为偶数，那么“与”运算后的值只能是0，奇数下标的bucket就永远散列不到，会浪费一半的空间。
原因3： 提高运算效率

map的几种遍历方法

方式1：Iterator迭代器

逐个获取哈希table中的每个bucket中的每个Entry结点，后面会详细介绍。

方式2：最常见的使用方式，可同时得到key、value值

这种方式是一个语法糖，我们可通过反编译命令javap，或通过IDE来查下编译之后的语句：

其底层还是使用的是Iterator功能。

方式3：使用foreach方式（JDK1.8才有）

这是一种Lambda表达式。foreach也是一个语法糖，其内部是使用了方式二的处理方式，Map的foreach方法实现如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dMLBCTiF-1595994935387)(https://raw.githubusercontent.com/zhaozhen197/my_markdown_img/master/1)]

方式4：通过key的set集合遍历

这种也是Iterator的方式，不过是通过Set类的iterator方式。

综合以上，在遍历Map时，从性能方面考虑，若需同时使用key和value，推荐使用方式1或方式2，若单纯只是使用key，推荐使用方式4。任何情况下都不推荐使用方式3，因为会新增二次查询（通过key再一次在Map中查找value）。

JDK8中的HashMap底层实现

ashMap在JDK8中做链表结构做了优化（但仍然线程不安全），在一定条件下将链表转为红黑树，提升查询效率。

1. 快速失败和安全失败是什么

HashMap、ArrayList 这些集合类，这些在 java.util 包的集合类就都是快速失败的；而 java.util.concurrent 包下的类都是安全失败，比如：ConcurrentHashMap。

在使用迭代器对集合对象进行遍历的时候，如果 A 线程正在对集合进行遍历，此时 B 线程对集合进行修改（增加、删除、修改），或者 A 线程在遍历过程中对集合进行修改，都会导致 A 线程抛出 ConcurrentModificationException 异常。

原因是迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

采用安全失败机制的集合容器，在遍历时不是直接在集合内容**问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常

变量**，记录了map新增/删除k-v对，或者内部结构做了调整的次数，其主要作用，是对Map的操作做一致性校验，如果在iterator操作的过程中，map的数值有修改，直接抛出**异常。

HashEntry对象几乎是不可变的(只能改变Value的值)，因为HashEntry中的key、hash和next指针都是final的。这意味着，我们不能把节点添加到链表的中间和尾部，也不能在链表的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变，这个特性可以大大降低处理链表时的复杂性。与此同时，由于HashEntry类的value字段被声明是Volatile的，因此Java的内存模型就可以保证：某个写线程对value字段的写入马上就可以被后续的某个读线程看到。此外，由于在ConcurrentHashMap中不允许用null作为键和值，所以当读线程读到某个HashEntry的value为null时，便知道产生了冲突 —— 发生了重排序现象，此时便会加锁重新读入这个value值。这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问 ConcurrentHashMap。总的来说，ConcurrentHashMap读操作不需要加锁的奥秘在于以下三点：

用HashEntery对象的不变性来降低读操作对加锁的需求；

用Volatile变量协调读写线程间的内存可见性；

若读时发生指令重排序现象，则加锁重读；

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/26020.html