lihuayang / note Goto Github PK
View Code? Open in Web Editor NEW笔记
笔记
先进者先出,这就是典型的 “队列”(Queue)
栈只支持两个基本操作:入栈 push() 和出栈 pop()。队列和栈非常相似,支持的操作也有限,最基本的操作也是两个:入队 enqueue() 放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。所以,队列和栈一样,也是一种操作受限的线性表数据结构。
跟栈一样,可以用是数组实现也可以用链表实现,用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。同样的,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。
// 用数组实现的队列
public class ArrayQueue {
// 数组:items,数组大小:n
private String[] items;
private int n = 0;
// head 表示队头下标,tail 表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为 capacity 的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 如果 tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出队
public String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确,把 -- 操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}
对于栈来说一个栈顶指针就可以了。但是队列需要两个指针:一个是 head 指针,指向队头;一个是 tail 指针,指向队尾。
当 tail 指针移到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。
可以用数据搬移来解决这个问题,每次进行出队操作时都相当于删除数组下标为 0 的数据,要搬移整个队列中的数据,出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。
实际上,在每次出队操作时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触发一次数据搬移操作。借助这个**,出队函数 dequeue()保持不变,修改入队方法 enqueue 的实现:
// 入队操作,将 item 放入队尾
public boolean enqueue(String item) {
// tail == n 表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0,表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新 head 和 tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
省略
主要解决数据搬移问题、省略
当向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?
一种是非阻塞的处理方式,直接拒绝任务请求;另一种是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理。
如何处理排队请求?按照公平性原则,先进者先服务,所以队列这种数据结构很适合来存储排队请求。那么用哪种队列的实现方式来处理呢?数组还是链表?两种实现方式又各有什么不同?
基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以针对响应时间比较铭感的系统,基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池排队的请求超过队列大小时,接下来的请求就会被拒绝没这种方式对于响应时间铭感的系统来说,就相对更加合理。不过设置一个合理的队列大小,也是非常讲究的,过大导致等待请求太多,过小导致无法充分利用系统资源,发挥最大性能。
Java IO 包中还提供了很多关于操作流的对象,如果需要将各种形式的流数据打印,则需要用到打印流。如果输入的数据流有多个,可以使用合并流,合并后统一操作。如果需要将对象流化,则需要用到专门操作对象的流对象,等等场景。
两者都可以直接操作输入流和文件,且都可以指定编码,是否自动刷新。PrintWriter 类常用于 Web 开发。
PrintStream
类除了提供写字节操作以外,还提供了各种打印方法如下,此类打印方法能够将是数据类型完整地打印出去,如 print(int i)
打印的是 4 个字节的数据,而不是 write(int i)
方法,每次都只写出 1 个字节。
void print(boolean b)
void print(char c)
void print(char[] s)
void print(double d)
void print(float f)
void print(int i)
void print(long l)
void print(Object obj)
void print(String s)
其构造方法可接受参数很多如下,且三种构造函数都能指定字符集。默认自带缓冲区,每次写出得刷新才能生效。也可以在构造函数中指定自动刷新。
PrintStream(File file)
PrintStream(OutputStream out)
PrintStream(String fileName)
当输入的数据源有多个时,可以使用 SequenceInputStream
对多个输入流进行合并,方便统一操作
Vector<FileInputStream> v = new Vector<FileInputStream>();
v.add(new FileInputStream("c:\\1.txt"));
v.add(new FileInputStream("c:\\2.txt"));
v.add(new FileInputStream("c:\\3.txt"));
SequenceInputStream sis = new SequenceInputStream(v.elements());
FileOutputStream fos = new FileOutputStream("c:\\4.txt");
byte[] buf = new byte[1024];
int len =0;
while ((len=sis.read(buf))!=-1) {
fos.write(buf,0,len);
}
// .close()
ObjectInputStream 与 ObjectOutputStream
被操作的对象需要实现 Serializable (标记接口)
DataInputStream 与 DataOutputStream
ByteArrayInputStream 与 ByteArrayOutputStream
CharArrayReader 与 CharArrayWrite
StringReader 与 StringWriter
递归(Recursive)是一种非常广泛的算法。包含是递归的是算法和数据结构,DFS 深度优先搜索、前后中序二叉树遍历等等。
递归关键 写出递推公式,找到终止条件,
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
思路:
如果有一级台阶,则只有一种跳法(1);
如果有两级台阶,则有两种跳法:(1,1;2);
如果有三级台阶,则有三种跳法:(1,1,1;1,2;2,1);
如果有四级台阶,则有五种跳法:(1,1,1,1;1,1,2;1,2,1;2,1,1;2,2;)......
依次类推可以发现如下规律:当 n=1,f(n)=1;当 n=2,f(n)=2;当 n>=3,f(n)=f(n-1)+f(n-2)
思路:先举几个例子,找出 f(n) 的规律,再处理一下边界条件
用来写入字符文件的便捷类。此类的构造方法假定默认字符编码和默认字节缓冲区大小都是可接受的。要自己指定这些值,可以先在 FileOutputStream 上构造一个 OutputStreamWriter。
文件是否可用或是否可以被创建取决于底层平台。特别是某些平台一次只允许一个 FileWriter(或其他文件写入对象)打开文件进行写入。在这种情况下,如果所涉及的文件已经打开,则此类中的构造方法将失败。
FileWriter 用于写入字符流。要写入原始字节流,请考虑使用 FileOutputStream。
创建一个 FileWriter,用如下方式,假设文件不存在,则会被创建,若文件存在则会被覆盖。当文件文件位不存在的文件夹或者盘符下,该方法会抛出 FileNotFoundException。
FileWriter writer = new FileWriter("D:\\demo.txt");
若文件不想被覆盖,则使用如下构造方法:指定追加模式为 true。此时当文件存在时,写操作会在文件末尾追加内容。
FileWriter writer = new FileWriter("D:\\demo.txt", true);
基本的使用方法如下,需要注意的是,调用 write 方法之后并不会直接将文本内容写入磁盘,会先在内存中滞留,当调用 flush 方法后,才会将内容刷入磁盘。此处能写入磁盘,是因为在 close 方法中,会先调用一次 flush 方法。 关闭流的操作需要在 finnaly 代码块中,且需要判断对象是否为 null,以免出现 NPE。
FileWriter fw = null;
try {
fw = new FileWriter("D:\\demo.txt");
fw.write("text");
} catch (IOException e) {
e.printStackTrace();
} finally{
if (fw!=null) {
try {
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
若想写入换行符,Windows 下用 "\r\n",Linux 下用 "\n"。使换行具有跨平台性方法很多,这里讲两种,一是使用 BufferWriter 类 newLine() 方法;二是使用 JDK 封装好的换行写入方法,如 PrintWriter 类的 println 方法。
// 法一(省略 flush 操作)
new BufferWriter(new FileWriter("D:\\demo.txt")).newLine();
// 法二(省略 flush 操作)
new PrintWriter("D:\\demo.txt").println("text");
用来读取字符文件的便捷类。此类的构造方法假定默认字符编码和默认字节缓冲区大小都是适当的。要自己指定这些值,可以先在 FileInputStream 上构造一个 InputStreamReader。
FileReader 用于读取字符流。要读取原始字节流,请考虑使用 FileInputStream。
创建一个 FileReader,用如下方式,假设文件不存在,该方法会抛出 FileNotFoundException。
FileReader reader = new FileReader("D:\\demo.txt");
读取一个文件的几种方法,单字符读取,字符数组读取
FileReader reader = new FileReader("D:\\demo.txt");
int c = 0;
while ((c = reader.read()) != -1) {
System.out.println("字符:" + (char) c);
}
FileReader reader = new FileReader("D:\\demo.txt");
char[] buf = new char[1024];
int num = 0;
while ((num = reader.read(buf)) != -1) {
System.out.println("字符:" + new String(buf, 0, num));
}
结合读取文件和写入文件操作,实现简单的文本文件拷贝。
FileReader reader = null;
FileWriter writer = null;
try {
reader = new FileReader("D://demo.txt");
writer = new FileWriter("D://demo_copy.txt");
int length = 0;
char[] buf = new char[1024];
while ((length = reader.read(buf)) != -1) {
writer.write(buf, 0, length);
writer.flush();
}
} catch (Exception e) {
try {
if (reader != null) {
reader.close();
}
if (writer != null) {
writer.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
将文本写入字符输出流,缓冲各个字符,从而提供单个字符、数组和字符串的高效写入。
可以指定缓冲区的大小,或者接受默认的大小。在大多数情况下,默认值就足够大了。
该类提供了 newLine() 方法,它使用平台自己的行分隔符概念,此概念由系统属性 line.separator 定义。并非所有平台都使用新行符 ('\n') > 来终止各行。因此调用此方法来终止每个输出行要优于直接写入新行符。
通常 Writer 将其输出立即发送到底层字符或字节流。除非要求提示输出,否则建议用 BufferedWriter 包装所有其 write() 操作可能开销很高的 Writer(如 FileWriters 和 OutputStreamWriters)。例如,
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("foo.out")))
;
将缓冲 PrintWriter 对文件的输出。如果没有缓冲,则每次调用 print() 方法会导致将字符转换为字节,然后立即写入到文件,而这是极其低效的
使用实例如下:
FileWriter writer = null;
BufferedWriter bfw = null;
try {
writer = new FileWriter("D://demo.txt");
bfw = new BufferedWriter(writer);
bfw.write("text");
bfw.newLine(); // 跨平台换行
} catch (Exception e) {
try {
if (bfw != null) {
bfw.close();
}
// 可以省略
if (writer != null) {
writer.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
从字符输入流中读取文本,缓冲各个字符,从而实现字符、数组和行的高效读取。
可以指定缓冲区的大小,或者可使用默认的大小。大多数情况下,默认值就足够大了。
通常,Reader 所作的每个读取请求都会导致对底层字符或字节流进行相应的读取请求。因此,建议用 BufferedReader 包装所有其 read() 操作可能开销很高的 Reader(如 FileReader 和 InputStreamReader)。例如,
BufferedReader in = new BufferedReader(new FileReader("foo.in"));
将缓冲指定文件的输入。如果没有缓冲,则每次调用 read() 或 readLine() 都会导致从文件中读取字节,并将其转换为字符后返回,而这是极其低效的。
通过用合适的 BufferedReader 替代每个 DataInputStream,可以对将 DataInputStream 用于文字输入的程序进行本地化
注: readLine 方法读取时,只返回换行符之前的内容,不包含文字中的换行符,所以如果需要必须得自己手动添加。
使用实例如下:
FileReader reader = null;
BufferedReader bfr = null;
try {
reader = new FileReader("D://demo.txt");
bfr = new BufferedReader(reader);
String line = "";
while ((line = bfr.readLine()) != null) {
System.out.println(line);
}
} catch (Exception e) {
try {
if (bfr != null) {
bfr.close();
}
// 可以省略
if (reader != null) {
reader.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
结合缓冲读取文件和缓冲写入文件操作,实现简单的文本文件拷贝。
BufferedReader bfr = null;
BufferedWriter bfw = null;
try {
bfr = new BufferedReader(new FileReader("D://demo.txt"));
bfw = new BufferedWriter(new FileWriter("D://demo_copy.txt"));
String line = null;
while ((line = bfr.readLine()) != null) {
bfw.write(line);
bfw.newLine();
bfw.flush();
}
} catch (Exception e) {
try {
if (bfr != null) {
bfr.close();
}
if (bfw != null) {
bfw.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
在 Windows 下换行符为 "\r\n",linux 下换行符为 "\n",两者共同点都是以 "\n" 结尾,可以通过该字符判断是否已经达到行尾,示例代码如下:
class MyBufferReader {
private FileReader r;
public MyBufferReader (FileReader r) {
this.r = r;
}
public String myReadLine() throws IOException {
StringBuilder sb = new StringBuilder();
int res = 0;
while ((res = r.read()) != -1) {
if ('\r' == ((char)res)) {
continue;
}
if ('\n' == ((char)res)) {
return sb.toString();
}
else {
sb.append((char) res);
}
}
// 若是没有 \n,则把之前读进来的全输出
if (sb.length() > 0) {
return sb.toString();
}
return null;
}
// ... 省略 close 方法
}
参考:
传智播客毕向东
并发:多个线程操作相同的资源,保证线程安全,合理使用资源
高并发:服务能同时处理很多请求,提高程序性能
CPU 的频率太快,快到主存跟不上,这样在处理器时钟周期内,CPU 常常要等待主存,浪费资源。所以 cache 的出现,是为了缓解 CPU 和主存之间速度不匹配问题(结构:cpu-> cache -> memory)
缓存的容量远远小于主存,不能包含所有的 CPU 所需要的数据。
用于保证多个 CPU cache 之间缓存共享数据的一致性
处理器为了提高运算速度而做出违背代码原有顺序的优化
单核时代是不会有问题的,但是多核就不一定了
规定了一个线程如何、何时可以看到由其他线程修改过后的共享变量的值。以及在必须时如何同步的访问共享变量。
java 内存模型
硬件内存模型
java 内存模型与硬件内存模型之间的关系
java 内存模型抽象结构图
同步操作图示
用来将文件或者文件夹封装成对象,方便对文件与文件夹的属性信息进行操作,File 对象可以作为参数传递给流的构造函数。
File 类既能封装文件,又能封装文件夹
// 封装文件
File f = new File("C:\\demo.txt");
// 封装文件夹
File f = new File("C:\\demo");
跟 FileOutputStream 不同的是,FileOutputStream 会在流建立时就默认创建并复写文件。而 File 是需要在调用 createNewFile 方法以后才会创建。
两者的共同点是,文件路径中包含有不存在的文件夹时,会抛出 FileNotFoundException。createNewFile 方法在创建成功时,返回 true。文件存在或者其他原因导致失败,则返回 false。
注:创建的是文件,而不是文件夹,所以当 new File("C:\\demo").createNewFile()
运行结果是,创建不带后缀名的 demo 文件,而不是创建了 demo 文件夹
new File("C:\\demo.txt").createNewFile();
如果需要创建文件夹需要调用 mkdir()
| mkdirs()
方法,使用如下:
// 此方法只能创建一级目录
new File("C:\\demo").mkdir();
// 此方法能创建多级目录
new File("C:\\demo\\demo\\demo\\").mkdirs();
删除指定文件,当文件路径中包含有不存在的文件夹,或者所要删除的文件不存在时,返回 false
new File("C:\\demo.txt").delete();
判断文件对象是否是文件或其他时,必须要先判断该文件对象封装的内容是否存在,如果不存在的话,返回都为 false。判断方法得在文件存在时,才会具有意义,如下代码:
File f = new File("C:\\dd\\demo.txt"); // 该文件不存在
f.isFile(); // fasle
f.isDirectory(); // fasle
常用的方法如下:
boolean exists(); // 文件是否存在
boolean isFile(); // 是否是文件
boolean isDirectory(); // 是否是文件夹
boolean isHidden(); // 是否是隐藏文件
boolean isAbsolute(); // 是否是绝对路径
getPath()
该方法返回的是构造函数中指定的路径,若封装的是相对路径则返回相对路径,封装的是绝对路径则返回绝对路径。不同于 getAbsolutePath()
方法,后一个方法返回的永远是绝对路径。
getParent()
该方法返回的是绝对路径中的父目录。如果获取的是相对路径,且含有上层目录,则返回上层目录,否则返回 null。
常用的方法如下:
String getName(); // 获取文件名
long lastModified(); // 获取上次修改时间
long length(); // 获取文件长度
使用 listFiles 方法时,File 对象指向的得是一个文件夹,指向文件时,返回的是 null,如果此时对返回的数组进行迭代,会出现 NPE。
File file = new File("D:\\dir");
File[] files = file.listFiles(new FileFilter() {
@Override
public boolean accept(File f) {
return f.getName().endsWith(".bmp");
}
});
使用递归,碰到文件夹时,继续调用自身,进行打印
public static String getLevel(int level) {
StringBuilder sb = new StringBuilder();
for (int x = 0; x < level; x++) {
sb.append("|--");
}
return sb.toString();
}
public static void showDir(File dir, int level) {
System.out.println(getLevel(level) + dir.getName());
level++;
File[] files = dir.listFiles();
for (int x = 0; x < files.length; x++) {
if (files[x].isDirectory())
showDir(files[x], level);
else
System.out.println(getLevel(level) + files[x]);
}
}
使用递归,碰到文件夹时,继续调用自身,放文件到集合
public static void fileToList(File dir, List<File> list) {
File[] files = dir.listFiles();
for (File file : files) {
if(file.isDirectory())
fileToList(file,list);
else {
if(file.getName().endsWith(".java"))
list.add(file);
}
}
}
// 省略写入文件方法
@Value("${app.name}")
private String projectName;
@Component
@ConfigurationProperties(locations="classpath:application.properties",prefix="app")
public class AppProperties{
String name;
String version;
}
@Autowired
private Environment env;
env.getProperty("app.name");
可以用于具体的方法中,较为灵活
import org.springframework.core.io.support.PropertiesLoaderUtils;
Properties properties=PropertiesLoaderUtils.loadAllProperties("application.properties");
查阅官方快捷键说明:Help -> Keymap Reference
常见快捷键,(Windows 下)
快捷键 | 解释 |
---|---|
代码自动排版 | Ctrl + Alt + L |
复制一行或选中的内容 | Ctrl + C |
查找 Java 类(推荐) | Ctrl + N |
查找资源(包括 Java 类)(推荐) | Ctrl + Shift + N |
全局查找字符串(推荐) | Ctrl + Shift + F |
窗口横向滚动(推荐) | Shift + 鼠标滚轮 |
自动补全语句分号(推荐) | Ctrl + Shift + Enter |
显示类继承结构 | Ctrl + H |
显示方法或类的 JavaDoc | Ctrl + Q |
重写父类或者接口的方法 | Ctrl + O |
整理 import | Ctrl + Alt + O |
回到上一次光标所在位置 | Alt + Ctrl + → / Alt + Ctrl + ← |
文件切换 | Alt + → / Alt + ← |
列出所有方法 | Alt + 7(Ctrl + F12 更好,可支持查找) |
生成方法(getter、setter) | Alt + Insert |
跳转到当前方法的调用方法 | Ctrl + 鼠标左键 |
跳转到指定行 | Ctrl + G |
搜索所有资源 | double Shift(输入 / 可以支持查找文件夹) |
查看一个接口的实现方法 | Ctrl + Alt + B |
重命名 | Shift + F6 |
替换 | Ctrl + R |
依次切换打开的文件(推荐) | Ctrl + Tab |
新建文件 | Ctrl + Alt + Insert |
显示工具窗口 | Alt + 数字角标 |
接口方法跳转到具体实现 | Ctrl + Alt + B |
跳转到接口声明 | F4 |
定位语法错误
按 F2 快速定位到下一个错误和警告处, Shift + F2 定位到上一个错误处
在版本控制文件对比窗口时,调到下一处修改的地方
按 F7 跳到下一处修改,Shift + F7 到上一处修改
显示类继承结构图(UML)
选中类名 -> 右键 Diagram -> 右键 Show Implementations -> 选中添加需要显示的子类
快捷方法显示类继承结构图
选中类名后 Ctrl + H -> 弹出视图中 Ctrl + A -> 右键 Diagram
设置鼠标划过显示 javadoc
File -> Setting -> Editor -> General -> Show quick documentation on mouse move
设置代码默认不折叠
File -> Setting -> Editor -> General -> Code Folding One line method
隐藏 .idea 文件夹和 *.iml 文件夹
setting -> File Type
给常用语句设置快捷键
Settings -> Editor -> Live Templates
可以新建一个自己的 Template Group,然后里面添加自己模板代码
设置自动注释不加在代码行首
Code Style -> Java -> Code Generation
去掉 Line comment at first column 和 Block comment at first column 复选框的勾
使项目脱离 svn 版本管理
删除隐藏的 .svn 文件夹即可
不显示面包屑导航
Editor - General - Appearance - Show breadcrumbs
不显示编辑面板左侧方法折叠和提示小图标
方法折叠:Editor - General - Code Floding - Show code floding outline
提示小图标:Editor - General - Show gutter icons
从接口直接直接跳到实现
ctrl + alt + 鼠标左键,也可以通过快捷键 Ctrl + Alt + B
补全判空、非空:在变量后面输入 . 接着输入 null 回车即可。非空即输入 notnull 或者 nn。
快速补全语句:Ctrl + Shift + Enter 补全分号和花括号等
选中多行:摁住鼠标滚轮,拖动即可
Setting->maven->runner VMoptions:-Dfile.encoding=GB2312
http://www.cnblogs.com/vhua/p/idea_1.html
数组需要连续的内存空间来存储,对内存的要求比较高。链表恰恰相反,不需要连续的内存空间,通过指针将零散的内存块串联起来。链表(List)常见结构:单链表、双链表、循环链表。
特殊结点:
各操作时间复杂度:
循环链表 是特殊的单链表,与单链表的唯一区别在于尾结点,循环链表的尾结点指向链表的头结点,首尾相连。单链表只有一个方向,双链表支持两个方向,除 next 指针之外,还有一个前驱指针 prev 指向前面的结点。
从链表中删除一个数据包含两种情况:
对于第一种情况,不管是单链表还是双链表,为了查找到给定值的结点,都需要从头结点开始依次遍历对比,直到找到值等于给定值的结点,然后通过指针操作将其删除。
单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析加法法则,删除只等于给定值的结点对应的链表操作总时间复杂度为 O(n)。
对于第二种情况,已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表不支持直接获取前驱结点,所以为了找到前驱结点,还是得从头结点开始遍历链表,直到 p->next=q。
但是对于双链表来说,此情况较有优势,因为保存了前驱结点的指针,省去遍历的步骤。所以针对第二种情况,单链表的删除操作需要 O(n) 而双链表只需要 O(1) 时间复杂度内搞定。
同理如果我们希望在链表的指定结点前面插入一个结点,双向链表比单链表有很大的优势,双向链表可以在 O(1) 时间复杂度内搞定,而单向链表需要 O(n) 的时间复杂度。
除了删除、插入有优势之外,对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系决定,决定是往后还是往前查找,所以平均只需要查找一半的数据。
LinkedHashMap 实现原理中包含双向链表这种数据结构
采 用空间换时间 的设计**,当内存充足时,追求代码的执行速度,可以选择空间复杂度较高,但时间复杂度相对较低的算法或者数据结构。相反内存比较吃紧,反过来需要用时间换空间的设计思路。
数组 | 链表 | |
---|---|---|
插入删除 | O(n) | O(1) |
随机访问 | O(1) | O(n) |
数组在简单易用,在实现上是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没有办法有效预读。
数组的缺点是大小固定,一经声明就要占用整块的连续内存空间。如果数组生命过大,系统很可能没有连续的内存空间分配给它。导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小限制,天然地支持动态扩容,也是与数组的最大区别。
链表中的每个结点都需要消耗额外的存储空间去存储一份下一个结点的指针,所以内存消耗会翻倍。而且对链表频繁的插入、删除操作,还会导致频繁的内存申请和释放,容易造成内存碎片,如果是 Java 语言,就有可能导致频繁的 GC。
维护一个有序的单链表,越靠近链表尾部的节点是越早之前访问的。当有新数据被访问时,从链表头开始顺序遍历链表。
时间复杂度为 O(n)
进程是程序的副本,进程是程序执行的实例
线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务
Thread
的子类,并重写 run()
Runnable
接口,并实现 run()
总结:
start()
为线程分配必须的系统资源、调度线程运行并执行线程的 run()
stop()
,而是让 run()
自然结束很常见的一个需求就是如何中断正在执行任务的线程?此时又可以分好几种情况
当线程处于正常执行状态时:处于 running() 状态,可以使用中断标记位的方式结束线程的运行。 一般推荐方式是使用中断标记位,每次迭代检查该标记的状态。
private static volatile boolean STOP = false;
**当线程处于可被打断状态:**sleeping(掉用了 Thread.sleep() 方法) 和 waittiing(调用了 Object.wait() 方法) 时,则需要使用 Thread#interrupt() 的方式打断其状态。
对中断操作的正确理解是:它不会真正地中断一个正在运行的线程,而只是发出中断请求,然后由线程在下一个合适的时刻中断自己。
-- 《Java 并发实战》 C7
**当线程处于不可被打断状态:**由于 I/O 操作阻塞或者由于 synchronized 进入锁池阻塞,此时就不能用 interrupt() 方法打断,因为这两种情况并不会去检查线程“已请求去取消”标记而抛出异常,只能设置线程的中断状态,但没有其他任何作用。此时要想终止线程就必须知道线程阻塞的原因:
- 同步的 Socket I/O
当对套接字调用 read() 和 write() 方法而阻塞时,这些方法都不会响应中断,可以调用 close() 方式,使其抛出异常 SocketException
- 同步的 I/O
当关闭一个正在 InterruptibleChannel 上等待的线程时,将抛出 CloseByInterruptException 异常并关闭链路。当关闭一个 InterrptibleChannel 时,将导致所有在链路上的操作的线程都抛出 AsynchronousCloseException
- Selector 的 异步 I/O
如果一个线程在调用 Selector#select() 方法时阻塞了,那么调用 close ()和 wakeUp() 会使线程抛出 ClosedSelectorException 并提前返回。
- 获取某个锁
如果一个线程由于等待某个内置锁而阻塞,那么将无法响应中断,因为线程认为它肯定会获得锁,所以将不会理会中断请求。但是,在 Lock 类中提供了 lockInterruptibly 方法,该方法允许在等待一个锁的同时仍能响应中断。
正常线程使用中断标记位的方式:
class MyThread implements Runnable {
private boolean flag = true;
@Override
public void run() {
while (flag) {
}
}
public void stopRunning() {
this.flag = false;
}
}
class ControlThread {
private MyThread r = new MyThread();
private Thread t = new Thread(r);
public void startThread() {
t.start();
}
public void stopThread() {
r.stopRunning();
}
}
一个线程从创建到消亡的过程,线程的生命周期分为五个状态:
创建状态(new)
当用 new 操作符创建一个新的线程对象时,该线程出于创建状态(只是一个空的线程对象,系统不为它分配资源)
可运行状态(runnable)
执行线程的 start()
将为线程分配必须的系统资源,安排其运行,并调用线程体的run()
,这样就使得该线程处于可运行状态(并不是运行状态,因为线程实际上并未运行,只是具备了运行的能力)
运行状态(running)
可运行状态(runnable)的线程获得了 cpu 时间片(timeslice),执行程序代码。
阻塞状态(block)
当发生下列事件时,会进入阻塞状态:
wait()
等待特定条件满足,放入线程等待队列(waitting queue)sleep()
、线程 i/o 阻塞返回可运行状态:
notify()
或者 notifyAll()
通知消亡状态(dead)
run()
,main()
执行结束,或者因异常退出了 run()
,则该线程结束生命周期,死亡的线程不可再次复生
加入 synchronized
后的线程状态转换图:(同步的线程状态转换图)
线程调度器选择优先级最高的线程运行。但是,如果发生一下情况,就会终止线程的运行
yield()
,让出了对 CPU 的占用权sleep()
,使线程进入睡眠状态Java 中每个对象都有一个锁(lock)或者叫监视器(monitor),当访问某个对象的 synchronized
方法时,表示将该对象上锁,此时其他任何线程都无法再去访问该 synchronized
方法,直到之前线程执行方法完毕后(或者是抛出异常)。那么将该对象的锁释放掉,其他线程才有可能再去访问该 synchronized
方法
示例代码:
class Example {
public synchronized void execute() throws Exception {
for (int i=0; i<20; i++) {
Thread.sleep(1000);
System.out.println("hello --" + i);
}
}
public synchronized static void execute2() throws Exception {
for (int i=0; i<20; i++) {
Thread.sleep(1000);
System.out.println("world --" + i);
}
}
}
class Thread1 implements Runnable {
private Example example;
public Thread1(Example example) {
this.example = example;
}
@Override
public void run() {
example.execute();
}
}
class Thread2 implements Runnable {
private Example example;
public Thread2(Example example) {
this.example = example;
}
@Override
public void run() {
example.execute2();
}
}
线程间相互等待资源,而又不释放自身的资源,导致无穷无尽的等待,其结果是系统任务永远无法执行完成。死锁问题是在多线程开发中应该坚决避免和杜绝的问题。
示例:
public class DeadLockDemo {
public void method1() {
synchronized (Integer.class) {
System.out.println(Thread.currentThread().getName() + " 获取到 Integer 锁");
Thread.sleep(1000);
synchronized (String.class) {
System.out.println(Thread.currentThread().getName() + " 获取到 String 锁");
}
}
}
public void method2() {
synchronized (String.class) {
System.out.println(Thread.currentThread().getName() + " 获取到 String 锁");
Thread.sleep(1000);
synchronized (Integer.class) {
System.out.println(Thread.currentThread().getName() + " 获取到 Integer 锁");
}
}
}
}
多线程编程的目的,就是"最大限度地利用 CPU 资源",当某一线程的处理不需要占用 CPU 而只和 I/O 等资源打交道时,让需要占用 CPU 资源的其它线程有机会获得 CPU 资源。从根本上说,这就是多线程编程的最终目的
线程安全是编程中的术语,指某个函数、函数库在多线程环境中被调用时,能够正确地处理多个线程之间的共享变量,使程序功能正确完成
1. 当一个线程进入一个对象的一个 synchronized 方法后,其它线程是否可进入此对象的其它方法?
其他方法的几种情况:
2. 为什么wait(),notify()方法要和synchronized一起使用?
wait()
作用为通知当前线程等待并释放对象锁,notify()
作用为通知等待此对象锁的线程重新获得对象锁,然而,如果没有获得对象锁,wait()
和 notify()
都是没有意义的,即必须先获得对象锁,才能对对象锁进行操作
JavaEE 开发中部署网站应用的常见方式总结,本文以 Tomcat 为例,列举三种方式:配置 tomcat 配置文件、打包应用放置特定位置、创建专属配置文件
在 Tomcat 中的 conf
目录中,在 server.xml 中的,<host/>
节点中添加:
<Context
path="/myapp"
reloadable="true"
docBase="D:\myapp"
workDir="D:\myapp\work">
</Context>
在 Tomcat 的配置文件中,一个 Web 应用就是一个特定的 Context,可以通过在 server.xml 中新建 Context 里部署一个 JavaWeb 应用程序。
其中 path
是虚拟路径(外部访问路径),docBase
是应用的物理路径(项目放在硬盘哪个位置),workDir
是这个应用的工作目录(默认是 Tomcat 目录中 work 目录),存放运行时生成的这个应用相关文件
注:
path=""
和 path="/"
应用不会被加载(原因不明)将 web 项目文件打包成 war 包或者直接将整个文件夹(包括该web的所有内容),拷贝到 Tomcat 的 webapps 目录中。
Tomcat 的 webapps 目录是 Tomcat 默认的应用目录,当服务器启动时,会加载所有这个目录下的应用。也可以将 JavaWeb 应用打成一个 war 包放在目录下,服务器会自动解开这个 war 包,并在这个目录下生成一个同名的文件夹。
一个 war 包就是有特性格式的 jar 包,它是将一个 Web 应用程序的所有内容进行压缩得到。具体如何打包,可以使用许多开发工具的IDE 环境,如 Eclipse、NetBeans、ant、JBuilder 等。也可以用 cmd 命令:
jar -cvf applicationname.war package.*;
在 Tomcat 的 conf\Catalina\localhost
目录中,新建一个 xml 文件,名字任意,该 xml 文件的内容为:
<Context
path="/myapp"
docBase="D:\myapp"
debug="0"
privileged="true">
</Context>
可以看出,文件中描述一个应用程序的 Context 信息,其内容和 server.xml 中的 Context 信息格式是一致的,文件名便是虚拟目录名。可以直接建立这样的一个 xml 文件,放在 Tomcat 的 conf\catalina\localhost 目录下
注意:
删除一个 Web 应用同时也要删除 webapps 下相应的文件夹和 server.xml 中相应的 Context,还要将 conf\catalina\localhost 目录下相应的 xml 文件删除。否则 Tomcat 仍会按配置去加载
方法三优点是可以定义别名。服务器端运行的项目名称为 path,外部访问的 URL 则使用 XML 的文件名。两种方式都可以访问到网站。
效果如下:
// 访问主网站:默认应用
http://localhost:8080/
// 访问二级网站(如:blog)
http://localhost:8080/blog
在 tomcat 的 conf\catalina\localhost 目录下新建 ROOT.xml
和 blog.xml
文件,内容如下:
<!-- ROOT.xml -->
<?xml version="1.0" encoding="UTF-8"?>
<Context path="/" reloadable="true" docBase="F:\deployDemo01"></Context>
<!-- blog.xml -->
<?xml version="1.0" encoding="UTF-8"?>
<Context path="/blog" reloadable="true" docBase="F:\deployDemo01-blog"></Context>
注:docBase 根据实际情况指定
应用已打包成 .war 包,放置在 Tomcat\webapps 路径下:
并在 sever.xml 中配置,如下(错误示例):
<Context
docBase="F:\DevelopmentKit\apache-tomcat-6.0.44\webapps\TestTomcatDoubleReload.war"
path="/ttd"
reloadable="true">
</Context>
解决:
参考:
http://lvzhou-31.iteye.com/blog/1898261
http://www.cnblogs.com/hwaggLee/p/5151827.html
http://www.cnblogs.com/xiaoyunxia/p/6307392.html
当调用 FileOutputStream#write(int i)
时,只写 1 个字节取低八位,也就是超过一个字节长度时,将会造成数据丢失,使用时需要注意。
FileOutputStream fos = new FileOutputStream("C:\\text.txt");
// 只将 1 个字节的数据写出去,剩余会被丢失
// 即写出了00100001
fos.write(289);
fos.close();
文件输出流是用于将数据写入 File 或 FileDescriptor 的输出流。文件是否可用或能否可以被创建取决于基础平台。特别是某些平台一次只允许一个 FileOutputStream(或其他文件写入对象)打开文件进行写入。在这种情况下,如果所涉及的文件已经打开,则此类中的构造方法将失败。
FileOutputStream 用于写入诸如图像数据之类的原始字节的流。要写入字符流,请考虑使用 FileWriter。
创建一个 FileOutputStream,用如下方式,假设文件不存在,则会被创建,若文件存在则会被覆盖。当文件路径中包含有不存在的文件夹或者盘符时,该方法会抛出 FileNotFoundException。
FileOutputStream fos = new FileOutputStream("D:\\demo.txt");
若文件不想被覆盖,则使用如下构造方法:指定追加模式为 true。此时当文件存在时,写操作会在文件末尾追加内容。
FileOutputStream fos = new FileOutputStream("D:\\demo.txt", true);
基本的使用方法如下,和 FileWriter 不同是 FileOutputStream 不带缓冲区,调用完 write 方法以后立刻会将内容刷入磁盘。
FileOutputStream fos = null;
try {
fos = new FileOutputStream("D:\\demo.txt");
fos.write('t');
} catch (IOException e) {
e.printStackTrace();
} finally{
if (fos!=null) {
try {
fos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
此类中常用 write(byte b[], int off, int len)
方法,将指定 byte 数组中从偏移量 off 开始的 len 个字节写入此文件输出流。
FileInputStream 从文件系统中的某个文件中获得输入字节。哪些文件可用取决于主机环境。
FileInputStream 用于读取诸如图像数据之类的原始字节流。要读取字符流,请考虑使用 FileReader。
创建一个 FileInputStream ,用如下方式,假设文件不存在,该方法会抛出 FileNotFoundException。
FileInputStream fis = new FileInputStream("D:\\demo.txt");
读取一个文件的几种方法,单字符读取,字符数组读取
FileInputStream fis = new FileInputStream("D:\\demo.txt");
int c = 0;
while ((c = fis.read()) != -1) {
System.out.println("字符:" + (char) c);
}
// .close()
FileInputStream fis = new FileInputStream("D:\\demo.txt");
byte[] buf = new byte[1024];
int num = 0;
while ((num = fis.read(buf)) != -1) {
System.out.println("字符:" + new String(buf, 0, num));
}
// .close()
结合读取文件和写入文件操作,实现简单的文本文件拷贝。
FileInputStream fis = null;
FileOutputStream fos = null;
try {
fis = new FileInputStream("D:\\pic\\1.jpg");
fos = new FileOutputStream("D:\\pic\\1_copy.jpg");
byte[] buf = new byte[1024];
int length = 0;
while ((length = fis.read(buf)) != -1) {
fos.write(buf, 0, length);
}
} catch (Exception e) {
try {
if (fis != null) {
fis.close();
}
if (fos != null) {
fos.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
该类实现缓冲的输出流。通过设置这种输出流,应用程序就可以将各个字节写入底层输出流中,而不必针对每次字节写入调用底层系统。
底层有 buf 数组,所以每次写完记得要 flush。使用实例如下:
FileOutputStream fos = new FileOutputStream("D:\\demo.txt");
BufferedOutputStream bfos = new BufferedOutputStream(fos);
bfos.write(new byte[]{'1', '2'});
bfos.flush();
// .close()
BufferedInputStream 为另一个输入流添加一些功能,即缓冲输入以及支持 mark 和 reset 方法的能力。
在创建 BufferedInputStream 时,会创建一个内部缓冲区数组。在读取或跳过流中的字节时,可根据需要从包含的输入流再次填充该内部缓冲区,一次填充多个字节。
mark 操作记录输入流中的某个点,reset 操作使得在从包含的输入流中获取新字节之前,再次读取自最后一次 mark 操作后读取的所有字节。
值得注意的是,该类的 available()
方法,解释为返回此输入流可读字节数,需要谨慎调用。当文件过大时,极容易导致内存溢出。
使用实例如下:
FileInputStream fis = new FileInputStream("D:\\demo.txt");
BufferedInputStream bfis = new BufferedInputStream(fis);
int lenght = 0;
byte[] buf = new byte[1024];
while ((lenght = bfis.read(buf)) != -1) {
// do something
}
结合缓冲读取文件和缓冲写入文件操作,实现简单的文本文件拷贝。
BufferedInputStream bfis = new BufferedInputStream(new FileInputStream("D:\\pic\\1.jpg"));
BufferedOutputStream bfos = new BufferedOutputStream(new FileOutputStream("D:\\pic\\1_pcopy.jpg"));
int lenght = 0;
byte[] buf = new byte[1024];
while ((lenght = bfis.read(buf)) != -1) {
bfos.write(buf, 0, lenght);
bfos.flush();
}
// .close()
参考:
传智播客毕向东
Collection
是一个高度抽象的接口,它主要的两个分支是:List
和 Set
,两者都是接口,皆继承于 Collection。List 是有序的队列,可以有重复的元素;而 Set 是数学概念中的集合,没有重复元素。
Java 抽象出了 AbstractCollection
抽象类,它实现了 Collection 中的绝大部分函数;这样,在 Collection 的实现类中,我们就可以通过继承 AbstractCollection 省去重复编码。
在 AbstractCollection 基础之上,又衍生出了 AbstractList
和 AbstractSet
,具体的 List 实现类继承于 AbstractList,而 Set 的实现类则继承于 AbstractSet。
另外,Collection 中有一个 iterator()
函数,它的作用是返回一个 Iterator
接口。通常,可以通过 Iterator
迭代器来遍历集合。ListIterator 是 List 接口所特有的,可以通过 listIterator() 返回一个ListIterator对象。
类定义如下:
public interface Collection<E> extends Iterable<E> {}
Collection 是一个高度抽象出的接口,是 Collection 层次结构中的根接口,它包含了集合的基本操作:添加、删除、清空、遍历(读取)、是否为空、获取大小、是否保护某元素等等。Collection 表示一组对象,这些对象也称为 collection 的元素
Collection 接口的所有子类(直接子类和间接子类)都必须实现2种构造函数:不带参数的构造函数和参数为 Collection 的构造函数。带参数的构造函数,可以用来转换 Collection 的类型。
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
类定义如下:
public interface List<E> extends Collection<E> {}
List 是一个继承于 Collection 的接口,即 List 是集合中的一种。特性是有序的队列,其中的每个元素都有一个索引;第一个元素的索引值是0,往后的元素的索引值依次+1。List 中允许有重复的元素。
List 继承于 Collection 接口,自然就包含了 Collection 中的全部接口,由于 List 是有序队列,它也额外的有自己的 API 接口。主要有添加、删除、获取、修改指定位置的元素、获取List中的子队列等。
// 相比与 Collection,List 新增的 API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
类定义如下:
public interface Set<E> extends Collection<E> {}
Set 继承于 Collection 接口,也是集合中的一种。特性是没有重复元素。没有重复元素怎么判断是依赖于具体实现的,如 ==、equals、hashCode 以及几个接口比如 Comparable 等等的规范下。
关于 API 方面,跟 Collection 完全一样。
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
类定义如下:
public abstract class AbstractCollection<E> implements Collection<E> {}
AbstractCollection
是一个抽象类,提供 Collection 接口的骨干实现,以最大限度地减少了实现此接口所需的工作。它实现了 Collection 中除 iterator() 和 size() 之外的函数。比如 ArrayList、LinkedList 等,它们这些类想要实现 Collection 接口,通过继承 AbstractCollection 就已经实现了大部分的接口了
类的定义如下:
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}
AbstractList
是一个继承于 AbstractCollection,并且实现 List 接口的抽象类。此类提供 List 接口的骨干实现,以最大限度地减少实现“随机访问”数据存储(如数组)支持的该接口所需的工作。
它实现了 List 中除 size()、get(int location) 之外的函数。
另外,和 AbstractCollection 相比,AbstractList 抽象类中,实现了 iterator() 接口。
类定义如下:
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {}
AbstractSet
是一个继承于 AbstractCollection,并且实现 Set 接口的抽象类。此类提供 Set 接口的骨干实现,从而最大限度地减少了实现此接口所需的工作。
由于 Set 接口和 Collection 接口中的 API 完全一样,Set 也就没有自己单独的 API。和 AbstractCollection 一样,它实现了 List 中除 iterator()
和 size()
之外的函数。
类定义如下:
public interface Iterator<E> {}
Iterator
是一个接口,是集合的迭代器。集合可以通过 Iterator 去遍历集合中的元素。一般从集合中删除指定元素时,可以使用此方法,是线程安全的。
boolean hasNext()
E next()
void remove()
参考文档:
https://blog.csdn.net/u011392897/article/details/54983068
IO 流用来处理设备之间的数据传输,Java 对数据的操作是通过流的方式,用于操作流的对象都在IO包中,基本功能是读写。
字节流可以处理任何流数据(包括文本、音频、图片等),而字符流只能处理文本文件。字符流的产生是因为文本文件相对常用,故对字节流进行了进一步的封装,在底层加上了查找码表进行编码的功能。
注: 由这四个类派生出来的子类名称都是以其父类名作为子类名的后缀,如:
InputStream 的子类 FileInputStream、Reader 的子类 FileReader
后进者先出,先进者后出,典型的 “栈” 结构(Stack)。栈是一种操作受限的线性表,只允许在一端插入和删除数据。当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就应该首选栈。
可以用是数组实现,也可以用链表来实现。用数组实现的栈称为顺序栈,用链表实现的栈称为链式栈。
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组,申请一个大小为 n 的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了,直接返回 false,入栈失败。
if (count == n) return false;
// 将 item 放到下标为 count 的位置,并且 count 加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空,则直接返回 null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
String tmp = items[count-1];
--count;
return tmp;
}
}
不管是顺序栈还是链式栈,存储数据只需要一个大小为 n 的数组就够了,在入栈和出栈的过程中,只需要一两个临时变量,所以空间复杂度是 O(1)。
不管是顺序栈还是链式栈,只涉及栈顶个别数据的操作,所以时间复杂度为 O(1)
操作系统给每个线程分配了一块独立的内存空间,这块内存组织成 栈 这种结构,用来存储函数调用时的临时变量,每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
编译器是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。从左向右遍历表达式,当遇到数字,直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。
如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。
用一个栈来保存未匹配的左括号,从左到右依次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号(弹出)。如果能匹配,则继续扫描剩下的字符串。如果扫描过程中遇到不能配对的右括号,或者栈中没有数据,则说明非法格式。
当所有的括号都扫描完,如果栈为空,则说明字符串为合法格式;否则说明有未匹配的左括号,为非法格式。
当你依次访问完一串页面 a-b-c 之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a,点击前进按钮,就可以重新查看页面 b、c。但是如果你后退到 b 页面后,点击了新的页面 d,那就无法再通过前进、后退功能查看页面 c 了。
使用两个栈,x 和 y,把首次浏览的页面依次压入栈 x,当点击后退按钮时,再依次从 x 中出栈,并将出栈的数据依次放入栈 y。当点击前进按钮时,依次从 y 中取出数据,放入 x 栈中。
当栈 x 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 y 中没有数据,说明当前页不能再前进。
数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。
线性表(Linear List),就是数据排成一条线一样的结构。每个线性表上的数据最多只有前后两个方向,除了数组,链表、队列、栈也是线性结构。对立的概念是非线性表,比如二叉树、堆、图等。数据之间并不是简单的前后关系
实现随机访问的原因。弊端:很多操作都非常低效,比如:插入、删除,为保证数据的连续性,需要做大量的数据搬移工作
a[i]_address = base_address + i * data_type_size
数组适合查找,查找时间复杂度为 O (1)
数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,用二分法查找,时间复杂度也是 O(logn)。所以,正确的表述:
数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)
如果在末尾插入则不需要移动数据,此时时间复杂度为 0(1),但如果在数组的开头插入元素,那所有的数据都需要搬运最坏的时间复杂度是 O(n),因为在每个位置插入元素的概率是一样的,所以平均情况的时间复杂度为(1+2+...+n)/n=O(n)。
如果数组中的数据是有序的,在某个位置插入一个新的元素时,必须按照刚才的方法。但如果数组中的数据并没有任何规律,只是被当做一个存储数据的集合。此时需要插入新元素到第 k 个位置,直接将 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 位置。
原因同插入操作。
如果不追求是数组中数据的连续性,将多次删除操作集中在一起执行。当数组中存在 a,b,c,d,e,f,g,h。现在需要依次删除 a,b,c 三个元素。
为了避免 d,e,f,g,h 这几个数据会被搬运三次,可以先记录下已经删除的数据,每次删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,再出发一次真正的删除操作,大大减少了删除操作导致的数据搬移。
注:此操作为 JVM 标记清除垃圾回收算法的核心**
在 C 语言中,数组越界是一种未决行为,并没有规定数据访问越界时编译器该如何处理。因为,访问数组的本质就是访问一段连续内存,只要通过偏移结算得到的内存地址是可用的,那么程序就可能不报任何错误。
Java 语言本身就会做越界检查,当越界时抛出 java.lang.ArrayIndexOutOfBoundsException 异常。
做非常底层的开发时,网络框架性能需要做到极致,数组就会优先于容器
a[k]_address = base_address + k * type_size
如果数组从 1 开始计数,那我们计算数组元素 a[k] 的内存地址就会变为
a[k]_address = base_address + (k-1) * type_size
对比两个公式,从 1 开始编号,每次随机访问数组元素都多了一次减法元素,对于 CPU 来说,就是多了一次减法指令。
对于 m * n 的数组,a [i][ j ] (i < m,j < n) 的地址为:
address = base_address + ( i * n + j) * type_size
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
ArrayList
是 List 接口的大小可变数组的实现。特点是其容量能在进行 add 操作时动态增长。它继承于 AbstractList,实现了 List, RandomAccess, Cloneable, Serializable 这些接口。
随机访问
ArrayList 实现了 RandmoAccess 接口,即提供了随机访问功能。指的是下标索引操作 index(i) 的时间复杂度是 O(1)。size、isEmpty、get、set、iterator、listIterator 操作在 O(1) 内完成,add(e) 操作平均在 O(1) 内完成,即添加 n 个元素需要 O(n) 时间。
自动扩容
底层是数组实现其容量是不能改变的,所以容量不够时,需要更大的数组,这个过程叫作扩容。每次扩容时,会拷贝一份新的内容,是个耗时的操作,避免频繁扩容影响性能。
线程不同步
ArrayList 是未同步的,多线程并发读写时需要外部同步,如果不外部同步,那么可以使用 Collections.synchronizedList 方法对 ArrayList 的实例进行一次封装,或者使用 Vector 类或 CopyOnWriteArrayList 类。
允许 null 值
对存储的元素无限制,允许null元素。
快速失败
iterator 和 listIterator 方法返回的迭代器是快速失败的,也就是如果在创建迭代器之后的任何时间被结构性修改,除了通过迭代器自己的 remove 或 add 方法之外,迭代器将直接抛出一个 ConcurrentModificationException,从而达到快速失败 fail-fast 的目的,尽量避免不确定的行为。
ArrayList的迭代器的快速失败行为不能被严格保证,并发修改时它会尽量但不100%保证抛出ConcurrentModificationException。因此,依赖于此异常的代码的正确性是没有保障的,迭代器的快速失败行为应该仅用于检测 bug。
能被克隆、能被序列化
// 默认构造函数
ArrayList()
// 指定初始化容量
ArrayList(int capacity)
// 构造一个包含指定 collection 的元素的列表
ArrayList(Collection<? extends E> collection)
对于此处要注意的是,无参构造函数在 1.6 和 1.7 中的实现是有差别的,
1.6 的实现方式是底层数组 大小默认为10;从 1.7 开始,无参构造方法构造的底层数组大小默认为0。
1.7 以后版本使用的是懒初始化方式。指的是默认构造方法构造的集合类,占据尽可能少的内存空间,在第一次进行包含有添加语义的操作时,才进行真正的初始化工作。
即在进行第一次 add/addAll 等操作时才会真正给底层数组赋非 empty 的值。如果 add/addAll 添加的元素小于 10,则把 elementData 数组扩容为 10 个元素大小,否则使用刚好合适的大小。
ArrayList 中使用私有方法 :ensureCapacity
、ensureCapacityInternal
方法来确保数组容量。
Resource resource = new ClassPathResource("appcontext.xml");
BeanFactory factory = new XmlBeanFactory(resource);
ApplicationContext factory = new ClassPathXmlApplicationContext("classpath:appcontext.xml");
// src目录下的
ApplicationContext factory = new ClassPathXmlApplicationContext("appcontext.xml");
ApplicationContext factory = new ClassPathXmlApplicationContext(new String[] {"bean1.xml","bean2.xml"});
// src/conf 目录下的
ApplicationContext factory = new ClassPathXmlApplicationContext("conf/appcontext.xml");
ApplicationContext factory = new ClassPathXmlApplicationContext("file:G:/Test/src/appcontext.xml");
ApplicationContext factory = new FileSystemXmlApplicationContext("src/appcontext.xml");
//使用了 classpath: 前缀 FileSystemXmlApplicationContext 也能够读入classpath下 的相对路径
ApplicationContext factory = new FileSystemXmlApplicationContext("classpath:appcontext.xml");
ApplicationContext factory = new FileSystemXmlApplicationContext("file:G:/Test/src/appcontext.xml");
ApplicationContext factory = new FileSystemXmlApplicationContext("G:/Test/src/appcontext.xml");
该方法只可用于 web 工程
ServletContext servletContext = request.getSession().getServletContext();
ApplicationContext ctx = WebApplicationContextUtils.getWebApplicationContext(servletContext);
BeanDefinitionRegistry reg = new DefaultListableBeanFactory();
XmlBeanDefinitionReader reader = new XmlBeanDefinitionReader(reg);
reader.loadBeanDefinitions(new ClassPathResource("bean1.xml"));
reader.loadBeanDefinitions(new ClassPathResource("bean2.xml"));
BeanFactory bf=(BeanFactory)reg;
通过 ContextLoaderListener 也可加载多个配置文件,在web.xml文件中利用 元素来指定多个配置文件位置,其配置如下:
<context-param>
<!-- Context Configuration locations for Spring XML files -->
<param-name>contextConfigLocation</param-name>
<param-value>
./WEB-INF/**/applicationContext.xml,
classpath:config/aer/applicationContext.xml,
classpath:org/codehaus/xfire/spring/xfire.xml,
./WEB-INF/**/*.spring.xml
</param-value>
</context-param>
Semaphore、CountDownLatch
public class ConcurrencyTest {
// 请求总数
public static int clientTotal = 5000;
// 同时并发执行的线程数
public static int threadTotal = 200;
public static int count = 0;
public static void main(String[] args) throws Exception {
ExecutorService executorService = Executors.newCachedThreadPool();
final Semaphore semaphore = new Semaphore(threadTotal);
final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
for (int i = 0; i < clientTotal ; i++) {
executorService.execute(() -> {
try {
semaphore.acquire();
add();
semaphore.release();
} catch (Exception e) {
log.error("exception", e);
}
countDownLatch.countDown();
});
}
countDownLatch.await();
executorService.shutdown();
log.info("count:{}", count);
}
private static void add() {
count++;
}
}
转换流中可以使用指定编码读取某个文件中的数据或使用指定编码将数据写入某个文件中
InputStreamReader 是字节流通向字符流的桥梁:它使用指定的 charset 读取字节并将其解码为字符。它使用的字符集可以由名称指定或显式给定,或者可以接受平台默认的字符集。
每次调用 InputStreamReader 中的一个 read() 方法都会导致从底层输入流读取一个或多个字节。要启用从字节到字符的有效转换,可以提前从底层流读取更多的字节,使其超过满足当前读取操作所需的字节。
为了达到最高效率,可要考虑在 BufferedReader 内包装 InputStreamReader。例如:
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
应用场景: 通过键盘录入数据。当录入一行数据后,就将该行数据进行打印。如果录入的数据是over,那么停止录入。对标准输出流(System.in)进行转换,包装成能够以字符形式操纵。
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(isr);
String line = "";
while ((line = reader.readLine()) != null) {
if ("over".equals(line)) {
break;
}
System.out.println(line);
}
应用场景: 同上。对标准输出流(System.out)进行转换,包装成能够以字符形式操纵。
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(isr);
String line = "";
OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter bw = new BufferedWriter(osw);
while ((line = reader.readLine()) != null) {
if ("over".equals(line)) {
break;
}
bw.write(line);
bw.newLine();
bw.flush();
}
把键盘录入的数据存储到一个文件
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = "";
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("D://demo.txt")));
while ((line = reader.readLine()) != null) {
if ("over".equals(line)) {
break;
}
bw.write(line);
bw.newLine();
bw.flush();
}
将一个文件的数据打印在控制台
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("D://demo.txt")));
String line = "";
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while ((line = reader.readLine()) != null) {
if ("over".equals(line)) {
break;
}
bw.write(line);
bw.newLine();
bw.flush();
}
流操作的基本规律:最痛苦的就是流对象有很多,不知道该用哪一个。通过三个明确来完成。
- 明确源和目的。
- 操作的数据是否是纯文本。
- 当体系明确后,在明确要使用哪个具体的对象。通过设备来进行区分:
集合 Java Collections Framework(JCF),就是可以容纳其他 Java 对象的对象,是 Java 提供的工具包,位于 java.util.* 系列包中,始于 JDK 1.2,以下是其优点:
集合只能存放对象,所以对于基本数据类型,需要将其转成对应的包装类型后,才能放入。
Java 集合主要可以划分为4个部分:List 列表、Set 集合、Map 映射、工具类(Iterator 迭代器、Enumeration 枚举类、Arrays 和 Collections )。Java 集合工具包框架图如下:
图的最顶层有三个类,分别是 Collection
、Map
、Iterator
,三者的共同点是都是接口。
Collection
和 Map
大致没有什么关联,因为 Map
表示的是关联式容器而不是集合,但也有将 Map
中的键值转化成集合视图的方法。
Collection
依赖于 Iterator
,是因为 Collection
的实现类都要实现 iterator()
函数,返回一个 Iterator
对象。
Collection 层次结构 中的根接口。Collection 表示一组对象,这些对象也称为 collection 的元素。一些 collection 允许有重复的元素,而另一些则不允许。
一些 collection 是有序的,而另一些则是无序的。JDK 不提供此接口的任何直接 实现:它提供更具体的子接口(如 Set 和 List)实现。
此接口通常用来传递 collection,并在需要最大普遍性的地方操作这些 collection。
Collection
是一个接口,是高度抽象出来的集合,它包含了集合的基本操作和属性。它包含了 List 和 Set 两大分支。
List
是一个有序的队列,每一个元素都有它的索引。第一个元素的索引值是0。Set
是一个不允许有重复元素的集合。将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。
Map
是一个映射接口,即 key-value 键值对。Map 中的每一个元素包含一个 Key 和这个 Key 对应的 Value
对 collection 进行迭代的迭代器。迭代器取代了 Java Collections Framework 中的 Enumeration。迭代器与枚举有两点不同:
- 迭代器允许调用者利用定义良好的语义在迭代期间从迭代器所指向的 collection 移除元素。
- 方法名称得到了改进。
Iterator
是遍历集合的工具,说 Collection 依赖于 Iterator,是因为 Collection 的实现类都要实现 iterator() 函数,返回一个 Iterator 对象。
实现 Enumeration 接口的对象,它生成一系列元素,一次生成一个。连续调用 nextElement 方法将返回一系列的连续元素。
例如,要输出 Vector v 的所有元素,可使用以下方法:
for (Enumeration<E> e = v.elements(); e.hasMoreElements();)
System.out.println(e.nextElement());
这些方法主要通过向量的元素、哈希表的键以及哈希表中的值进行枚举。枚举也用于将输入流指定到 SequenceInputStream 中。
注:此接口的功能与 Iterator 接口的功能是重复的。此外,Iterator 接口添加了一个可选的移除操作,并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。
Enumeration
是 JDK 1.0 引入的抽象类。作用和 Iterator 一样,也是遍历集合;但是 Enumeration 的功能要比 Iterator 少。在上面的框图中,Enumeration 只能在 Hashtable, Vector, Stack 中使用。
此接口是1.5新增的,目的就是为了 for-each 循环(增强型for循环)。除了数组外,其他类想要使用 for-each 循环必须实现这个接口。
此接口无方法,用于标记 List 接口的实现类,表明它能在O(1)的时间内进行通过下标获取对应的元素的操作,从而能支持一些特别的算法/操作来加速代码执行。
老生长谈
自然排序指的是类实现了 Comparable。SortedXXX/NavigableXXX 以及很多 Arrays.sort 方法都依赖这个。
a > b <---> a.compareTo(b) > 0
a = b <---> a.compareTo(b) = 0
a < b <---> a.compareTo(b) < 0
Comparator 接口是在一个类没有实现 Comparable 接口时,提供一个外部比较方法,方便程序实现以及程序变更,其他的和 Comparable 一样。
java.util.Collections
、java.util.Arrays
、apache commons collections、guava commom collect。集合类框架很好的扩展,同时封装了很多工具方法与新功能的集合类。
参考:
http://www.cnblogs.com/skywang12345/p/3323085.html
http://www.cnblogs.com/CarpenterLee/p/5414253.html
https://blog.csdn.net/u011392897/article/details/54983068
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.