经典数据结构

• 无序链表
• 数组
• 散列表（拉链表的hashmap 和线性探测法）
• 树结构 (二叉查找树 红黑树)

源码下载地址

二分查找、二叉查找树、无序链表的代码
https://github.com/huangzhenshi/Algorithms_Fourth

数据结构比较

要解决的问题：维护一个有序的数据结构同时，实现下面的功能

• 快速的查找：是否存在该元素，查找到最大值最小值
• 支持灵活的操作：插入、删除

• 无序链表的优点在于插入快，但是在维护一个有序数组的时候，无法快速的找到 node[3]，也就是难找到排名第N的元素。
• 数组的优势在于可以快速的定位到排名第三的元素，但是插入的时候需要后续元素顺延，根据下标查找快。
• 树形结构结合了数组和链表的特点，牺牲了数组的查询性能，但是更高效的插入性能
• 散列表结构实现了常数级别的查找，和快速的插入，但是没有顺序

无序链表

每次插入的时候，先遍历一遍是否已经有这个key了，有的话替换key的value，没有的话，插入在链表的首位。

• 在插入不重复的数据的时候，每次插入都需要遍历所有元素，N^2/2 次比较。平方级别的比较次数。
• 查找无需链表中是否有key值平均需要 N/2 次查询

  public void insert(Node node){ for(Node x=first;x!=null;x=x.next){ if(node.key==x.key){ x.value=node.value; return; } } Node old=first; first=node; first.next=old; size++; }

性能消耗

• 查找的次数（性能消耗）
• 比较的次数
• 交换的次数

二分查找维护有序数组

• 优点：容易理解，最差lgN 性能下实现查找，平均N/2性能的插入（中间位置，后面的顺延一个位置）
• 缺点：在于每次插入一个新的元素的时候，后面的元素都要顺序顺延一个位置。

//二分查找特性 最差情况想的比较次数是 lgN次
// rank  arr,lo,--mid,key  而不是让hi=mid，因为 --mid的话，最后会有hi<lo的时候
//所以分为4种情况
//如果命中就返回该key在 arr中的下标位置；
//如果小于最小值 就返回 -1； 如果大于最大值就返回 hi+1
//如果未命中，则返回的是该新元素在arr中 应有的位置
public static int rank(int[] arr,int lo,int hi,int key){
	 	if(hi==-1) return hi; 
		if(hi<lo) return lo;
		int mid=lo+(hi-lo)/2;
		if(key<arr[mid]){
			return rank(arr,lo,--mid,key);
		}else if (key>arr[mid]){
			return rank(arr,++mid,hi,key);
		}else{
			return mid;
		}
}

二叉查找树维护有序数组

原理

构建一棵树，小的在左边，大的在右边。每次插入都是挂在树的最外一层。最差情况下的查找和插入的性能由树的高度决定，当插入的数据为逆序的数据的时候，就是一个无序链表，最好的情况，就是一棵满二叉树，此时树的高度为lgN。被证明随机键的树高度为 2.99lgN,对数级别。

性能分析

• 最差情况下的插入和查找成本都是N ，就是有序数组插入导致的 链表
• 平均情况下 查找命中 1.39lgN 的查找和插入成本

源码展示 难点在于递归

public void put(char key,int value){
	root=put(root,key,value);
}
//每次put都是在树的末梢节点上新增一个节点
//记住 递归调用return时不会结束父程序，父程序会进行 size+1操作的
public Node put(Node x,char key,int value){
	//当根节点为null时会调用 该方法，初始化根节点
	//当put到树末端的时候也会调用该方法，使其挂在树上
	if(x==null) return new Node(key,value,1);
	if(key>x.key){
		x.right=put(x.right,key,value);
	}else if(key<x.key){
		x.left=put(x.left,key,value);
	}else{
		x.value=value;
	}
	x.N=size(x.left)+size(x.right)+1;
	return x;
}

平衡二叉树(红黑树、2-3树)维护有序数组

原理：

为了降低二叉查找树在最差情况下的情况，发明的平衡二叉树，往一棵树里插入，如果只有1个元素就变2个，如果已经有2个了，就变成一个3个，就向上分裂，根节点分裂的话，树的高度就+1；

特点：

• 大小为N的红黑树高度不会超过2lgN
• 可以实现随机一亿个数字插入之后，树的高度在19-30之间。
• 红黑树就是转置把一个节点有2个元素的中间连接为红连接，展开就是红黑树了，但是总结了一套插入的方法

主要是插入有3种情况

• 节点里面没有元素，直接存进入
• 节点里面已经有1个元素，形成一个有2个元素的节点
• 节点里面已经有2个元素，但是父节点只有1个元素，推到父节点
• 节点里面已经有2个元素，而且父节点里面也有2个元素，推到父节点，父节点再推到父父节点

性能

• 最差情况下： 查找和插入都是 2lgN
• 平均情况下： lgN

散列表

依赖高效的散列算法：

1. 把键按照一定的规则塞到长度为M的数组中
2. 使数尽量散列开来，均匀的分布到数组当中，避免数组一个位置里面太多的键，同时也避免一个位置上，不挂元素
3. 这种运算对于计算机来说，开销越小越好

经典散列方法：

1. 除留余数法：只是解决了键塞到数组中，但是散列均匀情况未做考虑。如果待插入的数字都是M的整数倍，那么所有的元素都会被塞到数组的第一个位置arr[0]的位置
   把键转换为数字，除以M（数组大小）求余数，就是所在数组中的下标位置了。
   例如 数字101 在 数组长度为10中的，余数为1，所以就在arr[1]的位置了。
2. 二进制 与运算(java HashMap的计算原理)

散列表的两种实现方式：

拉链法和线性探测法，但是这两种方法的高效都依赖有一个 好的散列算法（足够散列、算法对计算机运算友好），同时也都要支持动态调整大小。
相对于树形结构，散列表不具有排序功能，但是查找的性能是在常数级别，而不是对数级别。插入性能的话，散列表的性能依赖于 N/M 因子的设置和散列算法，总体而言肯定是高于树形结构。
牺牲的是没有了顺序功能。

拉链法：

hashmap的实现原理，一个小的数组 每个位置都是一个链表，通过散列求到对应的数组下标，看该位置是否有元素，有的话，遍历是否有同样的值后插进去。

线性探测法：

要求一个相对较大的数组，一般 元素总数:数组长度 <1：2，通过散列算法求到对应的数组下标，如果该位置已经有元素，则继续往后，直到找到null位置插入。

比较：
线性探测法在删除元素的时候，需要把后续的簇元素全部重新插入，相对来说，拉链法更容易实现。但是如果连续的内存越多的话，线性探测法的簇很短的话，线性探测法更快。