¿Cómo resuelve el mapa desordenado C++ STL las colisiones?
¿Cómo resuelve las colisiones C++ STL unordered_map?
Mirando el http://www.cplusplus.com/reference/unordered_map/unordered_map / , dice " Claves únicas No hay dos elementos en el contenedor que puedan tener claves equivalentes."
Eso debería significar que el contenedor está resolviendo colisiones. Sin embargo, esa página no me dice cómo lo está haciendo. Conozco algunas formas de resolver colisiones como usar listas enlazadas y/o sondeo. Lo que quiero saber es cómo el c++ STL unordered_map lo está resolviendo.
2 answers
El estándar define un poco más sobre esto de lo que la mayoría de la gente parece darse cuenta.
Específicamente, el estándar requiere (§23.2.5/9):
Los elementos de un contenedor asociativo desordenado se organizan en cubos. Las claves con el mismo código hash aparecen en el mismo cubo.
La interfaz incluye un bucket_count que se ejecuta en tiempo constante. (cuadro 103). También incluye un bucket_size que tiene que ejecutarse en tiempo lineal en el tamaño del cubo.
Eso es básicamente describe una implementación que usa encadenamiento de colisión. Cuando se utiliza el encadenamiento de colisión, cumplir con todos los requisitos es entre fácil y trivial. bucket_count() es el número de elementos en su matriz. bucket_size() es el número de elementos en la cadena de colisión. Obtenerlos en tiempo constante y lineal respectivamente es simple y directo.
Por el contrario, si se usa algo como sondeo lineal o doble hash, esos requisitos se vuelven casi imposibles de cumplir. En concreto, todos los elementos que se cifran en un valor específico deben aterrizar en el mismo cubo, y debe poder contar esos cubos en tiempo constante.
Pero, si usa algo como sondeo lineal o doble hash, encontrar todos los elementos que tienen hash al mismo valor significa que necesita hash el valor, luego camine a través de la "cadena" de elementos no vacíos en su tabla para encontrar cuántos de ellos tienen hash al mismo valor. Eso no es lineal en el número de elementos que hash a la sin embargo, el mismo valor linear es lineal en el número de elementos que se cifran en el mismo o un valor de colisión.
Con suficiente trabajo extra y una buena cantidad de estirar el significado de algunos de los requisitos casi hasta el punto de ruptura, podría ser apenas posible crear una tabla hash usando algo que no sea el encadenamiento de colisión, y aún así, al menos, cumplir con los requisitos--pero no estoy realmente seguro de que sea posible, y trabajo.
Resumen: todas las implementaciones prácticas de std::unordered_set (o unordered_map) indudablemente usan encadenamiento de colisión. Si bien podría ser (apenas) posible cumplir con los requisitos utilizando el sondeo lineal o el doble hashing, tal implementación parece perder mucho y no ganar casi nada a cambio.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-31 22:29:53
Probablemente encadenando. Una forma efectiva de resolución de colisión de hashmap es implementarla con una lista vinculada. Por lo tanto, si una entrada termina en colisión con otro hash, simplemente lo agregará al nodo puntero de la entrada colisionada. Te lo explicaré con código.
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;
Como se puede ver en la última parte. Cuando obtiene el valor hash en el que se colocará su entrada, primero colocamos el puntero pNext del nodo para apuntar a lo que ppTable[hash] ya tiene; si es nulo, el puntero será nulo de cualquier manera. Después de establecer el puntero del nodo, establecemos el nodo como el valor del nuevo índice hash e incrementamos uiCount a medida que colocamos con éxito una nueva entrada.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-31 22:38:45