一 查找
查找生活中的例子很多, 拿快递驿站来说, 我们怎么才能更快的找到自己的快递. 如果一点顺序都没有, 查找的时间复杂度为 O(n). 第一种想到的就是给每个快递一个编号, 然后按照编号放好, 这样我们只要使用先看中间, 就每次可以淘汰一半的快递 (也就是二分查找的思路) 代价是 O(lgn). 很明显生活中不是这样, 生活中如果快递比较少, 按照手机尾号分类, 就是一种 hash 算法, 这样查找的效率提高很多.
二 二分查找的简单实现
这里另外写了一个方法 也就是找到所有符合条件的 key, 基本思路就是找到左边界和右边界.
- public class ErFen {
- public static void main(String[] args) {
- int arr[] = {1, 2, 3, 4, 4,4,5, 69, 88, 555};
- System.out.println(find(arr,4));
- System.out.println(Arrays.toString(findAll(arr, 4)));
- }
- public static int[] findAll(int[] arr, int key) {
- int begin = 0;
- int end = arr.length - 1;
- int mid = (begin + end) / 2;
- int left = -1;
- int right = -1;
- while (true) {
- if(arr[mid]==key&&(mid==0||arr[mid]>arr[mid-1])){
- left = mid;
- break;
- }else if(arr[mid]>=key){
- end = mid - 1;
- }else{
- begin = mid + 1;
- }
- if (begin> end) {
- break;
- }
- mid = (begin + end) / 2;
- }
- if(left==-1)
- return new int[]{-1 , -1};
- begin = 0;
- end = arr.length - 1;
- mid = (begin + end) / 2;
- while (true) {
- if(arr[mid]==key&&(mid==arr.length-1||arr[mid]<arr[mid+1])){
- right = mid;
- break;
- }else if(arr[mid]<=key){
- begin = mid + 1;
- }else{
- end = mid - 1;
- }
- mid = (begin + end) / 2;
- }
- return new int[]{left, right};
- }
- public static int find(int[] arr, int key) {
- int begin = 0;
- int end = arr.length - 1;
- int mid = (begin + end) / 2;
- while (true) {
- if(arr[mid]==key)
- return mid;
- else if(arr[mid]<key)
- begin = mid + 1;
- else
- end = mid - 1;
- if (begin> end) {
- break;
- }
- mid = (begin + end) / 2;
- }
- return -1;
- }
- }
三 哈希函数的相关问题
hash 函数可以看作是一种分类的思想, 既然分类就涉及到一类的元素怎么处理, 一种是开放地址法 比如放快递的时候 , 尾号以 75 已经有快递了, 就放在 74 上. 另一种就是 hashmap 中采用的, 也就是拉链法, 把一个分类的组织起来, 也就是经典的桶结构.
其次是常见应用:
1. 字符串哈希(hashmap)
在数据存储领域, 主要是数据的索引和对容器的结构化支持, 比如哈希表.
2. 加密哈希
用于数据 / 用户核查和验证. 一个强大的加密哈希函数很难从结果再得到原始数据. 加密哈希函数用于哈希用户的密码, 用来代替密码本身存在某个服务器撒很难过. 加密哈希函数也被视为不可逆的压缩功能, 能够代表一个信号标识的大量数据, 可以非常有用的判断当前的数据是否已经被篡改(比如 MD5), 也可以作为一个数据标志使用, 以证明了通过其他手段加密文件的真实性.
3. 布隆过滤器
来源: http://www.bubuko.com/infodetail-3100903.html