Java 查找算法

简介: <div class="markdown_views"><p>这个问题有几个点要先确认</p><ul><li>必须是有序,如果无序的话就只能全遍历了</li><li>查找算法跟数据结构相关,不同的数据结构适用于不同的查找算法</li><li>查找算法与磁盘I/O有一定的关系,比如数据库在索引排序的时候,如果每次都从磁盘读取一个节点然后进行判断</li></ul>

这个问题有几个点要先确认

  • 必须是有序,如果无序的话就只能全遍历了
  • 查找算法跟数据结构相关,不同的数据结构适用于不同的查找算法
  • 查找算法与磁盘I/O有一定的关系,比如数据库在索引排序的时候,如果每次都从磁盘读取一个节点然后进行判断

数组

如果知道下标的话就方便了,查找的复杂度为1.
如果是针对值的查找,那么顺序遍历是O(n),

二分查找

使用二分查找的话可以减少时间复杂度为:O(logn)

/**
 * 二分查找又称折半查找,它是一种效率较高的查找方法。 
  【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
 * @author wzj
 *
 */
public class BinarySearch { 
    public static void main(String[] args) {
        int[] src = new int[] {1, 3, 5, 7, 8, 9}; 
        System.out.println(binarySearch(src, 3));
        System.out.println(binarySearch(src,3,0,src.length-1));
    }

    /**
     * * 二分查找算法 * *
     * 
     * @param srcArray
     *            有序数组 *
     * @param des
     *            查找元素 *
     * @return des的数组下标,没找到返回-1
     */ 
   public static int binarySearch(int[] srcArray, int des){ 

        int low = 0; 
        int high = srcArray.length-1; 
        while(low <= high) { 
            int middle = (low + high)/2; 
            if(des == srcArray[middle]) { 
                return middle; 
            }else if(des <srcArray[middle]) { 
                high = middle - 1; 
            }else { 
                low = middle + 1; 
            }
        }
        return -1;
   }

      /**  
     *二分查找特定整数在整型数组中的位置(递归)  
     *@paramdataset  
     *@paramdata  
     *@parambeginIndex  
     *@paramendIndex  
     *@returnindex  
     */
    public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){  
       int midIndex = (beginIndex+endIndex)/2;  
       if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){
           return -1;  
       }
       if(data <dataset[midIndex]){  
           return binarySearch(dataset,data,beginIndex,midIndex-1);  
       }else if(data>dataset[midIndex]){  
           return binarySearch(dataset,data,midIndex+1,endIndex);  
       }else {  
           return midIndex;  
       }  
   } 
}

但是插入因为会涉及当前节点后的所有值得移动,一次,其时间复杂度为O(n) + O(log n)

链表

只能从头节点遍历, 查找的复杂度是O(n)
插入或者是删除,因为只需要移动指针,时间复杂度为O(1) + O(n)

树的查找,主要是先序遍历,中序等遍历方式。
插入和删除,还是比较快
常用的会有如下的衍生方式:

二叉树

二叉树的构建:

class BinaryNode{
        int value;
        BinaryNode left;
        BinaryNode right;
        public BinaryNode(int value){
            this.value = value;
            this.left = null;
            this.right = null;
        }

        public void add(int value){
            if(value > this.value){
                if(this.right != null){
                    this.right.add(value);
                }else{
                    this.right = new BinaryNode(value);
                }
            }else{
                if(this.left != null){
                    this.left.add(value);
                }else{
                    this.left = new BinaryNode(value);
                }
            }
        }

        // 中序查找
        public BinaryNode get(int value){
            if(this.value == value){
                return this;
            }
            if(this.value > value){
                return this.left.get(value);
            }

            if(this.value < value){
                return this.right.get(value);
            }
            return null;
        }
    }

插入的复杂度本身并不高,只是简单的节点添加。但是因为寻找插入位置的查找操作的复杂度跟树的高度相关为logn,极差的情况下可能接近于线性查找。

平衡二叉树

平衡二叉树是尽量减少数高的二叉树,其算法中增加了左旋和右旋的操作。插入复杂度会高一些,但是会得到不错的查找性能。

B+Tree

学习自这里
这个就要说一下上面说的跟磁盘I/O相关的,因此为了减少磁盘I/O。可以利用磁盘的预读特性,一次提取大概相当于一页大小的节点到内存中。
先要说一下B-Tree.
一个平衡的m-way查找数,其要满足如下的条件:

  • 每节点中的数据量 < m
  • 每层节点数 <= m
  • 子数节点要完全大于、小于、或者在其之间。 也就是不能越过父节点的两个值
  • 叶子节点中的值的个数>=m/2
  • 非叶子节点中的值的个数=子节点个数-1
    如下图:
    这里写图片描述
    可以看出,三个子节点的有两个值,三个子节点中的数据分别对应了小于、之间、大于这个范围

B+Tree
与上面的差别是:

  • 所有关键字都在叶子节点
  • 父节点存储的都是到子节点的指针
  • 会有两个入口,一个是根节点,另外一个是从最小叶子节点开始的指针
    这里写图片描述

查找跟二叉树比较像,因为插入的时候已经是相当于二分算法了,所以只需要,递归找到就可以了。

Hash表

为了解决一些不容易排序,或者查找的对象。 比如图像,视频等等。
在Java的HashMap中有使用。
是一个链表的数组
- 对key进行进行散列函数,求Hash值,找到其对应的链表。
- 剩下的解决hash冲突的问题
- 解决hash冲突,可以在命中链表之后顺序比较
- 这里顺便再说一下一致性hash. 预置很多节点,选择最近的节点存入,可以解决增加节点数据转移的问题。

相关文章
|
4月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
4月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
101 3
|
4月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
182 0
|
3月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
334 58
|
2月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
|
9月前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
189 15
|
2月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
59 0
|
11月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
590 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
5月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
125 3
|
7月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。

热门文章

最新文章