Последний пришел, первый обслужен или Робин Гуд - PullRequest
Новая
       23

Последний пришел, первый обслужен или Робин Гуд

0 голосов
/ 28 марта 2020

Я пытаюсь вставить строки в хеш-таблицу. Это задача:

Если индекс в таблице ha sh уже используется:

  • Либо расположенный там элемент данных перемещается на один шаг вправо », оставляя свободное пространство для вставляемого элемента (как в случае хэширования« последний пришел, первый обслужен »),

  • Или расположенный там элемент данных не должен быть переместился, и вместо этого мы пытаемся вставить следующий индекс в таблицу (как при обычном линейном зондировании).

Пусть T будет элементом данных, уже находящимся в таблице и S будет элементом, который мы пытаемся вставить. Мы выбираем вариант 1 выше (чтобы переместить T вправо), если S теперь отошел от своего первоначального значения ha sh index , чем T. Если мы не выбрали альтернативу 2 .

Этот процесс повторяется до тех пор, пока нам больше не нужно перемещать элементы данных «на ступеньку вправо» (мы найдем свободное место в таблице).

Хорошо, так вот код, который я до сих пор (это не работает). Смотрите отметки о том, что мне не хватает: 

int hash(String S) {
    int h = Math.abs(S.hashCode());
    return h % hashLength;
}

        // Innserting String, exits with error message if table is full 
void insert(String S) {
    int h = hash(S); // Calculates hash value
    int next= h;  // Linear probing

    String t_existingEntry; //  element already on that index
    String s_toBeInserted = S; // element I try to put in

    // Probe Sequence Length (PSL) is how many times a node has been tried to be put in (?) 
    int s_moved = 0; // PSL for s
    int t_moved = 0; // PSL for t

    int pos_toS = next - hash(S); // calculate how far an element have moved (?)

    while (hashTable[next] != null) {
        t_existingEntry = hashTable[next]; // copied hashTable[next] and stores it in t_existingEntry 

        numProbes++;    

        // 1.1 Calculate 's_toBeInserted' distance from original index
        // 1.2 Adjust for wraparound

        // 2.1 Calculate element on index 'next' from original index
        // 2.2 Adjust for wraparound    

        // 3   If 's_toBeInserted' have moved longer/further

        // 3.1 Insert 's_toBeInserted'    




         neste++;

         if (next >= hashLength) // Wrap-around
             neste = 0;

         // If returned to original hash value, the table is full. Don't do rehashing here (it's not part of the task)
        if (next== h) {
            System.err.println("\nHash table full, exits");
                System.exit(0);
        }

        // Linear probing, alternative 2: 
        hashTable[next] = s_toBeInserted; // Saves String S on next available index

        n++; // Øker antall elementer som er lagret
      }
   }
 }

Здесь фигурные скобки могут быть неправильными, это всего лишь фрагмент кода. Я довольно новичок в программировании, и это было очень сложно, поэтому, если у кого-то есть какие-либо советы или примеры, заранее спасибо :) И извините за мой engli sh, это не мой родной язык, код был переведен.

...