Article Outline
对常见的数据结构和算法做一个初步的了解
<!--more-->
算法和数据结构的重要性
- 程序 = 算法 + 数据机构
- 其是计算机世界的基石，是一个开发者的内功
- 掌握好算法及数据结构之后，对代码效率的提升是本质性的
算法的复杂度
即对一个算法的复杂程度的数学描述
- 时间复杂度
O(1)- 哈希桶/数组随机寻址 （常数）即解决问题的时间和问题规模无关，比如数组寻址，无论多大的数组，只要在连续内存中，CPU都能很快返回结果O(N)- 遍历（线性）O(log(n))- 二分查找，二叉树（对数）O(n*log(n))- 基于比较的排序算法的下界O(n^2)- 冒泡排序（平方）
- 时间复杂度的计算是忽略常数的
- 即
O(2n) == O(n)
- 即
- 时间复杂度的计算中，高阶复杂度会吞掉低阶复杂度
- 比如
O(n^2) + O(n) == O(n^2)
- 比如
一些常用算法举例
基本数据结构
数组
- 随机寻址
- 常数时间
- 插入
- 线性时间
- 查找
- 无序：线性时间
- 有序：对数时间（二分查找）
接下来手写一个二分查找：
public class BinarySearchDemo {
// 假设 数组是从小到大排好序的
private static int binarySearch(int[] array, int target) {
int start = 0, end = array.length - 1;
while (true) {
if (array[start] == target) {
return start;
}
if (array[end] == target) {
return end;
}
if (target < array[start] || target > array[end]) {
return -1;
}
int mid = (start + end) / 2;
if (target < array[mid]) {
end = mid - 1;
} else if (target > array[mid]) {
start = mid + 1;
} else {
return mid;
}
}
}
public static void main(String[] args) {
System.out.println(binarySearch(new int[]{1, 4, 5, 7, 11, 15, 20}, 15));
System.out.println(binarySearch(new int[]{1, 4, 5, 7, 11, 15, 20}, 3));
}
}链表
和数组不同，数组是内存中连续的一系列地址，注意数组一定是连续的，
而链表则像一串珠子，每有新元素的时候，新开辟一块空间，后面元素中保存前一元素的地址
上述特性决定了链表的寻址是比较慢的（线性时间），因为只能从第一个元素开始一直往后找找到目标元素
但是链表的插入和删除则非常快，不会有像数组一样需要新增或者删除元素时后面的元素都得顺位移动
链表只需要将目标节点存储的前后节点的地址改变即可
关于单向链表（单链表）和双链表的区别：单链表每一个节点只保存着下一个节点的地址，而双链表保存着前一个和后一个节点的地址
手写一个简易的单链表例子来说明上述的链表结构和特性：
// 单向链表（单链表)的实现
public class Node {
Integer address; // 简易实现 用Integer表示内存地址
Node next;
public Node(Integer address, Node next) {
this.address = address;
this.next = next;
}
public static void main(String[] args) {
// 声明3个节点
Node head = new Node(1, null);
Node second = new Node(2, null);
Node third = new Node(3, null);
// 将节点们串起来
head.next = second;
second.next = third;
// 在这里就得到了一个简易的单向链表 可以使用debugger查看其内部结构
// 对于链表的特殊结构，使用for循环遍历方法也有不同：
for (Node currentNode = head; currentNode != null; currentNode = currentNode.next) {
System.out.println(currentNode.address);
}
}
}在上述例子中，展示了一个单链表的结构和特性，下来写一个简易的双链表来展示链表的新增/删除元素：
// 双链表的实现
public class Node {
Integer address; // 简易实现 用Integer表示内存地址
Node next;
Node prev;
public Node(Integer address) {
this.address = address;
}
public static void main(String[] args) {
// 声明3个节点
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// 将节点们串起来
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
for (Node currentNode = head; currentNode != null; currentNode = currentNode.next) {
// 在这里对地址为2的节点进行删除
if (currentNode.address == 2) {
// 将上一个节点存储的下一个节点的地址改为当前节点的下一个节点的地址
currentNode.prev.next = currentNode.next;
currentNode.next.prev = currentNode.prev; // 更改当前节点下一个节点的prev为当前节点的prev
}
}
}
}- 寻址
- 线性时间
- 插入/删除
- 常数时间
- 查找
- 线性时间
来看一个手写翻转单链表的例子：
package com.github.hcsp.datastructure;
public class ReverseLinkedList {
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
node1.next = node2;
Node node3 = new Node(3);
node2.next = node3;
Node node4 = new Node(4);
node3.next = node4;
print(node1);
print(reverse(node1));
}
// 原地翻转一个单链表
// 传递的参数是原始链表的头节点
// 返回翻转后的链表的头节点
public static Node reverse(Node head) {
Node prev = null;
Node pointer = head;
Node temp;
while (pointer != null) {
temp = pointer.next;
pointer.next = prev;
prev = pointer;
pointer = temp;
}
return prev;
}
public static class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
private static void print(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.value);
if (current.next != null) {
System.out.print("->");
}
current = current.next;
}
}
}如果想简单点实现的话，直接使用一个栈结构将单链表遍历一遍设置next即可。
再看一个判断链表是否成环的例子：
想判断链表是否成环，主要的判断思路为：
从同一个起点同时开始以不同速度前进的
2个指针最终相遇，那么可以判定存在一个环。
所以主要的判断方法为：
先设置两个指针都指向表头，其中
p1每次前进一个节点，p2每次前进两个节点，且p1和p2同时走， 当p2指向的地址为null，就证明链表没有环。如果在某个时刻，p1和p2指向的地址相同，那么链表就是有环的。
简单实现如下：
/**
* 判断一个单链表是否成环
* @param head 单链表的头结点
* @return
*/
private static boolean isCircle(Node head) {
if (head == null) {
return false;
}
//定义两个指针为同一起点
Node n1 = head; //慢指针
Node n2 = head; //快指针
//只要有环的话，这个循环条件就绝对会满足，如果没有环的话，到了最后总不满足
while(n2.next != null && n2.next.next != null) {
n1 = n1.next; //n1一次走一步
n2 = n2.next.next; //n2一次走两步
if (n1 == n2) { //如果成环，总会有一点n1==n2
return true;
}
}
return false;
}栈
- FILO(First In Last Out)
栈可以理解成一个杯子或者桶，先放进去的后拿出来
在Java虚拟机中，所有方法的调用都是在方法栈中的，最开始只有一个Main方法,每当一个方法调用的时候，会形成一个栈帧，该方法会被压入栈中
在多个方法嵌套调用时，后调用的先出栈
队列
- FIFO(First In First Out)
队列和栈是相对的，队列是先进去的先出来
哈希表
查找/插入/删除操作都是O(1)
哈希表内部有若干个桶，称为哈希桶，根据存储的对象们的特点，将其分为若干个哈希桶。
举个例子，比如有张三，李四，王五，赵六四个人，传统的数据结构中就是一股脑的将其存进去
而哈希表根据要存储的对象，将其分为了若干个桶，比如说本例中根据姓氏分为了张，李，王，赵 4个哈希桶
那么我们在检索是否存在张三时，就不需要像传统数据结构那样去检索整个结构，而是只需要去姓张的桶里查找即可
这个根据对象计算出不同的值从而分出不同的桶的过程就叫哈希运算
哈希表就是通过哈希运算将大规模的对象检索平摊到了若干个哈希桶的检索
哈希算法与碰撞
上述例子中提到的哈希运算，体现在代码里就是Object.hashCode(), 哈希表的愿望是将所有存储的对象近乎平均的分到每一个哈希桶里面去
然而存在一个问题是，我们hashCode的返回值为int，而int最多只有42亿，即最多只能有这么多桶，但是Java世界中的对象种类则为正无穷
所以肯定会出现哈希桶的碰撞，即同一个桶中数据过多的情况
比方说我现在有一个HashMap，内部有100个桶，我要存一百个元素，但是发生了最极端的碰撞，100个对象都存在了同一个桶中，而剩下的99个桶都是空的
这就引起了一个问题，此时检索HashMap跟检索一个链表的复杂度是一样的，原本理想的复杂度O(1)下降到了O(n)
HashMap的每一个桶内部都是一个链表，而在Java8之后，桶内部的实现是链表+红黑树，规模大了（目前超过8个会变为红黑树）会变为红黑树提升性能
哈希桶的内部实现及源码解析
Java7中的HashMap的实现为数组+链表，桶的底层为一个数组，因为其寻址快，而每个桶存储内容的数据结构为一个链表
先从Java7的HashMap开始说起
查看源码，我们可以看到，默认容量必须为2的次幂（因为必须要进行左移运算，所以必须为2的次幂），且初始为16
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16最大容量为: MAXIMUM_CAPACITY = 1 << 30;即2^30
而为什么哈希桶的数量一定要是2的次幂呢，原因是在进行计算要将对象放在哪个桶里的时候，进行了一个计算：
hash & (length - 1)长度减一然后和hash进行按位与,因为length为2的次幂，所以二进制的length - 1绝对会是11111111这种全为1的数，
再和hash进行按位与之后，保存的还是hash值作为数组下标，而如果不是2的次幂的话，减一之后位数上会出现0，按位与之后会造成有些桶是空的
而在不断put之后，在超过当前容量*负载因素的这个计算值之后(默认为16 * 0.75 = 12个)之后就开始扩容resize,扩容时还要重新计算所有桶的哈希值（rehash）
扩容默认也是扩大一倍,扩容之后将原有的内容重新计算hash之后移到新的容器中去，另外resize很消耗性能，初始化的时候尽量选取容量合适的HashMap
详细的代码不再赘述，总结一下Java7的HashMap的问题：
- 并发环境中容易造成死锁（形成环形链表，一直卡在
get()） - 容易发生碰撞，对于
String等的HashCode()可以设计哈希值相等的字符进行DOS攻击（比如拼接http请求字符串，攻击tomcat）
Java8之后对上述问题做了改进：
- 数组（桶底层）和 链表+红黑树（桶内部）
- 扩容时插入顺序改进, 做了保持顺序的处理，减少了出现死锁的概率，但是仍然是线程不安全的
- 函数方法
forEachcompute
Map的新APImergereplace