查找
查找算法性能的最主要评价标准是平均查找长度（Average Search Length,ASL），即查找过程中关键字的平均比较次数。
1.折半查找（BinarySearch）
折半查找算法针对的是有序的数组
public class BinarySearch {
public int binarySerach(int start,int end,int target,int[] array){
//当start == end时，直接去比较array[start] 与target值即可
while(start != end){
//中间的值
int mid = (start + end) / 2;
if(array[mid] == target){
return mid;
}else if(array[mid] < target){
//如果目标值大于中值，重新设置start为mid+1;
start = mid + 1;
}else{
//如果目标值大于中值，重新设置end为mid-1;
end = mid -1;
}
}
return array[start] == target ? start:-1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//测试代码
int[] array = new int[]{1,3,5,7,93,323,423,12134,223323};
BinarySearch bs = new BinarySearch();
int target = bs.binarySerach(0, array.length - 1, 12134, array);
}
}
折半查找算法是一种典型的采用分治策略的算法，它将问题分为规模更小的子问题。
折半查找算法的平均查找长度 O(log2n)。
折半查找算法适用于顺序储存并且需要已排序。适用与数据量较小的情况下。
2.基于索引顺序表的分块查找
对于数据量较大的顺序表，建立索引是一种以空间换取查找时间的做法。顺序表称为主表，索引表是有序的，但是顺序表不一定是有序的。如字典就是一种多级索引。
索引表:
| 姓 | 页码 |
|---|---|
| 黄 | 1 |
| 曾 | 5 |
主表1:
| 名 | 下标 |
|---|---|
| 黄1 | 0 |
| 黄2 | 1 |
| 黄3 | 2 |
| 黄4 | 3 |
主表5：
| 名 | 下标 |
|---|---|
| 曾1 | 4 |
| 曾2 | 5 |
| 曾3 | 6 |
| 曾4 | 7 |
设索引表的长度为i，每块主表的平均长度为m
所以如上表的ALS长度为 (m+1)/2 + (s+1)/2
3.二叉排序树
二叉排序树
4.散列（hash）
以上的几种排序的平均查找长度ASL都与数据量有关，数据量越大，比较次数就越多。在数据量很大的时候花费时间就很大了。
而散列，可以根据元素的关键字就获取到当前这个value储存在哪个位置。
i = hash(key)，所以i又叫散列地址，
实际上，散列函数就是关键字集合到地址集合的映射。
如果这个映射是1对1的，那么查找效率就是O(1)。
但是散列函数是压缩映射，并不是1：1的，所以不可避免地会有冲突。
处理冲突的方法有如下：
a.开放寻址法
当产生冲突时，继续查找下一个位置是否存在值，如果不存在，则把这个值放在这里，反之继续往下寻找。
比如key16,29共同映射到位置1，现在16先映射到了位置1，要放key29时发现这个位置1已经有值了，那么就继续查找位置2,如果发现他没有放值的话，就把key29-value放在这个位置。
查找的时候
假如查找key29，key29映射的是位置1,但是位置1的key并不是29,所以继续往下找位置2,然后发现位置2的key确实是29,那么就是这个啦。
随之而来的问题是，假如值666的映射就位置2,他插入的时候就会发现自己的位置怎么被人占了，而且霸占它位置的并不是和他同义词的，这就产生了非同义词冲突。
冲突大量存在的时候，多个冲突的key-value查找退化成了顺序查找了，极大降低查找效率。
寻找下一个位置的方式包括：
1.线性探查法
2.线性补偿法，用用一个固定的步长去寻找
3.随机探测法（生成一个随机表，每次探测按表上的那个随机数）
b.链地址法（拉链法）
把同义词冲突的key-value放到一个单链表里。
c.再哈希法
发生突出时再次hash。。耗费时间。
网友评论