哈希查找法

kinglyjn 2020-11-25 阅读次

哈希查找简介

如果说二分查找靠的是层层 “精密的筛选”，那么哈希查找就是 “瞬间移动”。它在理想情况下的时间复杂度是惊人的 $O(1)$。

核心本质：从比较到计算

普通的查找算法，本质都是比较：A 是否等于 B？如果不等，是大还是小？
而哈希查找彻底抛弃了比较，它的核心逻辑是：通过一个函数，直接把 “值” 变成 “地址”。

二分查找：在一排储物柜里，按编号一半一半地找。
哈希查找：你手里有一张纸条（哈希函数），上面写着：”柜子编号 = 你的姓名拼音首字母”。你只需看一眼名字，就直奔那个柜子，根本不需要看别的柜子一眼。

哈希查找的三大支柱

① 哈希函数 (Hash Function)：

我们需要一个数学公式，把任何输入（数字、字符串、甚至对象）转换成一个固定的数组下标。最简单的公式是取模法：index = target % arraySize。

② 哈希表 (Hash Table)

本质上是一个数组。哈希函数计算出来的索引，就是数据在这个数组里的存储位置。

③ 哈希冲突 (Hash Collision) —— 最关键的问题

如果 “张三” 计算出的位置是 5，”李四” 计算出的位置也是 5，该怎么办？我们这里使用最简洁直观的拉链法：在位置 5 挂一个链表，冲突的人都排在链表里。

简单哈希查找代码

MyHashMap 的存取过程演示

已加载初始化数据。

核心代码：

/**
 * @author KJ
 * @description 简单哈希查找
 */
public class MyHashMap {

    private static class Node {
        int key;         // 查找凭证（如：工号）
        String value;    // 实际数据（如：姓名）
        Node next;       // 冲突拉链节点的 next 指针
        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] table; // 哈希桶数组
    private int capacity; // 数组容量

    public MyHashMap(int capacity) {
        this.capacity = capacity;
        this.table = new Node[capacity];
    }

    /**
     * 哈希函数：计算存储位置
     */
    private int hash(int key) {
        return Math.abs(key) %  capacity;
    }

    /**
     * 存入数据
     */
    public void put(int key, String value) {
        int index = hash(key);
        Node newNode = new Node(key, value);
        // 处理冲突（如果桶里面已经有数据，使用头插法）
        if (table[index] != null) {
            newNode.next = table[index];
        }
        table[index] = newNode;
    }

    /**
     * 哈希查找：核心逻辑
     */
    public String get(int key) {
        // 第一步：瞬移到对应的桶
        int index = hash(key);
        Node current = table[index];

        // 第二步：在桶内通过链表寻找匹配的 Key
        while (current != null) {
            if (current.key == key) {
                return current.value; // 找到了返回数据
            }
            current = current.next;
        }
        return null; // 没找到
    }

    public static void main(String[] args) {
        // 插入测试数据
        MyHashMap map = new MyHashMap(10);
        map.put(202010, "Owlias");
        map.put(202011, "Leon");
        map.put(202012, "KJ"); // 故意制造一个与 202602 模 10 相同的 Key（假设冲突）

        // 查找数据
        int searchKey = 202012;
        String result = map.get(searchKey);
        System.out.printf("编号 %s 对应的员工是: %s\n",
                searchKey,
                result != null ? result : "未找到");
    }
}

为什么它是终极武器

我们来看它和二分查找的比较：

哈希查找虽然快到极致，但它也是有代价的，那就是它牺牲了 “顺序性”。

如果你问哈希表：“告诉我这里面最小的数是谁？” 它会一脸懵逼，因为它根本不记得谁大谁小。
如果你问：“帮我找 20 到 50 之间的所有数？” 它也无能为力。

这就是 HashMap、 TreeSet 能够快速定位的核心原理，牺牲数据的顺序性，把空间换时间这件事做到了极致！

标题：

哈希查找法

作者：

kinglyjn

声明：

引用本文请务必注明出处，原创不易，感谢尊重。

K-空间

koo-hub, cool-code.

哈希查找法

哈希查找简介

简单哈希查找代码

为什么它是终极武器