二分图(二部图)判别和最大匹配问题(匈牙利算法)

二分图(二部图)

如何判断一个图是否是二分图,二分图就是可以将图分为两个部分,边都是在两个部分之间,而每个部分内部不可以有边相连。

这样如果二部图中存在一个环,那么这个环中的边数必须是偶数,可以画图验证一下三角形、四边形和五边形就知道了。

那么环中的边数是偶数,就可以利用染色算法来进行判别,环是偶数则两种颜色可以交替,否则必定有两个相邻的节点颜色相同。

可以利用BFS算法(结合队列)对二分图进行判别。关键代码如下:

输入:

7
1 4
1 5
1 6
2 5
3 5
3 6
3 4
2 6
 public static void main(String[] args) throws Exception{
       
        Scanner sc = new Scanner(System.in);
        //读入数据,并构建邻接表
        int n = sc.nextInt();
        int [] colors = new int[n];
        HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(i, new ArrayList<>());
        }
        while (sc.hasNext()) {
            int forward = sc.nextInt();
            int backward = sc.nextInt();
            hm.get(forward).add(backward);
            hm.get(backward).add(forward);
        }
        System.out.println(hm);
        //这里节点的标识与数组的下表一一对应,也是为了简化问题,如果不是一一对应的情况,可能还需要做一次 index -> node 的转换

        for (int i = 0; i < n; i++) {
            int color = colors[i];
            if (color == 0) {
                boolean valid = BFS(hm, colors, i);
                if (!valid) {
                    System.out.println("not valid");
                    System.out.println(Arrays.toString(colors));
                    return;
                }
            }
        }
        System.out.println("valid!");
        System.out.println(Arrays.toString(colors));
    }

    public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
        LinkedList<Integer> queue = new LinkedList<>();
        colors[node] = 1;
        queue.offerLast(node);
        while(queue.size() != 0) {
            int curNode = queue.pollFirst();
            for (int neighber : hm.get(curNode)) {
                if (colors[neighber] == 0) {
                    colors[neighber] = - colors[curNode];
                    queue.offerLast(neighber);
                } else if (colors[neighber] == colors[curNode]){
                    return false;
                }
            }
        }
        return true;
    }

二分图中一个很重要的问题就是最大匹配问题,最大匹配问题利用匈牙利算法进行求解。

输入:

8
1 1
1 2
2 2
2 3
3 1
3 2
4 3
4 4

关键代码如下:

    static int maxn = 100;
    //通过邻接矩阵进行图构建
    static int [][] matrix = new int[maxn][maxn];
    static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过,每轮都初始化
    static int [] nxt = new int[maxn];  //表示整个过程中与女生匹配的男生id ,nxt[1]=2, 表示女1和男2匹配
    static int n = 5;  //表示男生数量为4(数值多1是为了和输入的id从1开始相匹配)
    static int m = 5;  //表示女生数量为4
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //构建邻接矩阵
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            matrix[a][b] = 1;
        }
        
        //开始遍历每个男生,尝试为每个男生匹配女生
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //每轮都要初始化女生是否匹配数组,因为dfs(递归)找增广路的时候需要标识来调整策略
            used = new boolean[m];
            if (DFS(i)) res ++;
        }
        System.out.println(res);
    }
    
    //这个方法是匈牙利算法的核心,函数标识在当前情况下,是否(返回值)能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
    public static boolean DFS(int x) {
        //遍历每个女生看看能不能和男生x匹配上
        for (int i = 1; i <= m; i++) {
            // 如果该女生和男生x存在可匹配的边,并且女生在这一轮没有匹配过
            if (matrix[x][i] == 1 && !used[i]) {
                //标识此轮中该女生被从尝试匹配过,防止递归找增广路的时候重复访问(增广路不是环,因此不能重复访问)
                
                used[i] = true;
                //如果这次循环没有找到,会对其他轮次的循环造成影响吗,因为你修改了used数组
                //不会,因为如果存在一条增广路,经过了上次不成立的增广路,那么上次的也是一条增广路,产生矛盾。

                //如果当前女生没有匹配的男生 || 当前女生有匹配的男生,并且可以让那个匹配的男生去找一个新的女生
                if (nxt[i] == 0 || DFS(nxt[i])) {

                    nxt[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

单单看代码注释还是很难理解,可能过一阵子就忘了,结合代码单个步骤调试会更加形象,后面有空整一个视频讲解吧。

参考文献

私钥、公钥、数字签名、数字证书

一些概念:公钥 与 私钥 、摘要、数字签名、数字证书

利用一个公认的证书颁发机构记录信息发布者的公钥信息(防止公钥被伪造),同时这个信息用这个公信机构的私钥进行加密,信息发布者就在自己的签名(摘要+私钥加密)的基础上额外附带自己的数据证书。

接收方收到数据后,如果认可证书管理机构,就用改管理机构的公钥将数字证书解密,得到信息发布者的公钥,进一步通过改公钥解密数字签名获得摘要,最后通过摘要验证收到的信息是否一致。

公钥私钥的两种应用场景

  • 加密,那肯定是不希望别人知道发送给我的消息,所以只有我才能解密,所以可得出别人用公钥负责加密自己用私钥负责解密
  • 签名,那肯定是不希望有人冒充我发送消息,只有我才能发布这个签名,所以可得出自己用私钥负责签名,别人用公钥负责验证是我发送的消息

私钥和公钥是一对,谁都可以加解密,只是谁加密谁解密是看情景来用的:
第一种情景是签名,使用私钥加密,公钥解密,用于让所有公钥所有者验证私钥所有者的身份并且用来防止私钥所有者发布的内容被篡改(摘要用私钥加密,公钥持有者解密后可以验证摘要一致性).但是不能来保证内容不被他人获得(公钥大家都有)。
第二种情景是加密,用公钥加密,私钥解密,用于向公钥所有者发布信息,这个信息可能被他人篡改(中间截获信息进行修改),但是无法被他人获得(无法获取明文)。

https://blog.csdn.net/qq_23167527/article/details/80614454

https://blog.csdn.net/mengzuchao/article/details/78682060

字节抖音客户端提前批一面20200712

设计模式有了解那些?

写单例模式的代码

Java的四种引用类型

进程和线程的区别

volitile关键字是什么意思

进程中的sleep/wait/join/yeild方法分别有什么作用

Android有了解吗?安卓上的MVC、M什么的有了解吗?

一个ArrayList<String str> 里面删除所有特定的字符串要怎么做

编程题:

求两个单链表的交叉点

常见排序算法的稳定性分析

稳定性简而言之就是带相同元素在排序前和排序后的相对位置是否保持一致。

默认从小到大的进行排序

1.冒泡排序

思想:每一轮都是将最大的一个元素冒到数组的结尾。

分析:当相邻的两个元素相等的时候,通常的做法应该是选择后面的那个相同元素继续做冒泡的比较,这样稳定性就不会被破坏。但是如果你在两个相邻元素相同的时,还是选择了交换两个相同的元素,这样稳定性就会遭到破坏,当然没有人会这么多此一举,所以通常默认情况下,因此冒泡排序就是一个稳定的排序算法。

2.选择排序

思想:每一轮选择最小的值所在的下边,确定之后交换到特定位置

分析:举个反例 5,4,5,3 排序,第一轮之后 3,4,5,5 。两个5的相对位置发生了变化,因此选择排序不稳定

3.插入排序

思想:维护数组前部分有序,当前元素插入到合适的位置。

分析:如果再向前找的过程中发现相同元素,则插再这个相同元素的后面,这样相同元素的相对位置不发生变化,是一种稳定的排序算法。但是如果你找到相同元素的时候,硬是要插入到前面,那么就是不稳定了,这里的稳定是默认你不会做这么无聊的操作了。

4.快速排序

思想:主元+分治

分析:举一个反例:3,2,2 第一轮3作为主元,变成 2,2,3 ,这样就可以认为排好序了。两个2的相对位置发生了变化,一种不稳定的排序算法。

5.归并排序

思想:分治与归并

分析:元素的交换只发生的归并的阶段,就是merge两个有序的小数组的过程。归并的过程中需要借助辅助数组。两个有序数组中,小的数排前面,当遇到相同的数的时候,则左边数组的数先排,这样就可以保持相对位置。因此是一种稳定的算法。如果你非要先排右边数组的元素,那么就破坏了稳定性,当然也是需要考虑到你不会这么做。

其他排序算法:

桶排序(基数、计数):稳定

堆、希尔:不稳定

上述提到的稳定算法基本上都是理想上可以达到的,当程序员的实现上不严谨的时候,会导致稳定的排序算法变成一种不稳定的排序算法。

工程中的排序算法

工程中类库提供的排序都是经过高度集成与优化的,时间复杂度O(NlogN)的算法都涉及到递归的操作,工程中是不允许出现递归,递归排序都被改写成了非递归的。

Java中的Arrays.sort方法会先判断数据的长度,如果数据在一定范围内,会直接使用插入排序,因为插入排序虽然是一个时间复杂为O(N²)的排序算法,但是如果数据量并不是很大,那么相对来讲很快,并且插入排序的特点就是如果一个数据近似有序,那么时间复杂度也近似O(N)。如果数据量较大,那么Arrays.sort方法会再判断排序的data是基础类型还是一个自己定义的对象,如果是基础类型,那么会使用快排,因为基础类型要保持稳定性是无意义的,如果是对象例如自己定义的类Student,那么就会使用归并排序,保证data的稳定性。无论是归并排序还是快速排序,当数据量被分解到一定范围时,会再次转换为插入排序 。

参考文献:

https://blog.csdn.net/wumenglu1018/article/details/106712801

https://www.jianshu.com/p/a5b5b5c4ee0f

C++ 复习 STL库

参照传智播客的黑马的教程 https://www.bilibili.com/video/BV1et411b73Z/?p=2

Standard Template Library(标准模板库)

STL从广义上分为:容器、算法和迭代器 (container、algorithm、iterator)

容器之vector

三种遍历方法

#include<vector>
vector<int> v;
v.push_back(10);
vector<int>::iterator itBegin = v.begin(); //第一个元素的地址(指针)
vector<int>::iterator itEnd = v.end();    //最后一个元素的下一个元素的地址(指针)
while (itBegin != itEnd) {
    cont << * itBegin << endl;
    itBegin++;
}

for (vector<int> ::iterator it = v.begin(); it != v.end(); it++){
    cout<<*it<<endl;
}
#include <algorithm> //标准算法头文件
void myPring(int val){ cout<<val<<endl;}
for_each(v.begin(), v.end(), myPrint); //这里采用了回调函数的技术

自定义类型的容器

vector<Person> v;
for(vector<Person>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*it).name << endl;
}
vecter<Person*>v;
for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*(*it)).name << endl;
    cout << (*it)->name <<endl;
}

容器可以嵌套

vector<vector<int>> v;
for (vector<vector<int>>::iterator outerIt = v.begin(); outerIt != v.end(); outerIt ++) {
    for (vector<int> ::iterator innerIt = (*outerIt).begin(); innerIt != (*outerIt).end(); innerIt ++ ) {
        cout << *innerIt << " ";
    }
    cout<<endl;
}

string类,底层就是通过char*来实现的(字符串的字面量实际上时const char * 类型的)

string的四种构造函数

  • string()
  • string (const char * c)
  • string(const & string str)
  • string(int n, char a)

string类内部重载=赋值运算符,还重载了多个,还有提供了assign以及重载的多个方法。

string类内部还重载+=等拼接字符串的方法,还提供了append一些列重载函数。

string类的查找函数find,rfind,一个从左往右找,一个从右边往左边查,并且重载了一系列。

string类的替换函数replace,详细函数的定义需要查查文档。

字符串比较 int compare(const & str)

字符串重载[]实现字符的读写,也提供了at函数提供访问。(这和java不同)下面两种都是合法的。

  • str[1] = ‘a’;
  • str.at(1) = ‘b’;

字符串插入删除 insert() erase()方法

字符串的字串 subStr()

vector

是一个动态的数组,有以下四种方式的构造函数

  • vector()
  • vector(v.begin(), v.end())
  • vector(int n, element)
  • vector(const vector & v)

vector容器可以赋值(重载了operator=),也可以调用assign方法

vector的size() capacity() empty() resize()方法

vector的插入和删除

push_back() pop_back() insert() erase()

vector元素存储 重载[]运算符,调用at(), front() 第一个元素,back()最后一个元素

vector容器的swap()方法

看得懂这个代码吗 vector<int>(v).swap(v)

调用拷贝构造函数创建匿名对象并实现vector的内容交换,一定程度上会节省v中capacity多余的空间浪费,而匿名对象会被系统回收。

reserve()函数,预留空间,减少动态扩容是的复制数据的开销。

deque容器

双端队列 #include<deque>

头部插入的效率高于vector,具体需要数据结构看底层源码

vector访问元素的速度会比deque快

API基本和vector类似,只是多了一些在头部的方法

deque没有capacity()方法,和底层实现有关(中控器)

//deque容器的排序
#include <algorithm>
sort(d.begin(), d.end())

stack容器

#include<stack>

stack<T> stk; stack<T>(const & stack stk); 普通构造和拷贝构造

pop push top 三个方法

size empty 方法

queue容器

#include<queue>

queue<T> que; queue<T>(const & queue que);

pop push front back 方法

size empty 方法

list容器

list表示链表(注意和java中的区别),c++底层实现是双向循环列表

多数的API和vector差不多,但是没有capacity的概念,不支持[] 和at访问,l.begin() 只能++或者– 不能 +=1 +=2 之类的(不支持随机访问)

反转和排序 list<int> l; l.reverse(); l.sort()

所有不支持随机访问迭代器的容器,不可以使用标准算法,(#include <algorithm>),一般来说这种容器的内部会提供对应的成员方法。

bool compare(int v1, int v2){ return v1 > v2; }
l.sort(compare);   //降序排序

自定义数据类型排序需要指定排序规则。

set/multiset

#include<set>

底层是用二叉树来实现的数据结构,是一种关联式容器

set不允许重复元素,multiset允许重复元素

插入元素只能用insert函数,删除erase,清空clear

find函数返回的是迭代器,count函数非1即0(multiset可能是其他值)

    set<int> s;
    pair<set<int>::iterator, bool> res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }
    res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }

set 的函数返回的结果是pair<iterator, bool> 第二个参数表示是否插入成功。

pair队组

两种创建队组的方式

  • pair<string, int> p(“Amy”, 17);
  • pair<string, int> p2 = make_pair(“Jerry”, 30);

cout << p.first << ” ” << p.second << endl;

set的排序(仿函数)

class MyCompare {
    public:
        bool operator()(int a, int  b) const{
            return a > b;
        }
};

int main() {
    cout << 'a' << endl;
    set<int, MyCompare> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    for (set<int, MyCompare>::iterator iter = s.begin(); iter != s.end(); iter ++) {
        cout << *iter << endl;
    }

}

自定义数据类型装入set中必须在创建set的时候,指定仿函数比较器,或者在自定义类中重载比较运算符。

Map容器

#include <map> //一种关联式容器

map里面存的都是队组pair

int main() {
    map<int, int> m;
    m.insert(pair<int, int>(10,10));
    m.insert(make_pair(30,10));
    m.insert(pair<int, int>(20,10));
    for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " " << iter->second <<endl;
    }
}

empty size swap erase(重载多个) clear

查找元素

map<int, int>::iterator iter pos = m.find(key);

函数对象(仿函数)

特点

  • 函数对象在使用时,像普通函数一样调用
  • 函数对象超出普通函数的概念,可以有自己的状态
  • 函数对象可以作为参数传递

谓词

仿函数返回值是bool数据类型,称为谓词。(有些类似java中的函数式接口或者python中的filter)

一元谓词(有一个形式参数)–过滤

二元谓词(有两个形式参数) –排序

内建函数对象

算术仿函数

#include <functional>
negate<int>n; //一元
cout<<n(50)<<endl;
plus<int> q;  //二元
cout<<q(10,5)<<endl;

关系仿函数(greater 最常用)

#include<vector>
#include<functional>
vector<int>v;
sort(v.begin(), v.end(), greater<int>());  //关键在这里
for(vector<int>::iterator it = v.begin(); it != v.end(); it ++) {
     cout << (*it) << endl;
}

逻辑仿函数(基本用不到)

STL常用算法

  • #include<algorithm>
  • #include <numeric>
  • #include <functional>

遍历

for_each(v.begin(), v.end(), 函数或者仿函数);

搬运、转换(类似java8的stream或者python的列表表达式)

trandform(s.begin(), s.end(), d.begin(), 函数或者仿函数); //目标容器需要提前开辟空间

查找:

find (v.begin(), v.end(), int val); //自定义类型需要重写运算符==方法。

find_if(v.begin(), v.end(), 仿函数); //

adjacent_find 查找重复相邻元素的地址

binary_search(v.begin(), v.end(), int val);

count(v.begin(), v.end(), int val);

count_if(v.begin(), v.end(), 一元谓词);

排序

sort(v.begin(), v.end(), 二元谓词);

random_shuffle(v.begin(), v.end());//记得加随机数种子

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); //target需要先开辟,v1,v2需要有序

reverse(v1.begin(), v2.begin());

拷贝和替换

copy(v1.begin(), v1.end(), target.begin()); //先开辟空间

replace(v1.begin(), v2.end(), int old, int new);

replace_if(v.begin(), v.end(), 一元谓词, int new);

swap(v1,v2);//同种类型的容器才能交换

算术生成算法

#include <numeric>
int total = accumulate(v.begin(), v.end(), int start_sum);
fill(v.begin(), v.end(), 100);

“集合”算法

set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟,前提必须是两个有序的序列

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序

set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序 ,差集有先后顺序关系

JAVA复习:GC垃圾收集器

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

垃圾是什么?指运行程序中没有任何指针指向的对象

不清理垃圾有什么后果?垃圾对象占用内存空间,容易内存溢出。

内存溢出和内存泄露的区别,

  • 内存溢出很容易来理解, 内存不够用,是指在程序申请内存时,没有足够的内存提供就出现了内存溢出
  • 内存泄漏 但是程序在申请内存后,无法释放已申请的内存空间 如java的数据库连接或者网络连接没有及时close。
  • 当内存泄露越来越多的时候,最终会导致内存溢出

JAVA 的垃圾回收机制

自动内存管理,(分配和回收)开发人员就不同过多关注内存的分配和释放,降低了内存的泄露和溢出。

java堆是垃圾回收的重点。青年区->老年区->永久代 回收频率依次减少

垃圾回收的算法

垃圾标记阶段:引用计数算法和可达性分析算法

引用计数器算法,每个对象保存一个整形的应用计数器,记录对象自身被引用的次数。

优点:实现简单,垃圾对象容易识别,判定效率高,回收没有延迟

缺点:额外的空间,更新计数器额外的时间开销。无法处理循环引用的情况(内存泄露,致命的缺点,因此java没有采用)

可达性分析/根搜索/追踪性垃圾收集算法

对象的finalization机制

对象要被gc回收之前会执行finalize方法,定义在Object类中的方法。可以在里面重写一些资源释放的方法。

但是不要主动去调用这个方法。

对象的三种状态

清除阶段的三种算法:

  • 标记-清除算法
  • 复制算法
  • 标记-压缩算法

标记-清除算法

标记从Gc roots开始遍历,标记所有可达到的对象(在对象的Header中记录为可达对象)

对堆中所有对象进行遍历,清除没有标记的对象。

缺点:效率不高,在进行GC的时候,需要停止整个应用程序,影响用户体验(Stop the world),容易产生内存碎片。需要维护一个空闲列表。

清空就是将对象的地址记录到空闲列表上。

复制算法:

优点:没有标志和消除过程,高效,不会产生碎片问题

缺点:需要两倍内存空间,需要维护对象之间的引用关系,如果大部分对象都不是垃圾,移动对象的时间开销也会很大

标记-压缩(标记-整理)算法

复制算法高效性的前提是垃圾对象多,存活对象少。而这很符合年轻代中数据的特点。但是老年代就不一样了,老年代的数据大部分是存活数据。

优点:没有内存碎片,不需要维护空闲列表,比复制算法空间利用率高

缺点:效率低,要维护对象间的引用,需要STW,影响用户体验

对比

分代收集算法:具体问题具体分析

青年代用复制算法,同时设置伊甸园区和幸存者区缓解内存的浪费。

老年代用标记-清除和标记-整理混合的方法。

增量收集算法:

缺点:造成垃圾回收总体成本提高,系统吞吐量下降。因为切换线程和上下文转换有额外开销。

分区算法:

一些概念:

System.gc() /Runtime.getRuntion().gc(),可能触发Full GC,对老年代和青年代进行回收。但是无法保证立刻调用垃圾收集器,会在程序执行的某个不确定时间节点进行调用。

System.runFinalization(); 会强制调用失去引用对象的finalize方法。

内存溢出 OOM:没有空闲空间,并且垃圾回收之后还是不够。

内存泄露 Memory Leak:对象不会再被程序使用了,但是GC又无法回收了。通常是编码过程的疏忽,导致某些对象的生命周期过长。

内存泄露的两个例子。

STW stop the world 所有的垃圾收集器都会有这个情况。就是把所有用户进程停止,执行垃圾回收。

并发(concurrent)实际上就是同步,某个时刻只有一个程序在执行,只是CPU快速地切换,让我们感觉同时在执行。

并行(Parallel) 同一个时刻,多个程序在真正运行。

  • 垃圾回收的并行:多条垃圾回收线程并行执行。
  • 垃圾回收的串行:只有一个垃圾回收器线程执行。
  • 垃圾回收器的并发:用户线程和垃圾回收线程同时执行。

安全点:

安全区域:

引用(前提都是可达的对象引用)

强引用对象不会被gc回收,也是内存泄露的主要原因。

软引用,内存足够不会回收,内存不够时,在二次gc时被回收。

弱引用:被gc就回收

JDK更新可以从三个层面区关注:

  • 语法层面
  • API层面
  • 底层优化

垃圾回收器的分类:

  • 按线程数分:串行gc和并行gc
  • 按照工作模式:并发式和独占式
  • 按碎片分:压缩式和非压缩式
  • 按工作内存:年轻代gc和老年代gc

GC的性能评估指标

上面标红的三项是主要的,但也是互相制约的。

主要关注前两项

吞吐量与暂停时间的矛盾。

可以在JVM参数中设置Parallel GC的吞吐量或者暂停时间的参数。

JAVA中的数组、链表、队列、栈

首先说一下Java中的集合框架collection是一个接口,、

下面有两大类型的子接口,分别是List和Deque

List下有三大常见的实现类,ArrayList、LinkedList、Vector

其中 ArrayList、Vector 底层都是用数组来实现的, LinkedList底层是用链表实现的

ArrayList非线程安全,Vecotr虽然是线程安全的但是已经被弃用了。

Stack类是早期JAVA为了栈数据结构而设计的一个类,它是vector的子类,但是早期设计的时候考虑的不是特别的完美,因为父类vector是一个线程安全的,意味着效率比较低,同时Vector的上层接口List里面有一个add(index, Element)的方法,被调用会破坏stack的结构,就是在这栈的中间可以随意的插入元素。因此Stack这个类也被弃用了。

Deque 接口顾名思义就是为了实现队列而提供的接口。双端队列。

下面有很多有用的实现类,ArrayDeque、LinekList、PriorityQueue 里面也封装了很多有用的方法。

LinkedList即使List的实现类又是Deque的实现类(底层是链表)因此可以使用它来作为队列或者栈来进行使用。

虽然LinkedList的功能很强大,但是它也是List的实现类,避免不了被错误调用

破坏了栈只能在栈顶操作数据的原则

操作队列或者栈用的方法主要带有offer poll peek + First/Last,而最好不是用add/remove之类的方法或者push/pop之类的方法,容易搞混乱。

这篇文章讲得很好。

https://mp.weixin.qq.com/s/Ba8jrULf8NJbENK6WGrVWg

复习:深度底层理解Java的String

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

String的两种创建方式:

  • String s = “abc”; //字面量初始化
  • String s = new String(“abc”); //对象的形式初始化

String类是final的,不可继承

JDK8以及以前版本String的底层是用char[]来进行存储的

JDK9以及以后底层改变为了用byte[]数据进行存储

修改底层结构的字符:String在程序中很常用,并且字符中大部分是拉丁文,即用一个字节就能进行存储,而cahr类型是两个字节的,因此会造成内存空间的浪费。

char[]就改变成了byte[]和对应的编码类型

StringBuilder、StringBuffer、JVM底层处理String的方式自JDK9都做了相应的修改。

String代表不可变的字符序列。

字符串常量池中不会存储相同的字符串。

StringPool 实际是一个固定大小的Hashtable,不能动态修改,常量过多的话Hash冲突会增加。大小可以在JVM的参数上进行定制。

常量池就类似java系统级别的一个缓存,可以让运行速度更快、更节省内存。

JDK6 的时候 字符串常量池在永久代的常量池中,JDK7和JDK8之后都在堆中。

为什么调整?

  • 永久代默认空间比较小,容易溢出
  • 永久代的垃圾回收的频率比较低(或者不回收),字符串回收效率低,也容易溢出

进阶知识

String s = “a” + “b” + “c”;

String s = “abc”

这两句在编译之后是等价的,常量字符串拼接(包括final修饰的变量)是在编译时期进行优化的。即在生成的字节码文件里面是两个一样的字面量“abc”

如果字符串的拼接符号的前后出现了变量,相当于在堆中new了一个String对象。

  • String s1 = “ab”;
  • String s2 = “cd”;
  • String s3 = s1 + s2;
  • String s4 = “abcd”;
  • System.out.println(s3 == s4); // false
  • String s3 = s1 + s2;这一句代码查看底层的字节码可以解释为
    • String tmp = new String();
    • tmp.append(s1);
    • tmp.append(s2);
    • s3 = tmp.toString();

以上导致了对象引用和常量池引用的地址不一致问题。

        String s = "";
        for (int i = 0; i < 10000; i++) {
            s = s + i;
        }
        
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            s1.append(i);
        }

上述代码展示的两种字符串拼接方案,效率千差万别

  • append的方式只有一个StringBuilder对象,而字符串拼接的方式每次拼接都会产生一个新的StringBuilder对象以及String对象
  • 其次 ,第一中方式内存中存在过多stringBuilder和String垃圾,如果进行gc需要花费额外的时间。

进一步提高,StringBuilder可以在初始化的时候指定char[]数组的容量,可以避免扩容过程中带来的性能损耗。即如果逻辑大致确定,可以指定一个capacity的上界,就不会扩容了。

intern函数,返回字符串是字符串常量池中的地址(有就直接返回,没有就“创建”,JDK版本有差别)

new String(“ab”); 这条语句会创造几个对象?

一个对象是new 关键字创建的,另一个对象是字符串常量池中的对象。

new String(“a”) + new String(“b); 呢?从字节码的角度看一共有5个对象

  • new StringBuilder()
  • new String()
  • 字符串常量池中的对象“a”
  • new String()
  • 字符串常量池中的对象”b”

StringBuilder的toString方法中 return new String(value, 0, count);分析对应的字节码,得知并没有在常量池中创建“ab”,

字符串常量池的HashTable中放到是什么?现在的理解存到的就是一个完整的String对象的引用,该对象引用和字面量引用是等价的。而new出来的对象是在堆中的。

面试题:

String s1 = new String("1");
s1.intern();
String s2 = "1";
System.out.println(s1 == s2);           //false

String s3 = new String("1") +  new String("1");
s3.intern();
String s4 = "11";
System.out.println(s3 == s4);       //jdk6:false   jdk7/8:ture

第1部分比较简单,就是s1在对空间中创建了一个字符串一的对象,同时字面量一也在字符串常量池里面创建了一个一的对象,而第2句s1.intern();就相当于什么都没做,第3句的S2通过字面量初始化,指向字符串常量池中的那个对象,所以两个地址是不一样。

第2题就比较难,因为它的输出结果和jdk的版本有关,执行intern语句之前,如果字符串常量池中已经有了,就没什么区别。当字符串不存在常量池中的时候,intern方法在1.6中会在永久代中复制一份String对象,并返回相应的地址。而在JDK7/8中,字符串常量池的位置调整到了堆中,调用intern方法的时候如果常量池中没有,则直接指向堆中已有的那个对象,节省空间。

String s = String.valueOf(123);
System.out.println(s == s.intern());    //jdk8 true
String s3 = new String("1") +  new String("1");
String s4 = "11"; 
s3.intern();
System.out.println(s3 == s4);       //jdk7/8:false
String s1 = new String("a") +  new String("b");
String s2 = s1.intern(); 
System.out.println(s1 == "ab");    //jdk6:false   //jdk7/8:true
 System.out.println(s2 == "ab");   //jdk6:true    //jdk7/8:true

在代码中何时的位置加上intern函数可以在一定程度上节省内存空间。因为字符串常量池中的数据可以复用,重复的String对象就可能被gc回收。

复习:Java虚拟机 JVM底层结构

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

类的加载过程

  • 加载
    • 通过一个类的全类名获取该类的字节流
    • 将字节流代表的静态结构转换为方法区的运行时数据结构
    • 在内存中生成一个Class对象,作为这个类的各种数据的访问入口
  • 链接阶段
    • 验证:验证字节流中的信息满足虚拟机要求,如cafebabe头
    • 准备:为类变量分配内存,类的赋值默认初始值(非final的静态变量)
    • 解析:将常量池中的符号引用转换为直接引用的过程
  • 初始化:执行类构造器方法clinit方法(如给静态变量进行显式初始化, 静态代码块执行),子类运行前需要先加载父类的clinit方法,该方法是同步的。

类的加载器

两种类型,引导类加载器(Bootstrap Classloader)和自定义类加载器(拓展类加载器,系统类加载器,用户自定义加载器)

  • 引导类加载器在代码中获取不到,使用c、c++实现的,嵌套在jvm内部,主要加载一些java的核心类库,也会加载拓展类加载器和系统加载器
  • 拓展类加载器加载,父类加载器就是引导类加载器,在ClassLoader继承体系下,加载jre/lib/ext下面的jar包
  • 应用程序类加载器(系统类加载器), 父类加载器就是引导类加载器 , 在ClassLoader继承体系下, 是默认的类加载器,我们在代码中写的类都是这个加载的。

用户自定义类加载器在一些特殊情况下使用

双亲委派机制

  • 如果一个类加载器收到了类加载请求,它并不会自己先去加载,而是把这个请求委托给父类的加载器去执行
  • 如果父类的加载器还存在父类的加载器,则进一步加上委托依次递归请求最终达到顶层的启动类加载器,
  • 如果父类加载器可以完成内加载任务就成功返回,倘若腹内加载器都无法完成此任务,此类加载器才会自己尝试去加载,这就是双亲委派模型

反向委派,核心类库是接口,外部jar包是实现类。

优势:避免类的重复加载,保护程序安全,防止核心的API被修改

沙箱安全机制,就是双亲委派机制对核心源代码的保护,不能再核心类库包名下定义main方法。

运行时数据区

本地方法栈、虚拟机栈、程序计数器、堆区、元数据区(方法区/非堆空间)

线程有自己的程序计数器、虚拟机栈、本地方法栈

多个线程共享堆区和方法区(进程独占,生命周期同JVM)

一个JVM实例对应着一个Runtime类的对象。

程序计数器(PC寄存器)

主要用来存储指向下一条指令的地址,也就是即将执行的指令代码,由执行引擎读取下一条指令

线程私有的,生命周期和线程同步,占用内存很小,不会发生OOM错误而且没有GC。

PC寄存器存储地址有什么用呢?因为CPU会不停的切换各个线程,当切换为某个线程之后,就要知道程序从哪里继续执行。

虚拟机栈

JAVA指令是根据栈来设计的,这样的优点是可以跨平台,指令级比较小,编译器容易实现,但是缺点是和基于寄存器的指令性能实现了一定的下降,同样的功能也需要更多的指令。

栈是运行时单位,堆是存储的单位。

虚拟机栈里面存数的是很多的栈桢 stack frame,每一个栈桢对应着一个方法的 。栈顶的栈桢对应着当前方法。

栈是一种快速有效的分配存储方式;访问速度仅次于PC计数器;操作只有两个 ,入站、出站;栈不存在垃圾回收问题.

StackOverFlowError请求的容量超过了虚拟机占允许的最大容量(无限递归)

OutofmemoryError动态拓展虚拟机内存的时候无法申请到足够的内存

JVM栈可以在启动的时候制定大小。

栈中存什么,栈桢(一个内存区块),栈桢和方法是一一对应的关系

当前栈桢–当前方法–当前类

方法的结束方式有两种,第一种正常结束return;第二种方法中出现未捕获的异常,以抛出异常结束。因此有可能栈顶是异常结束,栈底正常结束,因为栈底处理了异常。

每个栈桢的结构有:局部变量表、操作数栈、动态链接、方法返回地址、一些附加信息

局部变量表是一个数字数组,存方法参数和方法体内的局部变量,包括基本数据类型、引用数据类型和返回值类型。不存在安全问题。局部变量表的大小是在编译时期确定的。

局部变量表中的slot(除了long 和double占用两个slot(32bit 一个 slot),其他类型的数据或者引用占用一个slot);成员方法的局部变量表中的第一个元素是this的引用。slot重复利用,作用域小的销毁后重复利用。

成员变量都有默认初始化的过程,而局部变量没有,所以局部变量必须显式地赋值。

操作数栈主要用于保存计算过程中的中间结果,同时作为计算过程中变量临时的存储空间,

在方法执行过程中,根据字节码指令往栈中写入数据或提取数据即入栈或出栈

说操作数栈实际底层肯定是要用具体的数据结构来实现的,然后可以用数组或者列表,这里用的数组。所以需要指定数组的大小,编译时候确定。

动态链接(指向运行时常量池(这个常量池是字节码文件内部的,最终也会放到常量池中)的方法引用)的作用就是将符号引用转换为调用方法的直接引用

为什么需要常量池?提供一些符号和引用便于指令识别,减小字节码文件的冗余,多个字节码文件可以共用方法区的常量池。

方法调用是怎么样的?方法调用也有静态链接和动态链接对应早期绑定和晚期绑定。就是多态。

Lambda表达式引入入让java这种静态类型语言具有了动态类型语言的一些特性以及底层是用invokeDynamic指令来实现的。用值判断变量的类型,而不是用变量类型来约束值的类型是动态类型语言的关键。

虚方法和非虚方法

虚方法如果每次都需要不断向上层父类找实现类,效率会比较低。为了提高性能,建立虚方法表。虚方法在类加载的链接阶段被创建(具体是在解析的阶段)

方法返回地址 调用者的pc计数器的值作为返回地址,即调用方法之后的下一条指令地址。

方法如果正常退出,则正常返回调用者的方法返回地址,如果是异常退出,调用者则根据异常表来定位接下来执行的位置。

一些附加信息 不重要

一些面试题:

栈溢出的情况:stackOverflowError

调整栈的大小,能保证不一出吗?否

垃圾回收设计JVM栈吗?否

分配栈的内存越大越好吗?否

自定义的局部变量是否线程安全?不一定

如果方法的形参是引用类型的变量或者返回值是引用参数类型,则可能是线程不安全的

本地方法接口和本地方法库—–非运行时区的模块

本地方法:Native Method就是一个Java调用非Java代码的接口。为什么要用本地方法?

  • Java应用需要与Java外界环境交互,效率考量
  • Java需要与操作系统的交互,调用c语言实现的接口

本地方法栈

类似于虚拟机栈的作用,就是管理本地方法的调用,也是线程私有的,内存溢出差不多,有StackOverflow和OutOfMemory,也可以设置栈的内存大小。

一个JVM实例只有一个堆内存,堆也是java内存管理的核心区域。Java堆积在juem启动的时候即被串件,其空间大小也就确定了,是JVM 管理最大的一块内存空间。所有的线程共享堆空间(但是堆中可能有线程的私有缓冲区TLAB)

几乎所有的对象实例和数组都在堆空间中,对象的引用在JVM栈中的某个栈帧的局部变量表中。方法运行结束的时候,堆中的对象不会马上被移除,仅仅在垃圾收集的时候才会被移除。

堆是垃圾回收的重点区域。

现在垃圾收集器大部分都基于分代收集理论设计

  • JDK7以及之前:新生区+养老区+永久区
  • JDK8以及之后:新生区+养老区+元空间
  • 永久区/元空间可以理解为方法区。主要先关注新生区和养老区

堆可以手动设置堆空间的大小,默认是电脑内存的1/64,最大的堆内存大小是电脑内存的1/4。建议初始和最大的设置成一样的。

OOM Error 堆中的对象所占的空间超过了堆的大小,则会导致堆空间的溢出。

年轻代和老年代(二者的内存比例可以分配,默认值是1:2)

年轻代有分为:伊甸园区、幸存者1区和幸存者2区(默认比例是8:1:1,但是需要显式指定)

几乎所有的java对象都是在Edan区创建的,大多数的数据都在青年代被销毁。

  • 创建对象的过程,创建的对象默认放在edan区,当edan区满的时候,触发gc,不是垃圾的全部到to区,from区的也会被gc检查,不是垃圾也到to区。
  • from区和to区的数据会维护一个年龄,每次gc之后年龄+1,超过阈值的时候移动到老年区。
  • from区或者to区满的时候不会触发gc,只有edan区满的时候会,当伊甸园区来的对象to区放不下的时候,可以直接放到老年区。
  • 如果老年区也放不下,在老年区执行一次GC,如果还是放不下就报错OOM。

YGC就是MinorGC,MajorGC是OGC/老年代的GC。

GC线程执行会导致用户进程的暂停,所以GC要尽可能少。

分代的原因就是通过统计数据优化垃圾收集器的性能。因为大部分的对象的生命周期都比较短。

TLAB Thread Local Allocation Buffer

堆是线程共享数据,但是存在线程安全问题,加锁会导致效率的下降,因此未每个线程在伊甸园区分配私有缓存区域。(通常这个空间比较小,为伊甸园区的1%。)

伊甸园区过大,会降低MinorGC的效率,过小会导致MinorGC触发的频率过高,影响用户线程,所以设置要平衡一下。

堆是分配对象存储的唯一选择吗?(”是“)

逃逸分析后,如果未逃逸,则可以将对象优化成被栈上分配。

如果new的对象可以在方法外被进行调用,则发生了逃逸。(就是一个作用域的问题)

  • 栈上分配可以在某种程度上来说,加快代码的执行效率,并减少垃圾回收执行的次数,增强用户线程的体验。
  • 同步消除,如果锁通过逃逸分析,仅仅在当前线程被使用,那么不存在同步安全问题,可以消除同步操作。
  • 标量替换,未逃逸的对象,可以从聚合量的形式被打散成标量(基本数据类型),直接在栈上进行分配就可以了。

但是逃逸分析本身也要消耗性能的,总体的提升是有风险的。该技术还不成熟

方法区

方法区是线程共享的,逻辑上是堆的一部分,但是在大部分JVM在实现过程中是和堆分开的。jdk7 叫做永久带,jdk8叫做元空间。

方法区和永久代不严格等价,在hotspotJVM上是等价的。

元空间的使用的内存是本地内存,永久代用的是虚拟机内存。

方法区主要存类型信息,常量,静态变量和JIT代码缓存

类信息:

  • 类的完整定义如类声明、继承、实现情况、修饰符等
  • 域信息(成员变量):名称、类型、权限修饰符、顺序
  • 方法信息:方法名称、返回值类型、参数个数类型、方法字节码、本地变量表、操作数栈、异常表……

全局变量和全局常量的区别,全局常量在编译阶段就赋值完成了(在字节码文件中有体现),而全局变量在类加载链接阶段的prepare阶段才默认初始化,在第三各初始化阶段才显示初始化。

运行时常量池:字节码文件中有常量池,方法区中有运行时常量池。

常量池包括了各种字面量和对类型、域和方法的符号引用。


为什么要改?

  • 永久代的空间是不好确定,容易产生OOM
  • 对永久代的调优的过程是比较困难的

为什么StringTable要调整?因为永久代回收的效率很低,在full gc 的时候会触发,这导致StringTable回收的效率不高,而日常开发中会有大量的字符串被创建,如果不及时回收,会导致永久代空间不足,放到堆里面,回收会比较即使。

区分好对象本身一直是在堆区的,而对象引用变量(存的对象地址)放的位置不同版本有区别。

方法区的垃圾回收主要是常量池中废弃的常量不再使用的类型

方法区中类的回收条件十分苛刻,费力不讨好。

创建对象的方式

  • new
  • Class.newInstance
  • Constructor.newInstance
  • clone(实现Cloneable接口以及浅复制)
  • 反序列化

创建对象的步骤:Object obj = new Object();

对应的字节码:

Code:
stack=2, locals=2, args_size=1
0: new #2 // class java/lang/Object
3: dup
4: invokespecial #1 // Method java/lang/Object.””:()V
7: astore_1
8: return

  • 判断对象对应的类是否加载、链接、初始化
  • 为对象分配内存,计算占用空间的大小(确定的)
    • 内存规整-指针碰撞(整块空间)
    • 内存不规整-空闲分配列表(碎片化的空间)
  • 处理并发问题
  • 初始化分配到的空间(赋默认初始化值)
  • 设置对象头(所属的类,对象的HashCode,对象的GC信息、锁信息)
  • init方法初始化

对象的内存布局:

  • 对象头Header
    • 运行时元数据:哈希值、GC分代年龄、锁状态等
    • 类型指针:指向类元数据
  • 实例数据:从祖宗到自己的各种类型的字段
  • 对齐填充

对象的访问定位:

  • 句柄访问:效率低(间接访问),需要额外内存维护句柄池,栈中的指针稳定,
  • 直接指针(HotSpot采用的方式):效率高,栈中的指针不稳定,节省内存

直接内存

Java Process Memory = Java heap + native memory (其他空间太小了)

执行引擎

解释器和JIT编译器->java是半编译半解释型语言(与javac编译无关)

解释器:效率比较低,但是响应时间快

为什么非要有字节码?不想C语言、C++一步到位?分层思想可以提高各个部分的效率,不用一步到位的考虑,就想OSI网络分层结构一样,应用层不用直接管物理链路层的东西。虽然分层做出了一定性能上的牺牲。

JIT(Just in time)编译器:响应时间慢,但是执行效率高

Java中的编译器:前端编译器、后段编译器

热点代码以及探测方式

JIT编译后的代码缓存在方法区

默认情况下JVM执行引擎是混合模式,可以通过参数制定只运行特定模式。

JIT编译器分为C1(客户端)和C2(服务端)两种

Java 复习 JDK8 新特性 Lambda 和 Stream

参考自视频:https://www.bilibili.com/video/BV18b411t7Nc/

下面复习JDK8主打的两种新特性 Lambda 和 Stream

Lambda表达式

Lambda在一些动态语言中是一个匿名函数,在java中Lambda本质上是一个接口的实例化对象

格式 (o1, o2) -> Integer.compare(o1,o2)

  • 左边是形参列表(重写抽象方法的形参列表)
  • ->是Lambda操作符
  • 右边是Lambda方法体(重写抽象方法的方法体)

六种调用方式

  • Runnable runnable = () -> {System.out.println(“running”);}
  • Consumer<String> consumer = (String str) -> {System.out.println(str);}
  • Consumer<String> consumer = (str) -> {System.out.println(str);}
  • Consumer<String> consumer = str -> {System.out.println(str);}
  • Comparator<Integer> comparator = (o1, o2) -> return Integer.compare(o1, o2)
  • Comparator<Integer> comparator = (o1, o2) -> Integer.compare(o1, o2)

总结:是参数的类型可以省略,有自动推断机制,如果参数只有一个,那么括号可以省略,你把方法体应该用一对大括号来扩充,但是如果其中呢只有一条语句的话,括号可以省略,如果只有一条语句,并且是return语句,return这个关键词也可以省略。

这些都是建立在实现的接口中只有一个抽象方法(不会有歧义),这种类型的接口叫做函数式接口

函数式接口可以用FunctionalInterface注解进行修饰,类似Override注解的功能,在编译时期进行格式检查。

Lambda表达式一定依赖于函数式接口。

四大函数式接口

方法引用和构造器引用

方法引用本质上就是lambda表达式,只是一种更简便的方法,

使用要求:使用方法引用的前提是已有方法实现了接口抽象方法实现的功能,形参和返回值可以匹配上,有如下三种情况:

对象::非静态方法

Consumer <String> consumer = System.out::println;

Supplier<String> supplier = emp::getName;

类::静态方法

Comparator<Integer> comparator = Integer::compare;

Function<Double, Long> fun = Math::round;

类::实例方法(这种比较难)

BiPredicate<String, String> pre = String::equals;

Comparator<String> comparator = String::compareTo;

Function<Employee, String> func = Employee::getName;

构造器引用

Supplier<Employee> su = Employee::new;(调用空参数构造器)

Function<Integer, Employee> fun = Employee::new; (调用带一个参数integer的构造器)

BiFunction<Interger, String, Emplyee> fun2 = Employee::new;

数组引用(把数组看作一个特殊的类)

Function<Integer, String[]> fun = String[] :: new;

Stream API 真正把函数式编程风格引入到Java中,可以对集合数据进行操作,类似于SQL执行数据库查询。集合是数据在内存中,Stream是计算在CPU中

Stream不会自己存储元素,Stream也不会改变原有对象,Stream的计算是延迟的,

Stream的三个步骤,创建对象、中间操作、终止操作。

创建stream对象的方法

Collection接口中的default方法 stream 和 pararallStream

Arrays类的静态方法 stream

Stream类的静态方法 public static stream of (T…t)

创建无限流

Stream.iterate(0, t->t+2).limit(10).forEach(System.out::println) 输出前10个偶数,从0开始

Stream.generate(Math::random).limit(0).forEach(Sytem.out::println)输出10个随机数

中间操作

筛选和切片

fileter(Predicate p) 自定义筛选数据

limit(n) 截断流,取前n个数据

skip(n) 跳过前n个数据

distinct 筛选 利用流中元素的hashCode和equal方法去除重复元素。

映射

map(function fun)

Stream<String> stream = Arrays.asList("aa","bb","cc").stream();
stream.map(String::toUpperCase).forEach(System.out::println);

flatmap 扁平映射,把Stream套Stream的形式压成一层扁平的Stream

排序 sorted 自然排序和 sorted(Comparator comparator)定制排序

终止操作:

匹配和查找

allMatch anyMatch noneMatch 见面知意,参数一定是Predicate接口

findFirst、findAny、count、max(Comparator com)、min(Comparator com)

forEach(Consumer c) 内部迭代

归约 reduce(T identity, BinaryOperator)

System.out.println(Stream.iterate(1, x -> x + 1).limit(10).reduce(Integer::sum));

收集

collect(Collector c)

stream.collect(Collectors.toList()) stream.collect(Collectors.toSet())

Optional类 是用来避免空指针对程序对伤害。Optional可以理解为是一个容器或者是一个包装类,Optional有两种构造方法,一种是Optional.of(T) 一种是Optional.ofNullable()。为了避免在程序中出现空指针异常,使用orElse(备胎)方法获取Optional容器中的对象,如果是null就返回备胎,保证返回的对象不空。后面JDK9、10、11还会对这个类进行优化,可以暂且不用太关注。