Ruoke Zhang

不那么功利地学习

0%

发表于： 分类于：

异常

Throwable

Alt text Throwable具有 Exception和 Error 两个子类

Error 类代表严重错误，往往不建议我们在程序中用 catch捕获的，我们只能通过优化代码来优化 Error。当出现 Error 时，JVM 一般会选择终止线程。

发表于： 分类于：

Collection接口

collection

List

ArrayList

基本内容

  1. 可以允许null值
  2. 内存是连续的，节省内存空间。
  3. 插入时间复杂度：插在队头O(n)因为要把后面的元素都往后移动一位；插在队尾，如果不需要扩容，则是 O（1），如果需要扩容则先需要 O(n)把原来的 ArryList复制一遍，再执行O（1）的插入操作。 插在队中间，O(n).
  4. 删除时间复杂度：与插入的时间复杂度相对应。
  5. 并非线程安全。

底层实现

  1. 由动态数组实现，随机访问某个节点，只需要计算它的地址值，因此随机访问O(1). 实现了RandomAccess这一个标识借口。
  2. 如果没有指定初始容量，那么默认初始容量为0，第一次添加元素时，容量变成10. 每次动态扩容，容量变成原来的1.5倍。

ArrayList与 Array 的区别

  1. ArrayList可以动态扩容；Array则不行，它的长度是固定的，并且需要在初始化数组的时候就指定长度
  2. ArrayList支持泛型
  3. ArrayList只支持对象，对于基本数据类型则需要使用它们的包装类如Integer, Double。Array支持基本数据类型和对象。

LinkedList

底层实现

  1. 双向链表实现。在头部/尾部进行插入/删除的时间复杂度均为O(1)
  2. 不支持随机访问。每次访问指定元素的时间复杂度为O(n)
  3. 性能不如ArrayList, 在实际开发中基本不会用到。
  4. 线程不安全。
  5. 允许null值
  6. 除了数据之外还要存指针，所以占用空间比LinkedList大。

HashMap

实现原理

  1. 哈希表+链表/红黑树实现。解决哈希冲突的方法有 chaining/probing，一般使用chaining.
  2. 哈希值如何计算？拿到key的hashcode()。将原 hashcode和hashcode右移16位的值进行异或运算。
1

int hash = (key == null) ? 0 : (key.hashCode()) ^ ((key.hashCode()) >>> 16);
  1. 计算数组下标。hash&(length-1)，相当于hash%length. 二进制运算比取模运算更快。
  2. 如果遇到碰撞，就在链表或红黑树中找是否存在该key，如果存在则直接替换值，如果不存在，就加到里面去。链表长度为 8，并且哈希表长度大于64时，升级成红黑树。
  3. 红黑树节点数少于6时，变回链表。
  4. 初始容量16，负载因子0.75，扩容至原来的两倍。
  5. 并非线程安全。扩容的时候可能会造成链表成环。

时间复杂度

理想情况下，HashMap 的插入、删除和查找操作平均时间复杂度都是 O (1)。
如果转成红黑树，操作的时间复杂度会稳定在 O (log n)

发表于： 分类于：

Process

进程独有的：

  1. PC
  2. stack pointer(存储返回地址)
  3. address space
  4. file descriptors

想要去 manipulate一个 process，我们必须交给内核态去做这件事，也就是在用户程序中调用 syscall。对于每个syscall，我们都必须检查它的 return value，如果为-1，则说明出错了。

发表于： 分类于：

参考：小林 coding
参考视频

AOF

Append Ony File，是一个文本文件，因此较大。 当客户端发起一个写请求时，Redis 主线程首先在内存中执行写操作，接着将这个写命令同步到磁盘中的 AOF 日志中。

发表于： 分类于：

参考的技术博客
OSTEP slides
参考

虚拟内存

虚拟化：每个进程都认为，自己有自己的地址空间，多个进程的地址空间是分开的。 地址空间

实际上，CPU 拿到这些虚拟的地址，会让它内部的 MMU 把虚拟地址翻译成物理地址，也就是内存中的地址。内存里，每个地址可以存放一个字节。

发表于： 分类于：

参考视频

内存溢出的原因

  1. 一次性申请太多对象->分页查询
  2. 内存泄漏：可达但不再使用的对象仍然占用内存->找到并释放这些对象
  3. 本身资源不够->jmap -heap [process id]查看堆信息

jmap是一个JDK命令行工具，用来生成heap dump。heap dump叫做堆转储快照，是一个binary file，记录了堆里面所有对象的信息。
或者，添加JVM参数-XX:+HeapDumpOnOutOfMemoryError，当程序发生OOM时，JVM会自动生成heap dump。

发表于： 分类于：

参考：小林 coding

事务的特性

atomicity: undo log

consistency: 由其他三个特性实现.事务在执行前后，数据库从一个一致性状态转变到另一个一致性状态。

isolation: MVCC/lock.一个事物的执行不影响其它事务的执行

发表于： 分类于：

聚簇索引、二级索引

聚簇索引

InnoDB中，每个表都有一个聚簇索引，它决定着数据在磁盘上存储的物理顺序。

  1. 如果有 primary key, 即为聚簇索引
  2. 如果没有 primary key, 选择一个唯一的非空索引作为聚簇索引
  3. 如果还是没有，InnoDB隐式地创建一个自增列作为聚簇索引

B+ Tree

InnoDB在默认情况下，聚簇索引和二级索引都使用 B+ Tree存储。

发表于： 分类于：

参考：JavaGuide

ThreadLocal

Thread类里面有一个变量threadLocals，可以视为一个 HashMap，用来存放线程私有的内容。

1
2
3

/* ThreadLocal values pertaining to this thread. This map is maintained
    * by the ThreadLocal class. */
ThreadLocal.ThreadLocalMap threadLocals = null;

ThreadLocal类里面有一个instance 方法 set,实际上是把内容存在threadLocals里面。key是该ThreadLocal对象自己。

发表于： 分类于：

31. Next Permutation

考虑最后一个permutation：5-4-3-2-1，全部降序。

  1. 从后往前，找第一组升序的nums[i]和nums[i+1], 比如12947653，找到了nums[4]=4.
  2. 从后往前，找第一个比nums[i]大的数nums[j]，也就是 5
  3. 交换nums[i]和nums[j], 得到 12957643，此时nums[i]后面的数字全都是降序排列
  4. 把nums[i]后面的数字按升序排列，得到 12953467

128. Longest Consecutive Sequence

[100,4,200,1,3,2]