秋招突击——8、20——知识补充——Java容器

2024-08-20 22:04
文章标签 java 补充 秋招 知识 容器 20 突击

本文主要是介绍秋招突击——8、20——知识补充——Java容器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 引言
    • 正文
      • 总览
        • ArrayList
        • LinkedList
        • Queue & Stack & ArrayDeque
        • PriorityQueue![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/acdc7f306a2e4052bc6bc14a175e67fc.png)
        • HashSet & HashMap
        • LinkedHashSet & LinkedHashMap
        • TreeSet & TreeMap
      • 面试题
        • 计算HashCode，为什么要将hashCode中的高16位和低位按位异或？
        • HashCode中获取桶的位置时？使用什么方法来计算桶的下标？
        • 遍历集合过程中回删除元素吗？怎么处理？
        • HashMap冲突的时候，为什么用红黑树？不用平衡树？
        • 1000亿的数据，无限制内存，插入到HashMap中，怎么快速完全地插入？
        • 为什么在Java中如果要使用一个栈或者队列，为什么优先选择ArrayDeque，而不是LinkedList
    • 总结

引言

  • 之前虽然看过了容器相关的一些知识，但是不够全面，今天完整地过一遍。
  • 资料来源

正文

总览

在这里插入图片描述

  • 如上图，容器主要分为两类Map和Collection，这两个都是接口，下面是具体的实现类，然后重要的主要分为两类

  • Map

    • 最基本：HashMap和LinkedHashMap
    • 具备排序和范围查找的SortedMap=》NavigableMap接口的实现类：TreeMap

  • Collection

    • List
      • LinkedList
      • ArrayList
    • Queue
      • 常规实现类
        • LinkedList
        • PriorityQueue
      • Deque
        • LinkedList
        • ArrayDeque
    • Set
      • 常规实现类：
        • HashSet
        • LinkedHashSet
      • SortedSet
        • NavigableSet
          • 具体实现类，TreeSet

下面将重点讲解其中的几个部门内容

ArrayList

在这里插入图片描述
特点

  • 使用动态数组实现，自动扩容1.5倍
  • 非线程安全类，与之类似的vector是线程安全的

注意

  • 为了避免在使用中因为扩容，增加时间开销，需要提前估计数据容量,创建ArrayList给初始值
    • 或者提前手动扩容ensureCapacity
  • 不是C++中的vector，使用add添加元素和插入元素，没有push_back和insert

常见的方法

  • set（index，element）：修改特定索引位置的方法
  • get（index）：获取特定索引位置的方法
  • remove（index）\（element）：删除特定索引位置或者删除第一个满足要求元素
  • indexOf：返回元素第一次出现的位置
LinkedList

底层：双向链表
在这里插入图片描述
特点

  • 实现了List接口、Queue接口和Deque接口
  • 非线程安全的，需要使用Collections.synchronizedList进行包装

常规方法
Queue方法

  • 查看队首元素peek
  • 弹出队首元素poll
  • 元素入队offer

Deque方法

  • 添加元素offer
    • offerLast
    • offerFirst
  • 删除元素poll
    • pollFirst
    • pollLast
  • 查看元素peek
    • peekFirst
    • peekLast

模拟Stack

  • 添加元素push
  • 删除元素pop

注意

  • 有的时候需要操作一个特殊的队列，又能中间删除，又能模拟队列的结构，可以声明LinkedList对象
Queue & Stack & ArrayDeque

关于Queue和Stack

  • Java中实现Queue功能和Stack功能，推荐使用ArrayDeque，然后再是LinkedList

ArrayDeque

在这里插入图片描述

特点

  • 底层使用循环数组实现，不允许存放null元素
  • 非线程安全的，需要实现同步机制实现
  • 容量肯定是2的倍数

考点

  • 1、下表越界判定
    • head = (head - 1) & (elements.length - 1)
    • 这段代码实现取余操作
  • 2、扩容方式
    • 空间问题是插入之后解决的，tail和head都是指向下一个可插入的位置
    • head和tail相等的时候，进行扩容，直接扩容两倍
    • 先左后右
PriorityQueue在这里插入图片描述

特点

  • 保证每次取出的队列是最小的或者是最大的
  • 底层使用通过完全二叉树实现的小顶堆实现，实际上还是使用数组实现的
  • 添加元素和删除元素的时间复杂度都是logN

添加元素的过程

  • 添加元素要重新调整树的结构，默认是添加在数组的尾部
  • 自下而上进行调整，不断和父节点进行比较，不满足条件进行交换
    在这里插入图片描述

删除元素

  • 默认是弹出数组的首元素，然后将数组的最后一个元素重新放置到队首，重新进行调整
  • 调整方式
    • 从k指定的位置开始，将x逐层向下与当前节点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任意一个位置

在这里插入图片描述

HashSet & HashMap

HashMap和HashSet实现是相同的，都是基于HashMap，HashSet采用的是适配器模式实现的
在这里插入图片描述
特点

  • 非线程安全的，需要使用同步机制实现线程安全的
  • 不保证元素顺序，会对元素进行重排，TreeSet保证顺序
  • 使用红黑树和拉链法解决Hash冲突

扩容相关

  • 决定因素：初始容量Capacity 和 负载系数load factor
  • entry数量超过 capacity * loadFactor的时候，会进行扩容的
  • 对于插入元素较多的场景，需要初始化一个合适的容量，防止扩容

equals和hashcode的关联

  • 通过hashcode决定当前记录属于那个桶 bucket
  • 逐个比价equals决定，是否为目标记录

查找元素的基本流程

  • 计算索引坐标的方式
    • hash(k)&(table.length-1)等价于hash(k)%table.length，使用按位与的操作，来提高运行速度
      • table.length-1二进制的高位全部是0，低位全部是1，通过按位与的方式，实现取余数的操作
        在这里插入图片描述

插入元素的基本操作

  • 首先会做一次基本的查找，如果查找到该元素，就直接返回
  • 如果没有查到该元素，插入新的Entry
    在这里插入图片描述

Java8的HashMap结构

在这里插入图片描述

  • 针对hash冲突，采用拉链法和红黑树进行处理，记住采用尾插法

    • 如果元素数量超过了8，将链表转为红黑树，node转为treenode
    • 如果元素数量小于8，采用链表解决hash冲突的问题

  • 特点

    • 扩容每次都是两倍，所以容量肯定是2的倍数
    • 获取数据过程
      • 首先，判定当前key的hash值，根据hash值和容量 - 1 的按位与，找到数组对应的下标
      • 判断数组所处的位置是否有多个元素，是否是我们需要找的元素
        • 存在多个元素，先查看是不是treeNode结构，红黑树需要查找
        • 不是红黑树，需要对链表进行遍历查找
LinkedHashSet & LinkedHashMap

LinkedHashSet里面是对LinkedHashMap的一个适配器
在这里插入图片描述

特点

  • 在HashMap的基础上，采用双向链表的形式，将所有entry连接起来，保证元素的迭代顺序和插入顺序相同。
    • 迭代顺序和插入顺序相同
TreeSet & TreeMap
  • TreeSet同样的也是TreeMap的套壳
    在这里插入图片描述

TreeMap
特点

  • 底层通过红黑树实现，时间复杂度是logN
  • 非线程安全的，需要通过同步器包裹Collections.synchronizedSortedMap(new TreeMap)

红黑树的定义

  • 每一个节点要么是红色，要么是黑色
  • 根节点必须是黑色
  • 红色节点不能连续，父亲节点和孩子节点不能同时是红色
  • 对于每一个节点，从该点到null的任何路径，都含有相同个数的黑色节点
    • 每一次插入和删除操作都需要重新调整二叉树才行。

面试题

计算HashCode，为什么要将hashCode中的高16位和低位按位异或？
  • 混合高低位，增加随机性
    • 将高位和低位进行异或时，能够更好地混合二进制表示中的位，使得散列之后的值更加随机化
    • 有助于哈希表中均匀分布哈希值，避免不同的键因为高位相同发生哈希冲突
  • 降低低位的影响
    • 因为并没有完全用到计算出来的哈希吗，仅仅是使用了某些低位，通过高低位异或混合，将高位的影响传递到低位
  • 减少相似的哈希码
    在这里插入图片描述
HashCode中获取桶的位置时？使用什么方法来计算桶的下标？
  • 用与的操作来替换取模操作，提高运算速度。使用HashCode来计算桶的下标
    在这里插入图片描述
遍历集合过程中回删除元素吗？怎么处理？
  • 使用迭代器遍历的时候，删除元素，会报错
  • 必须要使用遍历器自带的remove方法可以
HashMap冲突的时候，为什么用红黑树？不用平衡树？
  • 解决了普通树的退化问题
  • 不需要频繁调整对应进行调整
1000亿的数据，无限制内存，插入到HashMap中，怎么快速完全地插入？
  • 核心
    • 要解决put方法插入慢的关键点
  • 预支内存，提前估计内存大概多大，然后提前分配内存，然后避免不断扩容。
  • 任务做一个划分，四个线程分别负责不同的块进行桶的操作
为什么在Java中如果要使用一个栈或者队列，为什么优先选择ArrayDeque，而不是LinkedList
  • 内存开销：
    • ArrayDeque的内存开销较小，仅仅保存数据和额外扩容的空间
    • LinkedList需要保存额外的两个指针，来增加内存消耗
  • 内存布局和局部性
    • ArrayDeque是一个动态扩展的数据，元素是连续存在的，遍历和访问元素，能够更好地利用CPU缓存
    • LinkedList内存不连续，缓存命中率低，然后性能较差
  • 时间复杂度
    • 添加元素的话，ArrayDeque是O（1），虽然LinkedList但是操作更加复杂

总结

  • 又算是草草结束了，想着明天腾讯三面了，我得去看看场景题，感觉很多时候，都会考场景题！
  • 这个算是有了一个大概的了解，而且很多细节也做了深究，但是始终感觉不够全面！

这篇关于秋招突击——8、20——知识补充——Java容器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1091295。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
sqlite3 相关知识

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式（Rollback Journal）定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能；支持多读者和单写者。支持安全的事务回滚，但并发性较低。性能写入性能更好，尤其是读多写少的场景。写操作会造成较大的性能开销，尤其是在事务开始时。写入流程数据首先写入 WAL 文件，然后才从 WAL 刷新到主数据库。数据在开始
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟 开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚 第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2