Как С++ STL unordered_map разрешает конфликты?

Ответ 1

Стандарт определяет немного больше об этом, чем кажется большинству людей.

В частности, стандарт требует (§23.2.5/9):

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

В интерфейс входит bucket_count, который работает в постоянное время. (таблица 103). Он также включает bucket_size, который должен выполняться со временем линейным по размеру ведра.

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

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

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

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

Резюме: все практические реализации std::unordered_set (или unordered_map), несомненно, используют цепочку столкновений. Хотя это может быть (едва ли) возможно удовлетворить требованиям с использованием линейного зондирования или двойного хэширования, такая реализация, похоже, теряет много и почти ничего не получает взамен.

Ответ 2

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

typedef struct mapnode {
    const char *strKey;
    void *pData;
    struct mapnode *pNext;
} mapnode_t;

typedef struct hashmap {
    mapnode_t **ppTable;
    unsigned uiLength; // how big is the table?
    unsigned uiCount; // how many entries do we really have?
} hashmap_t;

// excerpt from hashmap_insert
mapnode_t *node = malloc( sizeof(mapnode_t) );
if( !node ) {
    printf("**** Memory Allocation Error **** hashmap_insert::node is NULL\n");
    return false;
}
node->strKey = szKey;
node->pData = pData;

unsigned hash = gethash(szKey) % d->uiLength;
node->pNext = d->ppTable[hash];
d->ppTable[hash] = node;
++d->uiCount;

Как вы можете видеть из последней части. Когда вы получите хеш-значение, в которое будет помещена ваша запись, мы сначала заменим указатель node pNext на то, чтобы указать, что уже есть ppTable[hash]; если он равен нулю, указатель будет пустым в любом случае. После установки указателя node мы устанавливаем node в качестве нового значения индекса хэша и increment uiCount, поскольку мы успешно разместили новую запись.

Ответ 3

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

Я считаю, что существует некоторое неправильное представление о "уникальных ключах. Никакие два элемента в контейнере не могут иметь эквивалентные ключи".

посмотрите на код ниже

//pseudocode
std::unordered_map<int, char> hashmap;
hashmap[5] = 'a';
hashmap[5] = 'b'; //replace 'a' with 'b', there is no collision being handled.

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

Если вы хотите, чтобы коллизии обрабатывались для ваших типов (с std::unordered_multimap), вам нужен std::unordered_multimap и вам придется перебирать

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

//sp is std::shared_ptr
//memo is std::unordered_multimap< int, sp<AStarNode> >

//there probably multiple issues with this code in terms of good design (like using int keys rather than unsigned)

bool AStar_Incremental::hasNodeBeenVisited(sp<AStarNode> node)
{
    using UMIter = std::unordered_multimap<int, sp<AStarNode> >::iterator;

    bool bAlreadyVisited = false;

    //get all values for key in O(1*)
    int hash = WorldGrid::hashGrid(node->location);
    std::pair<UMIter, UMIter> start_end = memo.equal_range(hash); //bucket range
    UMIter start = start_end.first;
    UMIter end = start_end.second;

    //hopefully this is implemented to be O(m) where m is the bucket size.
    for(UMIter bucketIter = start; bucketIter != end; ++bucketIter)
    {
        sp<AStarNode> previousNode = bucketIter->second;
        sf::Vector2i& previousVisit = previousNode->location;
        if (previousVisit == node->location)
        {
            bAlreadyVisited = true;
            break;
        }
    }

    return bAlreadyVisited;
}