java查找算法：二分查找、哈希查找等

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等策略来处理冲突。