Помогите с хеш-таблицами и квадратичным зондированием в Java

Question

Мне действительно нужна помощь по вставке в хэш-таблицу. Я просто не совсем понял это прямо сейчас. Может ли кто-нибудь объяснить квадратичное и линейное зондирование в терминах непрофессионала?

public void insert(String key)
{
    int homeLocation = 0;
    int location = 0;
    int count = 0;

    if (find(key).getLocation() == -1)  // make sure key is not already in the table
    {
       //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING  ********
    }
}

Это код, над которым я работаю. Я не прошу никого делать это, мне просто нужна помощь в изучении всей концепции

Любая помощь будет принята с благодарностью.

Answer 1

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

Итак, у вас есть функция хеширования с двумя параметрами:

• vзначение объекта, используемого для вычисления хэш-кода.
• t, его i*f где i, называемый stepize, - это то, что вы добавляете каждый раз к своей хэш-функции, если происходит столкновение и f количество столкновений, достигнутых до настоящего времени.

Исходя из этого у вас есть две возможные функции:

H(v, t) = (H(v) + t) % n
H(v, t) = (H(v) + c*t + d*t*t) % n

Первая - это линейная функция, а вторая - квадратичная (здесь речь идет о названиях этой техники)... где вы должны знать, что % n является, c а также d выбираются константы, чтобы иметь лучшую хэш-функцию..

Практически говоря для линейного зондирования:

• Вы рассчитываете H(x, 0)
• • если ячейка свободна, поместите элемент туда
• • если ячейка занята, рассчитать H(x, i)
• • • если ячейка свободна, поместите элемент в новый адрес
• • • если клетка занята, то рассчитать H(x, i+i)
• • • • продолжайте, пока не найдете пустую клетку

для квадратичного зондирования то, что вы делаете, идентично, вы начинаете с H(x,0), затем H(x,i) затем H(x,i+i)отличается то, что задействована функция хеширования, которая придаст разный вес размеру шага.