Хэш-таблица с объединенным хешированием

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

Вот рассматриваемый метод добавления,

public boolean add(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(array, currentPos))
        return false;
    if (array[currentPos] == null)
        occupied++;
    array[currentPos] = new HashEntry(x, true);
    currentSize++;
    modCount++;
    if (occupied > array.length / 2)
        rehash();
    return true;
}

Если бы кто-нибудь мог показать мне, как этот метод можно преобразовать для использования объединенного хеширования, я был бы очень признателен.


java hashtable hash-collision
person Community    schedule 10.09.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

public boolean add(AnyType x) {
    // Finds the place that you want to insert into your table.
    // I believe the function contains the hash mapping
    int currentPos = findPos(x);
    // if the place is empty, you will insert your hash in there
    if (array[currentPos] == null) {
        array[currentPos] = new HashEntry(x, true);
    } else {
        // The place has been occupied (collision occured), so we will 
        // add it as a second item like a link list.
        // But, we do not want to allocate a new space and we use the 
        // empty spaces we have in our hash table instead.
        // That is the differece between coalesced hash and speparate chaining

        // the indexes are from 0 to HASH_TABLE_SIZE -1
        int cursor = HASH_TABLE_SIZE - 1; 
        /* Find the first empty bucket for the new entry */
        while ( cursor >= 0 && array[cursor] != NULL )
            --cursor;

        /* The table is full, terminate unsuccessfully */
        if ( cursor == -1 )
          return false;

        // Initial your new value in an empty bucket we found in the table
        array[cursor] = new HashEntry(x, true);

        /* Find the last node in the chain and point to it */
        // Here we need to find the tail of the link list in our hash table
        // We do not want to miss the link list that we made from the past,
        // therefore, we need to do the following
        struct node* it = array[currentPos];
        while ( it->next != NULL )
          it = it->next;
        // Now we assign the 
        it->next = array[cursor];       
    }
    return true;
}

Я надеюсь, что это помогает.

person Mahsa2    schedule 10.09.2015
comment
Это должно быть с использованием C? Язык, с которым я работаю, — Java. Хотя это выглядит правильно для C, я не знаю, что делать с struct node. Можете ли вы привести пример Java? - person ; 10.09.2015
comment
поэтому в java вместо struct node* вам нужно указать тип массива, который у вас есть. например это может быть массив объектов «Node», к которым у него есть доступ. Вы можете взглянуть на crunchify.com / , 'частный класс Node', чтобы увидеть, каким может быть тип массива + как его изменить — далее с помощью getNext(). - person Mahsa2; 10.09.2015
comment
Чтобы добавить к предыдущему комментарию: я не думаю, что у меня есть связанный список из прошлого, как вы сказали. У меня есть только array класса HashEntry. - person ; 10.09.2015
comment
Таким образом, каждый элемент в вашей таблице будет экземпляром класса Node. Ссылка, которую я отправлю вам, поможет вам понять, как работают списки узлов и ссылок. - person Mahsa2; 10.09.2015
comment
Я добавил pastebin типа моего массива (HashEntry). pastebin.com/CQPsqZMS Выглядит как связанный список, только без доступа к следующему элементу . Извините за то, что я очень новичок, как вы можете видеть, мне трудно понять. - person ; 10.09.2015
comment
Чтобы реализовать объединенную хеш-таблицу, вам нужно изменить класс HashEntry, чтобы он имел те же функции, что и класс «Node», о котором я упоминал, потому что вам нужна таблица списка ссылок для этого хэша. - person Mahsa2; 10.09.2015
comment
Давайте продолжим обсуждение в чате. - person ; 10.09.2015