开放地址法哈希实现——线性探测法

一 点睛

线性探测法是最简单的开发地址法，线性探测的增量序列为 d=1,2...m-1

二 需求

有一组关键字{14 36 42 38 40 15 19 12 51 65 34 25}，若表长为 15，散列函数为hash(key) = key % 13,则可采用线性探测法处理冲突，构造散列表。

三 最终探测结果

哈希地址	0	1	2	3	4	5	6	7	8	9	10	11	12	13	15
关键字	65	14	40	42	15	25	19		34		36		38	12	51
比较次数	1	1	2	1	3	9	1		1		1		1	2	3

四 实现

package hash;

import java.util.Scanner;
import java.util.concurrent.atomic.AtomicInteger;

public class Hash {
    static int m = 15; // 哈希表的表长
    static int NULLKEY = 0;//单元为空的标记
    static int HT[];
    static int HC[];

    // 哈希函数
    static int H(int key) {
        return key % 13;
    }

    static int Linedetect(int HT[], int H0, int key, AtomicInteger cnt) {
        int Hi;
        for (int i = 1; i < m; ++i) {
            cnt.getAndIncrement();
            Hi = (H0 + i) % m; // 按照线性探测法计算下一个哈希地址 Hi
            if (HT[Hi] == NULLKEY)
                return Hi;    // 若单元 Hi 为空，则所查元素不存在
            else if (HT[Hi] == key)
                return Hi; // 若单元 Hi 中元素的关键字为 key
        }
        return -1;
    }

    static int SearchHash(int HT[], int key) {
        // 在哈希表HT中查找关键字为 key 的元素，若查找成功，返回哈希表的单元标号，否则返回 -1
        int H0 = H(key); // 根据哈希函数H（key）计算哈希地址
        int Hi;
        AtomicInteger cnt = new AtomicInteger(1);
        if (HT[H0] == NULLKEY)// 若单元 H0 为空，则所查元素不存在
            return -1;
        else if (HT[H0] == key) { // 若单元H0中元素的关键字为 key，则查找成功
            System.out.println("查找成功，比较次数：" + cnt);
            return H0;
        } else {
            Hi = Linedetect(HT, H0, key, cnt);
            if (HT[Hi] == key) { // 若单元 Hi 中元素的关键字为 key，则查找成功
                System.out.println("查找成功，比较次数：" + cnt);
                return Hi;
            } else
                return -1;    //若单元Hi为空，则所查元素不存在
        }
    }


    static boolean InsertHash(int HT[], int key) {
        int H0 = H(key); // 根据哈希函数 H（key）计算哈希地址
        int Hi = -1;
        AtomicInteger cnt = new AtomicInteger(1);
        if (HT[H0] == NULLKEY) {
            HC[H0] = 1; // 统计比较次数
            HT[H0] = key; // 单元 H0 为空，放入
            return true;
        } else {
            Hi = Linedetect(HT, H0, key, cnt); // 线性探测
            if ((Hi != -1) && (HT[Hi] == NULLKEY)) {
                HC[Hi] = cnt.get();
                HT[Hi] = key; // 若单元Hi为空，放入
                return true;
            }
        }
        return false;
    }


    static void print(int HT[]) {
        for (int i = 0; i < m; i++)
            System.out.print(HT[i] + "\t");
        System.out.println();
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x;
        HT = new int[m];
        HC = new int[m];
        print(HT);
        System.out.println("输入12个关键字，存入哈希表中：");
        for (int i = 0; i < 12; i++) {
            x = scanner.nextInt();
            if (!InsertHash(HT, x)) {
                System.out.println("创建哈希表失败！");
                return;
            }
        }
        System.out.println("输出哈希表：");
        print(HT);
        print(HC);
        System.out.println("输入要查找的关键字");
        x = scanner.nextInt();
        int result = SearchHash(HT, x);
        if (result != -1)
            System.out.println("在第" + (result + 1) + "位置找到");
        else
            System.out.println("未找到");
        return;
    }
}

五 测试结果