Open address method hash implementation - secondary detection method

一 点睛

The secondary detection method refers to the method of detecting by jumping back and forth,发生冲突时,向后 1 位探测,向前 1 位探测,向后 4 位探测,向前 4 位探测......Probe by jumping,避免堆积.

The incremental sequence of secondary detection is  d=1,-1,4,-4,9,-9

二 需求

有一组关键字{14 36 42 38 40 15 19 12 51 65 34 25},若表长为 15,散列函数为hash(key) = key % 13,Then the second detection method can be used to deal with the conflict,构造散列表.

三 final detection result

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

四 实现

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 Seconddetect(int HT[], int H0, int key, AtomicInteger cnt) {
        int Hi;
        for (int i = 1; i <= m / 2; ++i) {
            int i1 = i * i;
            int i2 = -i1;
            cnt.getAndIncrement();
            Hi = (H0 + i1) % m; // Calculate the next hash address according to the linear probing method Hi
            if (HT[Hi] == NULLKEY)// 若单元 Hi 为空,则所查元素不存在
                return Hi;
            else if (HT[Hi] == key)//若单元Hi中元素的关键字为key
                return Hi;
            cnt.getAndIncrement();
            Hi = (H0 + i2) % m; // Calculate the next hash address according to the linear probing methodHi
            if (Hi < 0)
                Hi += m;
            if (HT[Hi] == NULLKEY) // 若单元 Hi 为空,则所查元素不存在
                return Hi;
            else if (HT[Hi] == key) // 若单元 Hi 中元素的关键字为 key
                return Hi;
        }
        return -1;
    }


    static int SearchHash(int HT[], int key) {
        // 在哈希表HT中查找关键字为 key 的元素,若查找成功,Returns the element number of the hash table,否则返回 -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 = Seconddetect(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 = Seconddetect(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("Failed to create hash table！");
                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;
    }
}

五 测试

绿色为输入,白色为输出.