c++ - resolucion - tablas hash en java

¿Cuál es la función hash más rápida para los punteros? (5)

Después de dejar esta pregunta por un tiempo, publicaré mi mejor función hash para los punteros hasta ahora:

template<typename Tval> struct MyTemplatePointerHash1 { size_t operator()(const Tval* val) const { static const size_t shift = (size_t)log2(1 + sizeof(Tval)); return (size_t)(val) >> shift; } };

Es de alto rendimiento para varios tamaños de bloques.
Si alguien tiene una función mejor, cambiaré la respuesta aceptada.

Los contenedores basados en la tabla Hash son una matriz asociativa muy rápida (por ejemplo, unordered_set , unordered_set ).

Su rendimiento depende en gran medida de la función hash utilizada para crear un índice para cada entrada. A medida que crecen las tablas hash, los elementos se repiten una y otra vez.

Los punteros son de tipo simple, básicamente un valor de 4/8 bytes que identifica de manera única un objeto. El problema es que usar una dirección como resultado de la función hash no es eficiente debido a que varios LSB son cero.

Ejemplo:

struct MyVoidPointerHash { size_t operator()(const void* val) const { return (size_t)val; } };

Una implementación más rápida es perder algunos bits:

struct MyVoidPointerHash2 { size_t operator()(const void* val) const { return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit } };

Este último produjo un aumento del 10-20% en el rendimiento en una aplicación de gran tamaño que usa conjuntos de hash y mapas con decenas de miles de elementos que se crean y eliminan con frecuencia.

¿Alguien puede ofrecer un mejor esquema para los indicadores hash?

La función debe ser:

¡Rápido! y debe alinear bien.
Ofrezca una distribución razonable, se permiten colisiones raras.

Actualización: resultados de referencia

Ejecuté dos juegos de pruebas, uno para int* y un puntero de clase que tiene un tamaño de 4 KB. Los resultados son muy interesantes.

std::unordered_set para todas las pruebas con un tamaño de datos de 16 MB asignado en una sola llamada new . El primer algoritmo se ejecutó dos veces para asegurarse de que los cachés estén lo más calientes posible y la CPU esté funcionando a toda velocidad.

Configuración: VS2013 (x64), i7-2600, Windows 8.1 x64.

Función hash predeterminada VS2013
Hash1: return (size_t)(val);
Hash2: return ''(size_t)(val) >> 3;
Hash3 (@BasileStarynkevitch): uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15)); uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15));
Hash4 (@Roddy): uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16)); uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16));
Hash5 (@egur):

Código:

template<typename Tval> struct MyTemplatePointerHash1 { size_t operator()(const Tval* val) const { static const size_t shift = (size_t)log2(1 + sizeof(Tval)); return (size_t)(val) >> shift; } };

Prueba 1 - int* :

El valor predeterminado de VS2013 fue 1292ms
Hash1 tomó 742ms
Hash2 tomó 343ms
Hash3 tomó 1008ms
Hash4 tomó 629ms
Hash5 tomó 350ms

Prueba 1 - 4K_class* :

El valor predeterminado de VS2013 tomó 0.423ms
Hash1 tomó 23.889ms
Hash2 tomó 6.331ms
Hash3 tomó 0.366ms
Hash4 tomó 0.390ms
Hash5 tomó 0.290ms

Actualización2:

El ganador hasta ahora es la función hash templada (Hash5). El mejor nivel de rendimiento para la velocidad para varios tamaños de bloques.

Actualización 3: Se agregó la función hash predeterminada para la línea base. Resulta que está lejos de ser óptimo.

El resultado devuelto por la función hash tiene tipo size_t , pero el contenedor lo convierte en un ''índice de cubo'', identificando el cubo correcto para ubicar el objeto.

Creo que esta conversión no está especificada en el estándar: pero espero que esto sea generalmente una operación Modulo N, donde N es el número de cubos, y que N es típicamente una potencia de dos, ya que duplicar el conteo de cubos es bueno. forma de aumentar el tamaño cuando hay demasiados golpes. La operación Modulo N significa que, para los punteros, la función hash ingenua solo usa una fracción de los intervalos.

El verdadero problema es que un algoritmo de hash "bueno" para contenedores debe basarse en el conocimiento del tamaño del cubo y los valores que está mezclando. Por ejemplo, si los objetos que estaba almacenando en la tabla son todos de 1024 bytes de tamaño, es posible que los 10 bits de menor orden de cada puntero sean los mismos.

struct MyOneKStruct x[100]; //bottom 10 bits of &x[n] are always the same

Por lo tanto, un ''mejor'' hash para cualquier aplicación probablemente requiera mucho ensayo y error y medición, y el conocimiento de la distribución de los valores que has hashing.

Sin embargo, en lugar de simplemente desplazar el puntero hacia N bits, probaría algo como XORingar la ''palabra'' superior en la inferior. Al igual que la respuesta de @ BasileStarynkevich.

La propuesta de agregar tablas hash es interesante. Mi énfasis en el siguiente párrafo: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html

Es imposible escribir una función hash completamente general que sea válida para todos los tipos. (No se puede simplemente convertir un objeto a memoria sin procesar y cortar los bytes, entre otras razones, esa idea falla debido al relleno). Por eso, y también porque una buena función de hash solo es buena en el contexto de un uso específico patrón, es esencial permitir a los usuarios proporcionar sus propias funciones hash.

La respuesta correcta desde un punto de vista teórico es: "Use std::hash que probablemente esté especializado para ser tan bueno como sea posible, y si eso no es aplicable, use una buena función hash en lugar de una rápida. la función hash no importa tanto como su calidad " .

La respuesta práctica es: "Use std::hash , que es pobre en orina, pero de todos modos funciona sorprendentemente bien".

TL; DR
Después de haberme sentido intrigado, corrí alrededor de 30 horas de puntos de referencia durante el fin de semana. Entre otras cosas, traté de obtener un caso promedio vs. el peor de los casos y traté de forzar a std::unordered_map en el peor de los casos dándole deliberadamente malas pistas sobre el recuento de cubos con respecto al tamaño del conjunto insertado.

Cometí los hashes pobres ( std::hash<T*> ) con hash de propósito general bien conocidos de buena calidad general (djb2, sdbm), así como las variaciones de estos que representan la longitud de entrada muy corta, y los hash que son se piensa explícitamente que se usa en hashtables (murmur2 y murmur3), y hashes pobres en orina que en realidad son peores que no hashing, ya que tiran la entropía.
Como los 2-3 bits más bajos siempre son cero en los punteros debido a la alineación, consideré que valía la pena probar un simple desplazamiento a la derecha como "hash", por lo que solo se usaría la información distinta de cero, en caso de que la tabla hash solo se usara los N bits más bajos. Resultó que por turnos razonables (¡también intenté cambios irrazonables!), En realidad funciona bastante bien.

Recomendaciones

Algunos de mis hallazgos fueron bien conocidos y nada sorprendentes, otros son muy sorprendentes:

Es difícil predecir qué es un hash "bueno". Escribir buenas funciones hash es difícil. No es sorprendente, hecho bien conocido, y una vez más probado.
Ningún hash supera significativamente a todos los demás en todos los escenarios. Ningún hash incluso supera significativamente a todos los demás el 80% del tiempo. El primer resultado fue esperado, el segundo es sin embargo sorprendente.
Es realmente difícil presionar std::unordered_map para comportarse mal. Incluso cuando se dan deliberadamente malas pistas para el recuento de cubos que forzará varias repeticiones, el rendimiento general no es mucho peor. Solo las peores funciones hash que eliminan la mayor parte de la entropía de una manera casi ridícula pueden afectar significativamente el rendimiento en más del 10-20% (como right_shift_12 , que prácticamente resulta en solo 12 valores de hash distintos para 50,000 entradas). no es de extrañar que el mapa hash se ejecute unas 100 veces más lento en este caso; básicamente estamos haciendo búsquedas de acceso aleatorio en una lista vinculada).
Algunos resultados "divertidos" seguramente se deben a los detalles de implementación. Mi implementación (GCC) usa un recuento de cubos primos ligeramente más grande que 2 ^ N, e inserta valores con hashes indentical de cabeza en listas enlazadas.
La especialización de std::hash<T*> es francamente patética para GCC (un simple reinterpret_cast ). Curiosamente, un functor que hace lo mismo constantemente realiza más rápido en las inserciones y más lento en el acceso aleatorio . La diferencia es pequeña (una docena de milisegundos en una ejecución de prueba de 8-10 segundos), pero no es ruido, es constante, probablemente relacionado con el reordenamiento de la instrucción o el pipeline. Es sorprendente cómo exactamente el mismo código (que también es no operativo) tiene un rendimiento consistente en dos escenarios diferentes.
Los hashes patéticos no tienen un rendimiento significativamente peor que los hashes o hashes "buenos" explícitamente diseñados para tablas hash. De hecho, la mitad de las veces son los mejores intérpretes o están entre los 3 mejores.
Las "mejores" funciones de hash rara vez dan como resultado el mejor rendimiento general.
Los hashes publicados como respuestas en esta pregunta SO generalmente son correctos. Son buenos promedios, pero no superiores a std::hash . Por lo general, aterrizarán entre los primeros 3-4.
Los valores hash pobres son algo vulnerables al orden de inserción (peor en inserción aleatoria y búsqueda aleatoria después de la inserción aleatoria) mientras que los valores "buenos" son más resistentes al impacto del orden de inserción (poca o ninguna diferencia), pero el rendimiento general es aún un poco más lento.

Configuración de prueba

Se realizaron pruebas no solo de valores alineados de 4 bytes u 8 bytes (o lo que sea), sino de direcciones reales obtenidas de la asignación del conjunto completo de elementos en el almacenamiento dinámico y el almacenamiento de las direcciones proporcionadas por el asignador en un std::vector (los objetos fueron eliminados, no son necesarios).
Las direcciones se insertaron en un std::unordered_map recientemente asignado para cada prueba en el orden almacenado en el vector, una vez en el orden original ("secuencial") y una vez después de aplicar un std::random_shuffle en el vector.

Las pruebas se realizaron para conjuntos de 50,000 y 1,000,000 objetos de tamaño 4, 16, 64, 256 y 1024 (los resultados para 64 se omiten aquí por brevedad, son como se esperaría en algún lugar en el medio entre 16 y 256 - solo permite la publicación de 30k caracteres).
El conjunto de pruebas se realizó 3 veces, los resultados varían en 3 o 4 milisegundos aquí y allá, pero en general son idénticos. Los resultados publicados aquí son la última ejecución.

El orden de las inserciones en la prueba "aleatoria", así como el patrón de acceso (en cada prueba) es pseudoaleatorio, pero exactamente idéntico para cada función hash en una ejecución de prueba.

Los tiempos bajo los puntos de referencia hash son para sumar 4.000,000,000 de valores hash en una variable entera.

El insert columna es el tiempo en milisegundos para 50 iteraciones de creación de un std::unordered_map , insertando 50,000 y 1,000,000 de elementos respectivamente, y destruyendo el mapa.

El access columna es el tiempo en milisegundos para hacer 100.000,000 búsquedas de un elemento pseudoaleatorio en el ''vector'' seguido de buscar esa dirección en el unordered_map .
Este tiempo incluye en promedio un error de caché para acceder a un elemento aleatorio en el vector , al menos para el conjunto de datos grande (el conjunto de datos pequeño se ajusta completamente a L2).

Todos los tiempos en un 2.66 GHz Intel Core2, Windows 7, gcc 4.8.1 / MinGW-w64_32. Granularidad del temporizador a 1 ms.

Código fuente

El código fuente está disponible en Ideone , nuevamente debido al límite de 30k caracteres de .

Nota: ejecutar el conjunto de pruebas completo lleva más de 2 horas en una PC de escritorio, así que prepárese para dar un paseo si quiere reproducir los resultados.

Resultados de la prueba

Benchmarking hash funcs... std::hash 2576 reinterpret_cast 2561 djb2 13970 djb2_mod 13969 sdbm 10246 yet_another_lc 13966 murmur2 11373 murmur3 15129 simple_xorshift 7829 double_xorshift 13567 right_shift_2 5806 right_shift_3 5866 right_shift_4 5705 right_shift_5 5691 right_shift_8 5795 right_shift_12 5728 MyTemplatePointerHash1 5652 BasileStarynkevitch 4315 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 421 6988 reinterpret_cast 408 7083 djb2 451 8875 djb2_mod 450 8815 sdbm 455 8673 yet_another_lc 443 8292 murmur2 478 9006 murmur3 490 9213 simple_xorshift 460 8591 double_xorshift 477 8839 right_shift_2 416 7144 right_shift_3 422 7145 right_shift_4 414 6811 right_shift_5 425 8006 right_shift_8 540 11787 right_shift_12 1501 49604 MyTemplatePointerHash1 410 7138 BasileStarynkevitch 445 8014 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 443 7570 reinterpret_cast 436 7658 djb2 473 8791 djb2_mod 472 8766 sdbm 472 8817 yet_another_lc 458 8419 murmur2 479 9005 murmur3 491 9205 simple_xorshift 464 8591 double_xorshift 476 8821 right_shift_2 441 7724 right_shift_3 440 7716 right_shift_4 450 8061 right_shift_5 463 8653 right_shift_8 649 16320 right_shift_12 3052 114185 MyTemplatePointerHash1 438 7718 BasileStarynkevitch 453 8140 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 8945 32801 reinterpret_cast 8796 33251 djb2 11139 54855 djb2_mod 11041 54831 sdbm 11459 36849 yet_another_lc 14258 57350 murmur2 16300 39024 murmur3 16572 39221 simple_xorshift 14930 38509 double_xorshift 16192 38762 right_shift_2 8843 33325 right_shift_3 8791 32979 right_shift_4 8818 32510 right_shift_5 8775 30436 right_shift_8 10505 35960 right_shift_12 30481 91350 MyTemplatePointerHash1 8800 33287 BasileStarynkevitch 12885 37829 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 12183 33424 reinterpret_cast 12125 34000 djb2 22693 51255 djb2_mod 22722 51266 sdbm 15160 37221 yet_another_lc 24125 51850 murmur2 16273 39020 murmur3 16587 39270 simple_xorshift 16031 38628 double_xorshift 16233 38757 right_shift_2 11181 33896 right_shift_3 10785 33660 right_shift_4 10615 33204 right_shift_5 10357 38216 right_shift_8 15445 100348 right_shift_12 73773 1044919 MyTemplatePointerHash1 11091 33883 BasileStarynkevitch 15701 38092 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 415 8243 reinterpret_cast 422 8321 djb2 445 8730 djb2_mod 449 8696 sdbm 460 9439 yet_another_lc 455 9003 murmur2 475 9109 murmur3 482 9313 simple_xorshift 463 8694 double_xorshift 465 8900 right_shift_2 416 8402 right_shift_3 418 8405 right_shift_4 423 8366 right_shift_5 421 8347 right_shift_8 453 9195 right_shift_12 666 18008 MyTemplatePointerHash1 433 8191 BasileStarynkevitch 466 8443 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 450 8135 reinterpret_cast 457 8208 djb2 470 8736 djb2_mod 476 8698 sdbm 483 9420 yet_another_lc 476 8953 murmur2 481 9089 murmur3 486 9283 simple_xorshift 466 8663 double_xorshift 468 8865 right_shift_2 456 8301 right_shift_3 456 8302 right_shift_4 453 8337 right_shift_5 457 8340 right_shift_8 505 10379 right_shift_12 1099 34923 MyTemplatePointerHash1 464 8226 BasileStarynkevitch 466 8372 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 9548 35362 reinterpret_cast 9635 35869 djb2 10668 37339 djb2_mod 10763 37311 sdbm 11126 37145 yet_another_lc 11597 39944 murmur2 16296 39029 murmur3 16432 39280 simple_xorshift 16066 38645 double_xorshift 16108 38778 right_shift_2 8966 35953 right_shift_3 8916 35949 right_shift_4 8973 35504 right_shift_5 8941 34997 right_shift_8 9356 31233 right_shift_12 13831 45799 MyTemplatePointerHash1 8839 31798 BasileStarynkevitch 15349 38223 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 14756 36237 reinterpret_cast 14763 36918 djb2 15406 38771 djb2_mod 15551 38765 sdbm 14886 37078 yet_another_lc 15700 40290 murmur2 16309 39024 murmur3 16432 39381 simple_xorshift 16177 38625 double_xorshift 16073 38750 right_shift_2 14732 36961 right_shift_3 14170 36965 right_shift_4 13687 37295 right_shift_5 11978 35135 right_shift_8 11498 46930 right_shift_12 25845 268052 MyTemplatePointerHash1 10150 32046 BasileStarynkevitch 15981 38143 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 432 7957 reinterpret_cast 429 8036 djb2 462 8970 djb2_mod 453 8884 sdbm 460 9110 yet_another_lc 466 9015 murmur2 495 9147 murmur3 494 9300 simple_xorshift 479 8792 double_xorshift 477 8948 right_shift_2 430 8120 right_shift_3 429 8132 right_shift_4 432 8196 right_shift_5 437 8324 right_shift_8 425 8050 right_shift_12 519 11291 MyTemplatePointerHash1 425 8069 BasileStarynkevitch 468 8496 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 462 7956 reinterpret_cast 456 8046 djb2 490 9002 djb2_mod 483 8905 sdbm 482 9116 yet_another_lc 492 8982 murmur2 492 9120 murmur3 492 9276 simple_xorshift 477 8761 double_xorshift 477 8903 right_shift_2 458 8116 right_shift_3 459 8124 right_shift_4 462 8281 right_shift_5 463 8370 right_shift_8 458 8069 right_shift_12 662 16244 MyTemplatePointerHash1 459 8091 BasileStarynkevitch 472 8476 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 9756 34368 reinterpret_cast 9718 34897 djb2 10935 36894 djb2_mod 10820 36788 sdbm 11084 37857 yet_another_lc 11125 37996 murmur2 16522 39078 murmur3 16461 39314 simple_xorshift 15982 38722 double_xorshift 16151 38868 right_shift_2 9611 34997 right_shift_3 9571 35006 right_shift_4 9135 34750 right_shift_5 8978 32878 right_shift_8 8688 30276 right_shift_12 10591 35827 MyTemplatePointerHash1 8721 30265 BasileStarynkevitch 15524 38315 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 14169 36078 reinterpret_cast 14096 36637 djb2 15373 37492 djb2_mod 15279 37438 sdbm 15531 38247 yet_another_lc 15924 38779 murmur2 16524 39109 murmur3 16422 39280 simple_xorshift 16119 38735 double_xorshift 16136 38875 right_shift_2 14319 36692 right_shift_3 14311 36776 right_shift_4 13932 35682 right_shift_5 12736 34530 right_shift_8 9221 30663 right_shift_12 15506 98465 MyTemplatePointerHash1 9268 30697 BasileStarynkevitch 15952 38349 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 421 7863 reinterpret_cast 419 7953 djb2 457 8983 djb2_mod 455 8927 sdbm 445 8609 yet_another_lc 446 8892 murmur2 492 9090 murmur3 507 9294 simple_xorshift 467 8687 double_xorshift 472 8872 right_shift_2 432 8009 right_shift_3 432 8014 right_shift_4 435 7998 right_shift_5 442 8099 right_shift_8 432 7914 right_shift_12 462 8911 MyTemplatePointerHash1 426 7744 BasileStarynkevitch 467 8417 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 452 7948 reinterpret_cast 456 8018 djb2 489 9037 djb2_mod 490 8992 sdbm 477 8795 yet_another_lc 491 9179 murmur2 502 9078 murmur3 507 9273 simple_xorshift 473 8671 double_xorshift 480 8873 right_shift_2 470 8105 right_shift_3 470 8100 right_shift_4 476 8333 right_shift_5 468 8065 right_shift_8 469 8094 right_shift_12 524 10216 MyTemplatePointerHash1 451 7826 BasileStarynkevitch 472 8419 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 10910 38432 reinterpret_cast 10892 38994 djb2 10499 38985 djb2_mod 10507 38983 sdbm 11318 37450 yet_another_lc 11740 38260 murmur2 16960 39544 murmur3 16816 39647 simple_xorshift 16096 39021 double_xorshift 16419 39183 right_shift_2 10219 38909 right_shift_3 10012 39036 right_shift_4 10642 40284 right_shift_5 10116 38678 right_shift_8 9083 32914 right_shift_12 9376 31586 MyTemplatePointerHash1 8777 30129 BasileStarynkevitch 16036 38913 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 16304 38695 reinterpret_cast 16241 39641 djb2 16377 39533 djb2_mod 16428 39526 sdbm 15402 37811 yet_another_lc 16180 38730 murmur2 16679 39355 murmur3 16792 39586 simple_xorshift 16196 38965 double_xorshift 16371 39127 right_shift_2 16445 39263 right_shift_3 16598 39421 right_shift_4 16378 39839 right_shift_5 15517 38442 right_shift_8 11589 33547 right_shift_12 11992 49041 MyTemplatePointerHash1 9052 30222 BasileStarynkevitch 16163 38829

No se puede superar su solución en la pista de rendimiento (ni para char , ni para struct 1024), pero en sentido de corrección hay algunas mejoras:

#include <iostream> #include <new> #include <algorithm> #include <unordered_set> #include <chrono> #include <cstdlib> #include <cstdint> #include <cstddef> #include <cmath> namespace { template< std::size_t argument, std::size_t base = 2, bool = (argument < base) > constexpr std::size_t log = 1 + log< argument / base, base >; template< std::size_t argument, std::size_t base > constexpr std::size_t log< argument, base, true > = 0; } struct pointer_hash { template< typename type > constexpr std::size_t operator () (type * p) const noexcept { return static_cast< std::size_t >(reinterpret_cast< std::uintptr_t >(p) >> log< std::max(sizeof(type), alignof(type)) >); } }; template< typename type = std::max_align_t, std::size_t i = 0 > struct alignas(alignof(type) << i) S { }; int main() { constexpr std::size_t _16M = (1 << 24); S<> * p = new S<>[_16M]{}; auto latch = std::chrono::high_resolution_clock::now(); { std::unordered_set< S<> *, pointer_hash > s; for (auto * pp = p; pp < p + _16M; ++pp) { s.insert(pp); } } std::cout << std::chrono::duration_cast< std::chrono::milliseconds >(std::chrono::high_resolution_clock::now() - latch).count() << "ms" << std::endl; delete [] p; return EXIT_SUCCESS; }

Obviamente, la respuesta depende del sistema y del procesador (en particular, debido al tamaño de la página y al tamaño de la palabra). Estoy proponiendo

struct MyVoidPointerHash { size_t operator()(const void* val) const { uintptr_t ad = (uintptr_t) val; return (size_t) ((13*ad) ^ (ad >> 15)); } };

La idea es que, en muchos sistemas, el tamaño de la página es a menudo 4Kbytes (es decir, 2 ¹² ), por lo que el desplazamiento a la derecha >>15 colocará partes importantes de la dirección en los bits más bajos. El 13* es sobre todo por diversión (pero 13 es primo) y para mezclar más los bits. El exclusivo o ^ está mezclando bits y es realmente rápido. Entonces, los bits más bajos del hash son una mezcla de muchos bits (tanto altos como bajos) del puntero.

^{No pretendo haber puesto mucha "ciencia" en tales funciones hash.} ^{Pero a menudo funcionan bastante bien.} ^YMMV. ^{¡Supongo que deberías evitar desactivar ASLR !}