Объединенный алгоритм удаления хэширования - PullRequest
Новая
       5

Объединенный алгоритм удаления хэширования

4 голосов
/ 13 июня 2011

Может кто-нибудь показать мне пример алгоритма удаления для объединенной объединенной хэш-таблицы?

Мой алгоритм вставки выглядит следующим образом: 

Insert (key) 
    int p = hash(key)
    if d[p] = NIL then
        d[p] = key
        next[p] = NIL
    else
        while next[p] != NIL 
            p = next[p]
        endwhile
        td[firstEmpty] = key
        next[p] = firstEmpty
        next[firstEmpty] = NIL
    endif
    UpdateFirstEmpty(); //sets firstEmpty to first empty slot with lowest index
endInsert

Скажем, количество слотов в таблицеравно 13. Хеш-функция возвращает ключ% 13. 

    Keys | 5 | 18 | 16 | 15 | 13 | 31 | 26 |      
Hash(key)| 5 |  5 |  3 |  2 |  0 |  5 |  0 |

После вставки их в таком порядке моя таблица будет выглядеть примерно так: 

index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
    d| 18| 13| 15| 16| 31|  5| 26| -1| -1| -1| -1| -1| -1|
 next|  1|  4| -1| -1|  6|  0| -1| -1| -1| -1| -1| -1| -1|

где -1 = NIL

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

Спасибо

РЕДАКТИРОВАТЬ: Я думаю, что я наконец получил это .. Я использую ту же технику, которую я использовал при удалении элемента из хеш-таблицы с открытым адресом.

ЭтоВот как это происходит: 

Search for key position and it's predecessor pp
    if key is found at position p
        if pp != NIL then 
             next[pp] = NIL  
        d[p] = NIL           //deletes the key
        p = next[p]          //move position to next value in the chain
        UpdateFirstEmpty()
        while d[p] != NIL do
            temp = d[p]      //save value
            d[p] = NIL       //delete value 
            p = next[p]      //move position to next value in chain
            UpdateFirstEmpty()
            Insert(temp)     //insert the value in the list again
        endwhile
   endif
endalg

index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
    d| 18| 13| 15| 16| 31|  5| 26| -1| -1| -1| -1| -1| -1|
 next|  1|  4| -1| -1|  6|  0| -1| -1| -1| -1| -1| -1| -1|
firstFree: 7

delete 18

index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
    d| 13| 31| 15| 16| 26|  5| -1| -1| -1| -1| -1| -1| -1|
 next|  4| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 6

delete 13

index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
    d| 26| 31| 15| 16| -1|  5| -1| -1| -1| -1| -1| -1| -1|
 next| -1| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 4

delete 26

index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
    d| -1| 31| 15| 16| -1|  5| -1| -1| -1| -1| -1| -1| -1|
 next| -1| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
firstFree: 0

Я не думаю, что это правильный способ сделать это, но, похоже, работает.Во всяком случае, я надеюсь, что поможет кому-то в будущем.

1 Ответ

0 голосов
/ 18 июля 2011

Одна вещь, которую мы можем сделать, чтобы упростить удаление, выглядит примерно так: предположим, что PP является родителем узла P (подлежит удалению).Так как мы знаем, что объединенное хеширование является комбинацией линейного зондирования и цепочки. Так что вместо того, чтобы сосать все элементы цепи после P вверх, мы можем просто поместить NULL в данные и следующий раздел P и ppopulate Next [PP] to Next [p].Поэтому в следующий раз, когда хеш-функция отображает какой-то ключ в это место, она может просто вставить его туда. Алгоритмы выглядят так: Удаление: 

Next[PP]=Next[P];  //as simple as deletion in link list without deleting node here
D[P]=NULL;
Next[P]=NULL;

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

...