Как C++ STL unordered_map разрешает коллизии?
Как C++ STL unordered_map разрешает коллизии?
Глядя на http://www.cplusplus.com/reference/unordered_map/unordered_map/, он говорит: "Уникальные ключи. У двух элементов в контейнере не может быть эквивалентных ключей".
Это должно означать, что контейнер действительно разрешает столкновения. Однако эта страница не говорит мне, как она это делает. Я знаю несколько способов разрешения коллизий, таких как использование связанных списков и / или исследование. То, что я хочу знать, - то, как C++ STL unordered_map разрешает это.
1 ответ
Стандарт определяет немного больше об этом, чем кажется большинству людей.
В частности, стандарт требует (§23.2.5/9):
Элементы неупорядоченного ассоциативного контейнера организованы в сегменты. Ключи с одинаковым хеш-кодом появляются в том же сегменте.
Интерфейс включает в себя bucket_count это работает в постоянном времени. (таблица 103). Он также включает в себя bucket_size это должно бежать во времени, линейном по размеру ковша.
Это в основном описывает реализацию, которая использует цепочку столкновений. Когда вы используете цепочку столкновений, выполнение всех требований находится где-то между легким и тривиальным. bucket_count() это количество элементов в вашем массиве. bucket_size() количество элементов в цепочке столкновений. Получить их в постоянное и линейное время соответственно просто и понятно.
Напротив, если вы используете что-то вроде линейного зондирования или двойного хеширования, эти требования практически невозможно выполнить. В частности, все элементы, которые хэшируются до определенного значения, должны попадать в одно и то же ведро, и вы должны иметь возможность считать эти ведра в постоянное время.
Но если вы используете что-то вроде линейного зондирования или двойного хеширования, то обнаружение всех элементов, хэшированных с одним и тем же значением, означает, что вам нужно хэшировать значение, а затем пройтись по "цепочке" непустых элементов в вашей таблице, чтобы узнать, сколько из тех, кто хэшируется до того же значения. Это не является линейным по количеству элементов, которые хэшируются до одного и того же значения - это линейно по количеству элементов, которые хэшируются к одному и тому же или сталкивающимся значениям
При достаточной дополнительной работе и значительном расширении смысла некоторых требований почти до критической точки, едва ли возможно создать хеш-таблицу, использующую что-то отличное от цепочки столкновений, и все же, по крайней мере, что-то вроде удовлетворения требований. Но я не совсем уверен, что это возможно, и это наверняка потребует много дополнительной работы.
Резюме: все практические реализации std::unordered_set (или же unordered_map) несомненно использовать цепочку столкновений. Хотя было бы возможно (едва ли) возможно удовлетворить требования с помощью линейного зондирования или двойного хеширования, такая реализация, похоже, теряет много и почти ничего не получает взамен.
Я нашел этот ответ в поисках того, как определить, когда мои типы сталкиваются, поэтому я опубликую его на тот случай, если это является целью вопроса.
Я полагаю, что существует некоторое неправильное представление о "уникальных ключах. Никакие два элемента в контейнере не могут иметь эквивалентные ключи".
посмотрите на код ниже
//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 и придется перебирать
Надеюсь, этот код можно прочитать без контекста, с которым я его сгенерировал. он в основном проверяет, является ли какой-либо элемент в корзине, связанный с хешем, тем элементом, который я ищу.
//sp is std::shared_ptr
//memo is std::unordered_multimap< int, sp<AStarNode> >
//there's 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;
}
Скорее всего, цепочкой. Одним из эффективных способов разрешения коллизий в хэш-картах является реализация его с помощью связанного списка. Таким образом, если запись заканчивается столкновением с другим хешем, она просто добавит ее в узел указателя сопоставленной записи. Я объясню с кодом.
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;
Как вы можете видеть из последней части. Когда вы получите хеш-значение, в которое будет помещена ваша запись, мы сначала добавим узел pNext указатель указывает на что угодно ppTable[hash] уже есть; если он нулевой, указатель будет нулевым в любом случае. После установки указателя узла мы устанавливаем узел в качестве значения и приращения нового хеш-индекса uiCount как мы успешно разместили новую запись.