哈希查找算法⼜称散列查找算法，是⼀种借助哈希表（散列表）计算数据元素存储地址，从而查找目标元素的一种方法。它是非常高效的查找算法，其时间复杂度在最好的情况下可以达到O（1），即使是比较坏的情况，时间复杂度也非常低，查找数据非常快。事物都有两面性，有优即有劣。虽然哈希查找非常高效，但是他的高效是以空间换时间的代价来实现的。在如今，空间问题我们很容易解决，比如加内存等。可是时间复杂度的提高就非常难，因此，在允许的情况下，我们一般会选择牺牲空间换取时间上的高效。

1、哈希查找算法介绍

用途：哈希查找算法适⽤于⼤多数场景，既⽀持在有序序列中查找⽬标元素，也⽀持在⽆序序列中查找⽬标元素，其时间复杂度在最好的情况（无哈希冲突时）下可以达到O（1）。

哈希表：哈希表（Hash table）⼜称散列表，是⼀种存储结构，通常⽤来存储多个元素。和其它存储结构（线性表、树等）相⽐，哈希表查找⽬标元素的效率⾮常⾼。每个存储到哈希表中的元素，都配有⼀个唯⼀的标识（⼜称“索引”或者“键”），⽤户想查找哪个元素，凭借该元素对应的标识就可以直接找到它，⽆需遍历整个哈希表。

原理：

哈希查找也叫散列查找，是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数f(key)，将所需查询的数据映射到表中一个位置来访问记录，若查找集合中存在这个记录，则必定在 f(key) 的位置上，从而加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

• 哈希技术既是一种存储方法，也是一种查找方法。

• 哈希冲突，即key1≠key2，而f(key1)=f(key2)时，即通过哈希函数计算得到键相同，这也就意味着同一个键对应多个值。

2、哈希函数 f(key) 的构造方法

从原理可知，哈希查找算法找计算键的散列函数非常重要，必须保证唯一性。在哈希表中,若出现key1≠key2，而f(key1)=f(key2)时，则这种现象称为地址冲突（哈希冲突），此时key1和key2对哈希函数f来说是同义词。根据设定的哈希函数f=H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，这一映射过程为构造哈希表(散列表)。

好的哈希函数应该使一组关键字的哈希地址均匀分布在整个哈希表中，从而减少冲突，常用的构造哈希函数的方法有：

1）直接地址法（直接寻址法）：取关键字的某个线性函数值为散列地址

• ① 公式：f(key)=a * key+b （a,b都是常数）。
• ② 适合查找表较小且连续的情况。
• ③ 优点：简单、均匀，不会产生冲突。
• ④ 缺点：需要知道关键字的分布，现实中不常用。

2）数字分析法：

• ① 方法：抽取关键字中的一部分来计算存储位置。
• ② 适用于关键字位数较大的情况。

3）平方取中法：

• ① 方法：将关键字先平方，然后截取中间x位作为存储位置。假设关键字是1234，那它的平方就是1522756，再抽取中间的3位就是277
• ② 适合用于不知道关键词分布，且位数不长的情况。

4）除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k) = k mod p， p<=m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。此方法为最常用的构造散列函数的方法。

• ① 方法：f(key)=key mod p (p<=m)，m是散列表表长。
• ② p取小于等于m的最小质数或者不包含小于20质因子的合数，以减少冲突的情况。

5）折叠法：将关键字从左到右分割成位数相等的几个部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。比如关键字是9876543210，散列表表长为三位，我们将它分成四组，987|654|321|0，然后将他们叠加求和等于1962，再求后三位得到散列地址962。

• ① 方法：将关键字拆分成若干部分后累加起来，根据散列表表长取总和的后若干位作为存储位置。
• ② 适用于不知道关键字分布，且位数较长的情况。

6）随机数法：

• ① 方法：f(key)=random(key)。
• ② 注意random的随机种子需要是固定的，以便查询的时候能够根据key重新找到存储位置。
• ③ 适用于关键字长度不等的情况。

散列表查找算法实现：

1. 首先定义一个散列表结构
2. 对散列表进行初始化
3. 对散列表进行插入操作
4. 根据不同的情况选择散列函数和处理冲突的方法（这里选用的是除留余数法和开放定址法）

3、常用冲突处理方法

采用均匀的哈希函数可以减少地址冲突，但是不能避免冲突，当我们使用哈希函数后发现有 key1 != key2，但却有 f(key1) = f(key2) 时，即发生冲突。因此，必须有良好的方法来处理冲突，通常处理地址冲突的方法如下:

1）开放地址法

1. 开放定址法就是一旦发生了冲突（两个数据元素的哈希值相同），就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总是能找到，然后将记录插入。

2. 当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。

这种方法是最常用的解决冲突的方法。下面的代码中也使用了这种方法。

2）拉链法（链地址法）

将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。

将大小为M 的数组的每一个元素指向一个链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。下图很清楚的描述了什么是拉链法。

“John Smith”和“Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。

3）再散列函数法

4）公共溢出区法

4、操作步骤

• step1 取数据元素的关键字key，计算其哈希函数值。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。

• step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。

5、实现方式

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 哈希查找
 */
public class HashSearch {
    // 初始化哈希表
    static int hashLength = 7;
    static int[] hashTable = new int[hashLength];

    // 原始数据
    static int[] list = new int[]{13, 29, 27, 28, 26, 30, 38};

    public static void main(String[] args) throws IOException {
        System.out.println("*******哈希查找*******");

        // 创建哈希表
        for (int i = 0; i < list.length; i++) {
            insert(hashTable, list[i]);
        }
        System.out.println("展示哈希表中的数据：" + display(hashTable));

        while (true) {
            // 哈希表查找
            System.out.print("请输入要查找的数据：");
            int data = new Scanner(System.in).nextInt();
            int result = search(hashTable, data);
            if (result == -1) {
                System.out.println("对不起，没有找到！");
            } else {
                System.out.println("数据的位置是：" + result);
            }
        }
    }

    /**
     * 方法：哈希表插入
     */
    public static void insert(int[] hashTable, int data) {
        // 哈希函数，除留余数法
        int hashAddress = hash(hashTable, data);

        // 如果不为0，则说明发生冲突
        while (hashTable[hashAddress] != 0) {
            // 利用 开放定址法 解决冲突
            hashAddress = (++hashAddress) % hashTable.length;
        }

        // 将待插入值存入字典中
        hashTable[hashAddress] = data;
    }

    /**
     * 方法：哈希表查找
     */
    public static int search(int[] hashTable, int data) {
        // 哈希函数，除留余数法
        int hashAddress = hash(hashTable, data);

        while (hashTable[hashAddress] != data) {
            // 利用 开放定址法 解决冲突
            hashAddress = (++hashAddress) % hashTable.length;
            // 查找到开放单元 或者 循环回到原点，表示查找失败
            if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, data)) {
                return -1;
            }
        }
        // 查找成功，返回下标
        return hashAddress;
    }

    /**
     * 方法：构建哈希函数（除留余数法）
     *
     * @param hashTable
     * @param data
     * @return
     */
    public static int hash(int[] hashTable, int data) {
        return data % hashTable.length;
    }

    /**
     * 方法：展示哈希表
     */
    public static String display(int[] hashTable) {
        return Arrays.toString(hashTable);
    }
}