Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。

简介: 【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。

Java中的查找算法主要包括二分查找(Binary Search)和哈希查找(Hashing)。这两种算法都是基于特定数据结构的高效查找方法。以下是它们在Java中的实现示例。

二分查找

二分查找是一种在已排序数组中查找元素的搜索算法。它将数组分为两个部分,每次比较中间元素与目标值,然后根据比较结果决定在左半部分还是右半部分继续查找。

public class BinarySearch {
   
    public static int binarySearch(int[] arr, int target) {
   
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
   
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
   
                return mid;
            } else if (arr[mid] < target) {
   
                left = mid + 1;
            } else {
   
                right = mid - 1;
            }
        }

        // 如果未找到目标元素,则返回-1
        return -1;
    }
}

哈希查找

哈希查找利用哈希函数将键映射到哈希表中的位置,从而快速查找或插入元素。哈希函数应该尽量减少冲突,并且哈希表需要支持动态调整大小以保持良好的性能。

以下是一个简单的哈希表实现:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HashTable<K, V> {
   
    private final Map<K, List<V>> map;

    public HashTable() {
   
        this.map = new HashMap<>();
    }

    public void put(K key, V value) {
   
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public boolean containsKey(K key) {
   
        return map.containsKey(key);
    }

    public List<V> get(K key) {
   
        return map.getOrDefault(key, List.of());
    }
}

在这个实现中,我们使用了Java内置的HashMap来存储键值对。每个键对应的值是一个列表,因为一个键可能对应多个值。通过put方法可以插入键值对,通过containsKey检查键是否存在,通过get获取与给定键关联的所有值。

请注意,以上哈希表实现不考虑删除操作以及解决哈希冲突的方法。在实际应用中,你可能需要选择更复杂的哈希表实现,如Open Addressing、Separate Chaining等策略来处理冲突。

相关文章
|
9天前
|
存储 Java 程序员
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
33 10
|
22天前
|
存储 算法 安全
深入理解SHA系列哈希算法:安全性的保障与演进
深入理解SHA系列哈希算法:安全性的保障与演进
|
26天前
|
存储 Java C++
Java虚拟机(JVM)管理内存划分为多个区域:程序计数器记录线程执行位置;虚拟机栈存储线程私有数据
Java虚拟机(JVM)管理内存划分为多个区域:程序计数器记录线程执行位置;虚拟机栈存储线程私有数据,如局部变量和操作数;本地方法栈支持native方法;堆存放所有线程的对象实例,由垃圾回收管理;方法区(在Java 8后变为元空间)存储类信息和常量;运行时常量池是方法区一部分,保存符号引用和常量;直接内存非JVM规范定义,手动管理,通过Buffer类使用。Java 8后,永久代被元空间取代,G1成为默认GC。
27 2
|
10天前
|
存储 设计模式 监控
Java面试题:如何在不牺牲性能的前提下,实现一个线程安全的单例模式?如何在生产者-消费者模式中平衡生产和消费的速度?Java内存模型规定了变量在内存中的存储和线程间的交互规则
Java面试题:如何在不牺牲性能的前提下,实现一个线程安全的单例模式?如何在生产者-消费者模式中平衡生产和消费的速度?Java内存模型规定了变量在内存中的存储和线程间的交互规则
19 0
|
15天前
|
存储 Java
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
|
16天前
|
存储 缓存 NoSQL
使用Java编写高效的文件处理和存储系统
使用Java编写高效的文件处理和存储系统
|
22天前
|
存储 算法 安全
MD5哈希算法:原理、应用与安全性深入解析
MD5哈希算法:原理、应用与安全性深入解析
|
24天前
|
算法 安全 Java
Java数据结构与算法:哈希函数
Java数据结构与算法:哈希函数
|
24天前
|
存储 算法 Java
Java数据结构与算法:用于高效地存储和检索字符串数据集
Java数据结构与算法:用于高效地存储和检索字符串数据集
|
25天前
|
存储 Java
顺序存储二叉树(java)
顺序存储二叉树(java)
10 0