两个用于存储整数的哈希表

Question

我正在尝试实现2个并行的哈希表，这些哈希表可以一起工作，特别是我想这样做：当我插入新的键x时，它将尝试将其插入表T1中。如果T1中的位置空闲，则执行插入。如果T1中的位置被键y占据，那么将替换现有键y，并将其插入另一个表中。如果T2中的位置被第三个键z占据，则键z位于T1中，依此类推。妙处在于，如果找到一个循环，则表的大小将增加1，然后通过重新插入新表中的所有元素来重新开始。如果N / M> = 1/2，则通过重新输入N个插入的元素，将表的大小加倍。

很显然，我已经写了帖子的基本结构。

我想表T1应该具有h1：11 k％M（对于整个k），而表T2 a h2：13 k％M（对于整个k）。]

但是我不知道如何连接我刚刚描述的所有功能。

我希望有人耐心帮助我，我在互联网上找不到代码示例，这给我带来了很多问题。 （对我而言，没有文档就很难学习新事物）

有人可以引导我吗？

公共类JumpHashing {

class HashEntry {

    String key;
    int value;    

    /* Constructor */
    HashEntry(String key, int value) {

        this.key = key;
        this.value = value;        
    }
}

class HashTable {

    private int TABLE_SIZE; //dimensions of the table
    private int size;   //number of key-value pairs 
    private HashEntry[] table;
    private int primeSize;

/* Constructor */
public HashTable(int ts) {

    size = 0;
    TABLE_SIZE = ts;

    table = new HashEntry[TABLE_SIZE];

    for (int i = 0; i < TABLE_SIZE; i++)
        table[i] = null;

    primeSize = getPrime();       
}

/* Function to get prime number less than table size for myhash2 function */
public int getPrime() {
    for (int i = TABLE_SIZE - 1; i >= 1; i--)
    {
        int fact = 0;
        for (int j = 2; j <= (int) Math.sqrt(i); j++)
            if (i % j == 0)
                fact++;
        if (fact == 0)
            return i;
    }
    /* Return a prime number */
    return 3;
}


public int getSize() {
    return size;
}

public boolean isEmpty(){
    return size == 0;
}

/* Function to clear hash table */
public void makeEmpty() {
    size = 0;
    for (int i = 0; i < TABLE_SIZE; i++)
        table[i] = null;
}


}}

我正在尝试实现2个并行的哈希表，这些哈希表可以一起工作，特别是我想这样做：当我插入新的键x时，它将尝试将其插入表T1中。如果T1中的位置为空，则...

Answer 1

首先，您应该弄清楚您要使用的哈希表算法。链式哈希表还是开放式哈希表？