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

Question

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

Вот метод добавь в вопросе,

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

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

Answer 1

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

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

Надеюсь, это поможет.