Si se colocan bolas en n contenedores de manera uniforme al azar, el contenedor cargado más pesado tiene O ( lg n / lg lg n ) bolas con alta probabilidad. En "The Power of Simple Tabulation Hashing" , Pătraşcu y Thorup mencionan que "los límites de Chernoff-Hoeffding para aplicaciones con independencia limitada" ( espejo ) muestran que esto limitado a la población del contenedor cargado más pesado también se cumple si las bolas son distribuidas por un Función hash independiente de Ω ( lg n / lg lg n ) .
En "Balls and Bins: Smaller Hash Families and Faster Evaluation" , Celis et al. tenga en cuenta que no se sabe si hay una familia de funciones hash donde
- Las funciones hash se pueden representar con bits de espacio
- Las funciones hash se pueden evaluar en tiempo
- La carga máxima es con alta probabilidad.
Si hay una constante tal que cualquier familia independiente de k es suficiente para # 3, entonces la construcción polinómica de las familias independientes de k cumpliría con # 1 y # 2.