Реализация операции вставки, двойного хеширования - PullRequest
Новая
       11

Реализация операции вставки, двойного хеширования

0 голосов
/ 02 мая 2020

Я должен реализовать конкретную операцию вставки. В основном я хочу создать 2 параллельные таблицы, управляемые 2 различными функциями ha sh. Когда вам нужно вставить новый ключ x, вы пытаетесь вставить его в таблицу T1. Если позиция T1 [h1 (x)] свободна, вставка выполняется. Если местоположение T1 [h1 (x)] занято ключом y (т. Е. H1 (x) = h1 (y)), то существующий ключ y заменяется, и он вставляется в другую таблицу. То есть y располагается в T2 [h2 (y)], если позиция T2 [h2 (y)] занята третьей клавишей z, клавиша z расположена в T1 [h1 (z)] и т. Д. , Если вы найдете al oop, размер таблиц увеличится на 1 и начнется заново, вставив все элементы в новую таблицу. Если N / M> = 1/2, размер таблицы удваивается, что делает вставку вставленных элементов N.

это мой базовый класс, очень традиционный, почти не имеет смысла покажи это тебе 

public class 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;
}}}

кто-нибудь может мне помочь? Я видел классовые c методы для вычисления sh примера 

int myhash1(String x )
{
    int hashVal = x.hashCode( );
    hashVal %= TABLE_SIZE;
    if (hashVal < 0)
        hashVal += TABLE_SIZE;
    return hashVal;
}

, но я не понимаю, как применить их к моей проблеме

Мой вопрос в основном : не могли бы вы объяснить мне, как установить две фикции для расчета га sh? И как установить вставку (изменение размеров таблиц, с которыми я сталкиваюсь, другими способами или внутри вставки? Чтобы повторно вставить элементы в таблицу, я вставляю цикл во вставку или это лучше выделенный метод? Как я могу заставить программу понять, есть ли al oop?)

...