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

引言

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

正文

总览

• 如上图，容器主要分为两类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但是操作更加复杂

总结

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