¿Cuál es exactamente el tamaño de tabla en SAS HashTable especificado por hashexp?

Question

Me gustaría aclarar un poco sobre la definición de un cubo en la tabla hash SAS. La pregunta es exactamente sobre el parámetro hashexp.

Según el SAS Docs, hashexp es:

tamaño de la tabla interna del objeto hash, donde el tamaño de la tabla hash es 2n.

El valor de HASHEXP se utiliza como un exponente de potencia de dos para crear el tamaño de la tabla hash. Por ejemplo, un valor de 4 para HASHEXP equivale a un tamaño de la tabla hash del 24, o 16. El valor máximo para HASHEXP es 20.

El tamaño tabla hash no es igual a la cantidad de artículos que pueden ser almacenado Imagine la tabla hash como una serie de 'cubos'. Un tamaño de tabla hash de 16 tendría 16 'cubos'. Cada cubo puede contener un número infinito de elementos. La eficacia de la tabla hash reside en la capacidad de la función hashing para asignar elementos a los elementos y recuperarlos de los depósitos.

Debe establecer el tamaño de la tabla hash en relación con la cantidad de datos en el objeto hash para maximizar la eficacia de las rutinas de búsqueda de objetos hash. Pruebe diferentes valores de HASHEXP hasta que obtenga el mejor resultado. Por ejemplo, si el objeto hash contiene un millón de elementos, un tamaño de tabla hash de 16 (HASHEXP = 4) funcionaría, pero no de manera muy eficiente. Un tamaño de tabla hash de 512 o 1024 (HASHEXP = 9 o 10) daría como resultado el mejor rendimiento.

La pregunta es ¿qué es exactamente un tamaño de la tabla hash de , si bien no es una cantidad de datos en el objeto hash?

Debería entenderse como si quisiéramos asignar tanta memoria como sea necesario pero no menos, no más. Es un poder de dos para que las cosas funcionen rápido. Pero no limita la cantidad de datos posiblemente utilizados, solo indica cuánto se va a usar, ¿no?

Answer 1

Paul Dorfman (el maestro de hash) entra en un poco de detalle en la página 10 de este documento técnico:

http://www2.sas.com/proceedings/forum2008/037-2008.pdf

Como yo lo entiendo, tablas hash almacenan sus datos en los árboles binarios. Cada segmento creado por hashexp representa la cantidad de árboles binarios que se usarán para almacenar los datos. Un hashexp de 0 usaría un solo árbol, mientras que un hashexp de 8 usaría 256 árboles. Cuando se realiza una búsqueda contra el objeto hash, un algoritmo interno determina en qué árbol debe existir la clave (en función del valor hash). Luego verifica ese árbol por el valor. Al saber automáticamente cuál de los 256 árboles buscar (por ejemplo) se habría ahorrado 8 comparaciones (2^8) en comparación con un único árbol binario.

Todo parece mucho más complejo que eso, pero esa es mi interpretación de por qué funciona más rápido.

Answer 2

Como señaló Rob Penridge, Paul Dorfman es de hecho el SAS Hash Object Guru. Hashexp no está relacionado con el tamaño de la tabla hash, de nuevo como se menciona en la respuesta de Rob.

Si tiene una tabla con 100obs y 10 variables numéricas que se cargan en una tabla hash, el tamaño de la tabla hash es simplemente 100obs * 10vars * 8bytes (suponiendo que todos los vars numéricos estén almacenados como campos de 8 bytes) 7.8KB give o toma un 10%.

Recuerde que SAS asigna dinámicamente espacio RAM a medida que se agregan registros a la tabla Hash en la memoria, por lo que no necesita especificar con anticipación qué tamaño debería tener. [He estado usando tablas hash regularmente, pero no puedo pensar de cualquier lugar donde se pueda especificar el tamaño por adelantado].

Consejo general: si desea saber qué tan grande será su tabla hash, ejecute PROC CONTENTS en el conjunto de datos que desea cargar en la tabla hash y multiplique "Longitud de observación" & "Nº de obs en el conjunto de datos ", esto dará el tamaño de memoria necesario en bytes. Si tienes tanta memoria, entonces puedes cargarla en la memoria.