Отдельный хэш цепочки с методом цепочки для цикла в методе Put () - PullRequest
Новая
       37

Отдельный хэш цепочки с методом цепочки для цикла в методе Put ()

0 голосов
/ 02 октября 2019

У меня проблемы с пониманием этого фрагмента кода в цикле for. Он использует цепочку методов, чтобы решить, какой LinkedList должна быть размещена пара ключ / значение.

Я начинаю понимать идею, лежащую в основе HashTable с отдельной цепочкой, или, в данном случае, HashTable с двумя зондами. У нас есть начальный связанный список, который хранит наши пары ключ / значение в индексе, определенном нашей хэш-функцией. Чтобы реализовать разрешение конфликтов, мы должны назначить LinkedList каждому индексу нашего исходного LinkedList и создать две отдельные хеш-функции для каждой передаваемой пары ключ / значение. если происходит столкновение, мы реализуем код, чтобы решить, будет ли первая или вторая хеш-функция генерировать значение / индекс с наименьшим количеством цепочек, добавленных к индексу, и поместим нашу пару ключ / значение в этот индекс. Код ниже я частично написал сам, а частично нашел из других источников. Что меня смущает, так это операторы if внутри циклов for в моем методе «updatePut». См. Ниже: 

public void put(Key key, Value value) {
    if (updatePut(key, value)) {
        return;
    }

    smallerList(key).add(new Entry(key, value));
    N++;

}
private boolean updatePut(Key key, Value value) {

для (int i = 0; i <записи [хэш (ключ)]. Size (); i ++) {</h1> if (записи [хэш (ключ))] .get (i) .key.equals (ключ)) {

записей [хэш (ключ)]. get (i) .value = значение; 

            return true;

        }
    }

    for (int i = 0; i < entries[hashTwo(key)].size(); i++) {
        if (entries[hashTwo(key)].get(i).key.equals(key)) {
            entries[hashTwo(key)].get(i).value = value;
            return true;
        }
    }
    return false;
}
private LinkedList<Entry> smallerList(Key key) {
    if (entries[hash(key)].size() > entries[hashTwo(key)].size())
        return entries[hashTwo(key)];

    return entries[hash(key)];
}

@Override
public Value get(Key key) {

    for (int i = 0; i < entries[hash(key)].size(); i++) {
        if (entries[hash(key)].get(i).key.equals(key))
            return (Value) entries[hash(key)].get(i).value;
    }

    for (int i = 0; i < entries[hashTwo(key)].size(); i++) {
        if (entries[hashTwo(key)].get(i).equals(key))
            return (Value) entries[hashTwo(key)].get(i).value;
    }

    return null;
}

Итак, я получаючто int i = 0 используется для определения того, сколько цепочек мы прикрепили к каждому индексу, но почему мы используем 'int i' в нашем вызове метода get ()? Кажется, что было бы более разумно вызывать get () для индекса, созданного методом хеширования, чтобы проверить и посмотреть, занят ли он уже. Я могу только предположить, что мой мыслительный процесс по этому вопросу некорректен, потому что код работает просто отлично. Кто-нибудь, пожалуйста, объясните мне, как будто мне 5 лет! Чем детальнее, тем лучше.

...