数据结构

作者: f377 | 来源:发表于2020-12-03 11:34 被阅读0次

IOS开发_数据结构
py基础
思维导图之数据结构+算法
数据结构与算法分析：大纲]
数据结构：数组
数据结构—概述
OVS 源码分析整理
01. 数据结构与算法绪论
数据结构与算法 - 查找
C#之数据结构（上）

HashMap的原理，内部数据结构？
- 底层使用哈希表（数组 + 链表），当链表过长会将链表转成红黑树以实现 O(logn) 时间复杂度内查找
讲一下 HashMap 中 put 方法过程？
1. 对 Key 求 Hash 值，然后再计算下标。
2. 如果没有碰撞，直接放入桶中，
3. 如果碰撞了，以链表的方式链接到后面，
4. 如果链表长度超过阀值（TREEIFY_THRESHOLD == 8），就把链表转成红黑树。
5. 如果节点已经存在就替换旧值
6. 如果桶满了（容量 * 加载因子），就需要 resize。
HashMap 中 hash 函数怎么是是实现的？还有哪些 hash 的实现方式？
1. 高 16bit 不变，低 16bit 和高 16bit 做了一个异或
2. （n - 1） & hash --> 得到下标
3. 还有哪些 Hash 实现方式：可以参考之前的博客 Effective Java 学习笔记 -- hashCode()
HashMap 怎样解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是什么定位到在这个值新数组中的位置，
- 将新节点加到链表后，
- 容量扩充为原来的两倍，然后对每个节点重新计算哈希值。
- 这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为 <原下标+原容量> 的位置。
抛开 HashMap，hash 冲突有那些解决办法？
- 开放定址，链地址法
针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
- 将链表转为红黑树， JDK1.8 已经实现了。
数组和 ArrayList 的区别；
1. 数组可以包含基本类型和对象类型，ArrayList 只能包含对象类型
2. 数组大小固定，ArrayList 大小可以动态变化
3. ArrayList 提供了更多的特性（addAll、removeAll）。
Arraylist 如何实现排序
- Collections.sort(List<T> list);
- sort(List<T> list, Comparator<? super T> c);
HashMap
1. 数组 + 链表方式存储
2. 默认容量： 16(2^n 为宜,若定义的初始容量不是 2^n，容量会定义为大于该初始容量的最小 2^n)
  - 例如：初始容量为 13，则真正的容量是 16.
3. put:
  1. 索引计算 : ((key.hashCode() ^ (key.hashCode() >>> 16)) & (table.length - 1))
  2. 在链表中查找，并记录链表长度，若链表长度达到了 TREEIFY_THRESHOLD(8)，则将该链转成红黑树。
  3. 若在链表中找到了，则替换旧值，若未找到则继续
  4. 当总元素个数超过容量*加载因子时，扩容为原来 2 倍并重新散列
    - (元素的下标要么不变，要么变为【原下标+原容量】)。
  5. 将新元素加到链表尾部
  6. 线程不安全
HashTable
1. 数组 + 链表方式存储
2. 默认容量： 11(质数为宜)
3. put:
  1. 索引计算 : （key.hashCode() & 0x7FFFFFFF）% table.length
  2. 若在链表中找到了，则替换旧值，若未找到则继续
  3. 当总元素个数超过容量*加载因子时，扩容为原来 2 倍并重新散列。
  4. 将新元素加到链表头部
4. 对修改 Hashtable 内部共享数据的方法添加了 synchronized，保证线程安全。
HashMap ，HashTable 区别
1. 默认容量不同。
2. 索引计算方式不同。
3. HashMap 特有的将过长链表转换为红黑树。
4. 新元素的位置不同。
5. 线程安全性
HashMap、ConcurrentHashMap 区别。
1. 索引计算消除了最高位的影响
2. 默认容量： 16(若定义了初始容量(c)，容量会定义为大于(c + (c >>> 1) +1) 的最小 2^n)
  - 例如：初始容量为 13，则真正的容量是 32.
3. 线程安全，并发性能较好
  - 并发性能好的原因是 ConcurrentHashMap 并不是定义 synchronized 方法，而是在链表头上同步，不同的链表之间是互不影响的。
ConcurrentHashMap 原理
1. 最大特点是引入了 CAS（借助 Unsafe 来实现【native code】）
  1. CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
  2. Unsafe 借助 CPU 指令 cmpxchg 来实现
  3. 使用实例：
    1. 对 sizeCtl 的控制都是用 CAS 来实现的
    1. sizeCtl ：默认为0，用来控制 table 的初始化和扩容操作。
      
      -1 代表table正在初始化
      
      N 表示有 -N-1 个线程正在进行扩容操作
      
      如果table未初始化，表示table需要初始化的大小。
      
      如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。
  4. CAS 会出现的问题：ABA
    - 对变量增加一个版本号，每次修改，版本号加 1，比较的时候比较版本号。
TreeMap 和 TreeSet 区别和实现原理
- TreeSet 底层是 TreeMap，TreeMap 是基于红黑树来实现的。
如果想实现一个线程安全的队列，可以怎么实现？
知道 LRU 吗，20分钟基于 HashMap 实现一个 LRU 算法，面试官给个地址，进去写代码，面试官远程看
- 如何设计实现一个LRU Cache？
二叉树的遍历方式，前序、中序、后序和层序
- 可以再写一篇了。。
常见的排序算法时间复杂度（排序算法实现也要重点掌握）
- 常见排序算法实现(Java)
红黑树的特点及相比平衡二叉树的优点（先介绍各自特点）？
- 红黑树
  1. 每个节点要么是红色，要么是黑色。
  2. 根节点永远是黑色的。
  3. 所有的叶节点都是空节点（即 null），并且是黑色的。
  4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
- 平衡二叉树
  1. 任何节点的两个儿子子树的高度最大差别为一
- 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
B+树的了解
- 多分支结构有效降低了树的高度
- B 树的各种操作能使 B 树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率
Trie-Tree 原理及其应用；
- 字典树
- 特点
  1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符互不相同。
- 核心思想是空间换时间
- 应用
  1. 字符串检索
  2. 词频统计

boolean 占几个字节
1. 如果 boolean 变量在栈上，那么它占用一个栈单元（32-bits）
2. 如果在堆上，那么就跟 JVM 的实现有关了
3. 在 Oracle 的 JVM 实现，boolean[] 中每个元素占用一个字节（8-bits）
Java 访问修饰符权限的区别；
- public 所有类都可访问
- protected 只允许包内、子类访问。
- 默认 只允许包内访问
- private 只允许类内访问
String 是否可以继承， “+” 怎样实现?
- String 是 final 类，不可继承。
- + 是通过 StringBuilder（或 StringBuffer）类，和 append 方法实现
String，StringBuffer，StringBuilder，区别，项目中那里用到了 StringBuffer 或者 StringBuilder
- String 不可变
- StringBuffer，可变，线程安全
- StringBuilder，可变，线程不安全
String为啥不可变，在内存中的具体形态？
- String 使用 final char value[] 来存放字符序列。
Comparable 接口和 Comparator 接口实现比较
- Comparable 是直接在"被比较"的类内部来实现的
- Comparator则是在被比较的类外部实现的
Arrays 静态类如何实现排序的？
- 双轴快排
1. 首先检查数组长度，如果比阀值（286）小，直接使用双轴快排
2. 否则先检查数组中数据的连续性，标记连续升序，反转连续降序，如果连续性好，使用 TimSort 算法（可以很好的利用数列中的原始顺序）
3. 否则使用双轴快排 + 成对插入排序
Java 中异常机制。
- Java 中所有异常都是 Throwable 的子类，他的直接子类有两个，一个是 Error, 一个是 Exception。
  - Error 一般表示 JVM 出现了严重问题，比如说栈溢出或 OOM,
  - Exception 中异常分为两类，
    - 一类是 RuntimeException 表示运行期间出现的错误，比较常见的是空指针异常和数组下标越界，出现这种异常一般是程序出现了逻辑错误，也就是代码有 Bug。
    - 另一类是编译时异常（除了 RuntimeException 以外的异常），常见的一般有 IOException等，出现这种错误程序编译会不通过。
- 还有一种分类方式是 checked exception 和 uncheck exception。unchecked exception 包括 Error 和 RuntimeExcetion，checked exception 指之前所说的编译时异常。
Java 中异常怎么处理，什么时候抛出，什么时候捕获；
- 一般原则是提早抛出，延迟捕获
- 出现异常时，若当前无法处理则抛，否则捕获异常，尝试恢复。