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

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

1 голос
/ 10 апреля 2010

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

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  ********
    }
}

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

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

1 Ответ

3 голосов
/ 10 апреля 2010

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

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

  • v, значение объекта, используемого для вычисления хеш-кода.
  • t, это i*f, где i, называемый stepsize , - это то, что вы добавляете каждый раз к своей хэш-функции, если происходит столкновение, и 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), что отличается функцией хеширования, которая придаст различный вес размер шага.

...