• 什么是大小端
  • 大端模式
  • 小端模式
• 为什么有大小端之分
• Java中的大小端
• Byte转换工具
  • byte转换工具，用到大小端模式

什么是大小端

大端模式

高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中，这样的存储模式有点儿类似于把数据当作字符串顺序处理：地址由小向大增加，而数据从高位往低位放。

小端模式

高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中，这种存储模式将地址的高低和数据位权有效地结合起来，高地址部分权值高，低地址部分权值低，和我们的逻辑方法一致。

• 基础知识
  • &(与)
    • 例子1
    • 例子2
  • |(或)
    • 例子1
    • 例子2
  • ^(异或)
    • 例子1
    • 例子2
  • ~(非)
    • 例子1
• 位置交换

基础知识

&(与)

与运算符用符号&表示，其使用规律如下：两个操作数中位都为1，结果才为1，否则结果为0。

例子1

1
2
3

int a=129;
int b=128;
System.out.println("a&b的结果是："+(a&b));

1

a&b的结果是：128

“a”的值是129，转换成二进制就是：10000001。
“b”的值是128，转换成二进制就是：10000000。
根据与运算符的运算规律，只有两个位都是1，结果才是1，可以知道结果就是10000000，即128。

• QPS是什么
• QPS如何统计
• 根据QPS推算PV
• 根据QPS,PV推算服务器数量
  • 峰值QPS和机器计算公式
    • 峰值时间每秒请求数(QPS)
    • 峰值机器数量
  • 例子
• 最佳线程数
  • 为什么要找最佳线程数
  • 最佳线程数的获取
  • 影响最佳线程数的主要因素
    • IO
    • CPU
• QPS和线程数的关系

QPS是什么

单个进程每秒请求服务器的成功次数
QPS = req/sec = 请求数/秒

QPS如何统计

QPS统计方式 [一般使用 http_load 进行统计]
QPS = 总请求数 / ( 进程总数 * 请求时间 )

• 用法
• 例子
  • 例1
  • 例2
  • 例3
  • 例4
  • 例5
  • 例6
  • 例7

用法

$\sum_i^n{k}$
i表示下界，n表示上界， k从i开始取数，一直取到n，全部加起来。
$\sum{i}$这样表达也可以，表示对i求和，i是变数。

• 直接寻址
• 散列表
  • 链接法
  • 开放寻址法
• 散列函数的设计
  • 散列函数的需求
  • 常见的散列函数
    • 除法散列函数
    • 乘法散列函数

转帖:散列表

直接寻址

使用散列的目的是能够快速取得某个元素，那么如果能够保证每个元素都存在一个“槽”的话（类似于数组），就能够完成在O(1)的时间内完成取元素的工作。如果一个集合的元素都是取自全域U={1, 2, ... m}，那么通过使用数组T[1,...m]来保证每个元素都存在与之对应的”槽“。

Thread#run方法是不抛出任何检查型异常(Checked Exception)，但是它自身却可能因为一个异常而被终止，导致这个线程的终结。
最麻烦的是，在线程中抛出的异常即使在主线程中使用try...catch也无法截获，因此可能导致一些问题出现，比如异常的时候无法回收一些系统资源，或者没有关闭当前的连接等等。
主线程之所以不处理子线程抛出的RuntimeException，是因为线程是异步的，子线程没结束，主线程可能已经结束了。
UncaughtExceptionHandler名字意味着处理未捕获的异常。更明确的说，它处理未捕获的运行时异常。

• 基础
  • 算法
  • 使用场景
• 字节码解析
  • 字节码分析
  • 字节分类意义
• 源码解析
  • ObjectOutputStream
  • ObjectInputStream

基础

序列化：将数据结构或对象转换成二进制串的过程。
反序列化：将在序列化过程中所生成的二进制串转换成数据结构或者对象的过程。
调用writeObject()序列化一个对象，是将其写入磁盘，以后在程序再次调用readObject()时，根据wirteObject()磁盘的文件重新恢复那个对象。
Externalizable接口扩展Serializable，并增添两个方法：writeExternal()和readExternal()。在序列化和重新装配的过程中，会自动调用这两个方法。
Externalizable是Serializable接口的子类，有时不希望序列化那么多，可以使用这个接口，这个接口的writeExternal()和readExternal()可以指定序列化哪些属性。

算法

算法一般会按步骤做如下事情：

1. 将对象实例相关的类元数据输出。
2. 递归地输出类的超类描述直到不再有超类。
3. 类元数据完以后，开始从最顶层的超类开始输出对象实例的实际数据值。
4. 从上至下递归输出实例的数据。

• 跳表介绍
  • 跳表核心思想
• 存储模式
  • 性质
  • 结构设计
• 操作
  • 搜索
  • 插入
    • K取值
    • 高度
    • 空间复杂度
  • 删除
• 代码
  • Java
  • C++
    • 初始化
    • 插入
    • 删除

跳表介绍

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。
跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB都有用到它，它的效率和红黑树以及AVL树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
这是跳表的作者，上面介绍的William Pugh给出的解释。

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

跳表核心思想

从该有序表中搜索元素“23,43,59”，需要比较的次数分别为<2, 4, 6>，总共比较的次数为2 + 4 + 6 = 12次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，把一些节点提取出来，作为索引。得到如下结构。

把“14,34,50,72”提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构。

如果是说链表是排序的，并且节点中还存储指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。

• 算法
• Java

算法

中缀表达式转后缀表达式的方法：

1. 遇到操作数：直接输出（添加到后缀表达式中）
2. 栈为空时，遇到运算符，直接入栈
3. 遇到左括号：将其入栈
4. 遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5. 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素【栈内的栈顶运算符>=遇到的运算符，就弹出】，然后将该运算符入栈
6. 最终将栈中的元素依次出栈，输出。

实现中缀表达式转换为后缀表达式主要包含三个类，一个主函数，一个自定义栈的类，还有一个就是核心类，实现其转换。

• 概念
  • 时间复杂度
  • 空间复杂度
• 示例
  • 时间复杂度
    • $n^3$
    • O(n)：
    • O(1)：
    • O($log_{2}n$)：
    • O($n^2$)
    • O($nlog_{2}n$)
  • 时间复杂度
    • O(1)

概念

时间复杂度

是度量算法执行的时间长短，时间复杂度是指他运行时计算的次数。
一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))
随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，$log_{2}n$，n，$nlog_{2}n$，n的平方，n的三次方，2的n次方），找出后，f(n) = 该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n) = O(f(n)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O($n^2$)，立方阶O($n^3$),…，k次方阶O($n^k$)，指数阶O($2^n$)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

是度量算法所需存储空间的大小，空间复杂度是指运行完一个程序所需内存的大小。在算法中所谓的空间复杂度为O(1)并不是说只使用一个空间，而是说在待处理的数据量变化的情况下使用的空间量是不变的。空间复杂度一般算的是辅助空间的大小，如果这个辅助空间的大小不随元素N变化那么就是O(1)。
例如：冒泡排序，需要的辅助空间是一个作交换用的临时变量，而且无论任何情况下都只要这一个，所以空间复杂度就是O(1)。但桶排序就不同了，本身需要M个桶，桶的数量是人为决定的，然后需要N个结点，去装原本的N个元素，所以空间复杂度就是O(M+N)。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分。
固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示：S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

示例

时间复杂度

$n^3$

1
2
3
4
5
6
7
8
9

for(i=1; i<=n; ++i)
{
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次
    }
}

则有T(n) = n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定n的三次方为T(n)的同数量级，则有f(n) = n的三次方，然后根据T(n)/f(n)求极限可得到常数c，则该算法的时间复杂度：T(n) = O($n^3$) 。注：$n^3$即是n的3次方。

O(n)：

1
2
3
4

int x = 1;//时间复杂度为O(1)  
for(int i=0; i<n; i++) {  
    System.out.println(i);  
}//时间复杂度为O(n)

O(1)：

1

int x = 1;

O($log_{2}n$)：

1
2
3
4

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    count++;  
}

O($n^2$)

1
2
3
4
5
6

int n = 8, count = 0;;  
for(int i=1; i<=n; i++) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}

O($nlog_{2}n$)

1
2
3
4
5
6

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}

时间复杂度

O(1)

一个临时变量temp，所以空间复杂度为O(1)

1
2
3
4

int x=1, y=2;  
int temp = x;  
x = y;  
y = temp;