13. 哈希搜索

PangHu大约 8 分钟

哈希搜索（Hashing Search）是基于哈希表（Hash Table）的搜索方法。哈希表通过哈希函数（Hash Function）将键（Key）映射到数组的某个索引上，从而实现快速查找。下面我将解释哈希搜索的实现原理，给出一步步的数据演示，并最后提供Java代码示例。

实现原理

哈希函数：哈希函数接受一个键（Key）作为输入，并输出一个整数索引（Index）。理想情况下，哈希函数应该均匀分布输入到输出空间，即对于不同的输入，哈希函数应该产生不同的输出，或者至少对于不同的输入产生尽可能少的冲突（Collision）。
哈希表：哈希表是一个数组，用于存储键值对（Key-Value Pair）。数组的索引由哈希函数根据键计算得出。
处理冲突：当两个不同的键产生相同的哈希值时，就会发生冲突。有多种处理冲突的方法，如链地址法（Separate Chaining，即使用链表或红黑树等数据结构存储具有相同哈希值的键）和开放地址法（Open Addressing，如线性探测、二次探测等）。

优点

**速度快：**哈希搜索的核心是通过哈希函数将数据映射为唯一的哈希值，进而通过哈希值直接定位到数据在存储介质上的位置。这种“一步到位”的查找方式使得哈希搜索的平均查找复杂度为O(1)，即无论数据量多大，查找时间都是常数级别。

**空间利用率高：**哈希索引的结构紧凑，因为它只需存储哈希值和对应的数据地址（如行指针），这大大降低了存储开销。同时，由于哈希函数的作用，不同大小的数据都能被映射为固定长度的哈希值，从而节省了存储空间。

**支持快速插入和删除：**哈希表在插入和删除数据时，只需计算新数据的哈希值，然后将其添加到哈希表或从中删除即可，无需移动其他数据，因此操作效率很高。

缺点

**不能避免读取行：**哈希索引只包含哈希值和行指针，而不存储字段值，所以在查找时需要先通过哈希值找到行指针，然后再读取对应的数据行。虽然访问内存中的行的速度很快，但在某些场景下，这种额外的读取操作可能会对性能产生影响。

**无法用于排序：**由于哈希索引数据并不是按照索引值顺序存储的，所以无法直接用于排序操作。无法使用部分索引列匹配查找：哈希索引始终是使用索引列的全部内容来计算哈希值的，因此不支持部分索引列匹配查找。例如，在数据列（A,B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。

**只支持等值查找：**哈希索引只支持等值比较查询，如=、IN()、<=>等操作。它不支持任何范围查询，如WHERE price>100这样的条件。

**存在Hash冲突：**当不同的数据经过哈希函数计算后得到相同的哈希值时，就发生了哈希冲突。此时，存储引擎需要遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。哈希冲突越多，查找效率就越低。

综上所述，哈希搜索在速度、空间利用率和插入/删除操作方面有着显著的优势，但在某些特定场景下（如排序、部分索引列匹配查找、范围查询等）存在限制。因此，在选择是否使用哈希搜索时，需要根据具体的应用场景和需求进行权衡。

应用场景

数据库索引： 哈希索引在数据库中用于快速查找和检索数据，通过减少查询时间来提高数据库性能。特别是在需要快速定位数据，并且不依赖于数据的物理顺序时，哈希索引是一个理想的选择。

缓存系统： 哈希索引在缓存系统中用于快速存储和检索数据，加快数据读写速度，提升应用程序的整体性能。在高并发、需要快速响应的场景中，如Web应用、在线游戏等，缓存系统结合哈希索引可以显著提升用户体验。

电子邮件系统： 在电子邮件系统中，哈希索引可以帮助快速查找和检索邮件，减少查询时间，提高邮件系统的性能。尤其是在处理大量邮件、需要快速定位特定邮件时，哈希索引的优势尤为明显。

搜索引擎： 哈希索引在搜索引擎中用于快速查找和检索网页，提高搜索引擎的响应速度和准确性。在处理海量网页数据时，哈希索引能够迅速定位到相关信息，提高搜索效率。

密码存储： 哈希索引在密码存储中用于快速验证用户密码，确保密码安全，避免密码泄露。通过将密码转换为哈希值进行存储和比对，可以防止密码被直接获取和破解。

分布式存储： 在分布式存储系统中，哈希算法被用于数据分片和负载均衡。通过将数据的哈希值作为存储位置的依据，可以实现数据在多个节点上的均匀分布和高效访问。

数据校验： 哈希函数可以用于数据校验，校验网络传输过程中的数据是否正确，防止数据被恶意篡改。在数据传输和存储过程中，通过计算数据的哈希值并进行比对，可以确保数据的完整性和一致性。

总结来说，哈希搜索在需要快速查找和检索数据的场景中都非常适用，包括数据库、缓存、电子邮件、搜索引擎、密码存储、分布式存储和数据校验等多个领域。这些场景的共同特点是数据量大、查询频繁且对性能要求较高，而哈希搜索正是解决这些问题的有效手段之一。

数据演示

假设我们有一个哈希函数，它对于给定的键，返回该键的ASCII码和除以数组长度后的余数作为索引。

初始化哈希表：假设我们有一个长度为5的数组（索引从0到4），用于存储键值对。
插入键值对：
- 插入 "apple"（ASCII码和为 97 + 112 + 112 + 108 + 101 = 529），哈希值为 529 % 5 = 4，存储在索引4。
- 插入 "banana"（ASCII码和为 98 + 97 + 110 + 97 + 110 + 97 = 599），哈希值为 599 % 5 = 4（冲突），但我们可以使用链地址法处理冲突，即在索引4的位置存储一个链表，链表中包含 "apple" 和 "banana" 的键值对。
搜索键值对：
- 搜索 "apple"，计算哈希值为 4，直接访问索引4的位置，找到链表，遍历链表找到 "apple" 的键值对。
- 搜索 "orange"（ASCII码和为 111 + 114 + 97 + 110 + 103 + 101 = 636），哈希值为 636 % 5 = 1，直接访问索引1的位置（假设该位置是空的），返回未找到。

Java代码示例

当然，下面是的Java示例代码，包括插入（put）和搜索（get）键值对的哈希表实现：

import java.util.ArrayList; 
import java.util.List; 
   
public class HashTable { 
    private List<List<KeyValuePair>> table; 
    private static final int SIZE = 5; // 哈希表大小 
   
    // 键值对类 
    static class KeyValuePair { 
        String key; 
        Object value; 
   
        KeyValuePair(String key, Object value) { 
            this.key = key; 
            this.value = value; 
        } 
    } 
   
    // 构造函数 
    public HashTable() { 
        table = new ArrayList<>(SIZE); 
        for (int i = 0; i < SIZE; i++) { 
            table.add(new ArrayList<>()); 
        } 
    } 
   
    // 自定义哈希函数（简单示例） 
    private int hash(String key) { 
        int hash = 0; 
        for (char c : key.toCharArray()) { 
            hash += c; 
        } 
        return hash % SIZE; 
    } 
   
    // 插入键值对 
    public void put(String key, Object value) { 
        int index = hash(key); 
        List<KeyValuePair> bucket = table.get(index); 
        for (KeyValuePair pair : bucket) { 
            if (pair.key.equals(key)) { 
                // 如果键已存在，更新值 
                pair.value = value; 
                return; 
            } 
        } 
        // 键不存在，添加到链表中 
        bucket.add(new KeyValuePair(key, value)); 
    } 
   
    // 搜索键值对 
    public Object get(String key) { 
        int index = hash(key); 
        List<KeyValuePair> bucket = table.get(index); 
        for (KeyValuePair pair : bucket) { 
            if (pair.key.equals(key)) { 
                // 找到键，返回对应的值 
                return pair.value; 
            } 
        } 
        // 键不存在，返回null 
        return null; 
    } 
   
    // 示例方法，打印哈希表内容 
    public void printTable() { 
        for (int i = 0; i < SIZE; i++) { 
            List<KeyValuePair> bucket = table.get(i); 
            System.out.println("Bucket " + i + ": "); 
            for (KeyValuePair pair : bucket) { 
                System.out.println("  Key: " + pair.key + ", Value: " + pair.value); 
            } 
        } 
    } 
   
    // 主方法，用于测试 
    public static void main(String[] args) { 
        HashTable hashTable = new HashTable(); 
        hashTable.put("apple", "A fruit"); 
        hashTable.put("banana", "Another fruit"); 
        hashTable.put("cherry", "A small red fruit"); 
   
        hashTable.printTable(); // 打印哈希表内容 
   
        System.out.println("Searching for 'apple': " + hashTable.get("apple")); 
        System.out.println("Searching for 'orange': " + hashTable.get("orange")); 
    } 
}

在上面的代码中，我添加了一个printTable方法来打印哈希表的内容，以及一个main方法来测试哈希表的插入和搜索功能。运行main方法将看到哈希表的内容以及搜索"apple"和"orange"的结果。