Consulta ejercicio tablas de hash I2-2024-1

[IgnacioHqz]

Hola, estuve tratando de hacer este ejercicio de tablas de hash, pero tengo algunas dudas que no he podido resolver.
Lo primero es que no logro entender cómo es que obtienen la funcion de hash que se presenta como solucion. Hay alguna razón de por qué deba ser así? La verdad es que no se me habría ocurrido hacerla así, por lo que tal vez haya alguna estrategia que se pueda hacer para poder llegar a la funcion propuesta.
También aprovechar de preguntar sobre la misma función. Qué sucede con los casos en que los RUT son menores a 22 millones? Otra duda que me surgió fue que cómo se manejan los casos en donde hay dos RUT que tienen el mismo numero antes del digito verificador?

Si me pudieran ayudar se los agradecería mucho!

[tomastrivino]

Hola!!
1.- Puedes plantear otras funciones de hash para este ejercicio. Lo importante es haber llegado a eso y obtener adecuadamente el factor de carga, entre otros. Un hint que te da el enunciado, es que el 80% de los datos están entre 22.000.000 y 22.400.000 (y son 200 mil personas), por lo que habrán 160.000 registros contenidos en ese rango. Por darte un ejemplo, cuando yo di esta prueba, recuerdo haber propuesto una función con módulo, algo como $h(RUN) = RUN mod 200000$ :)

2.- Respecto a tu otra pregunta, recuerda que acorde al enunciado se define RUN Entero (sin DV) y DV char respectivamente. No me queda tan claro por qué te preocupa el número antes del dígito verificador.

[IgnacioHqz]

Holaa gracias por tu respuesta!
En relación al primer punto, ¿por qué solamente en la pauta se centran en el 80% y no consideran el otro 20%?
Y con respecto a la función que me comentas, por lo general las funciones de hash que hay que hacer siempre son del tipo mod? Lo pregunto ya que la verdad siento que me va a costar crear una función que no sea del tipo mod. Si me pudieras orientar a cómo poder crear una buena función te lo agradecería mucho, ya que la materia la entiendo, pero crear funciones me suelen costar :/

Con respecto al segundo punto, más que gana me preocupaban los casos en los que hubieran dos RUN con los mismos números antes del del DV, por lo que habría una colisión, por ejemplo 20.000.123-1 y 20.000.123-5 o se asume que esto no sucede?

[tomastrivino]

Hola,
generalmente las funciones de hash con módulos, quizás combinado techos/pisos, suelen ser suficientes como una función de hash básica para efectos de la prueba. El hint del 80% te sirve para saber en qué rango estarán mayormente concentrados los datos! Inicialmente sabemos que los RUN se concentran en el rango de 1 a 25.000.000, pero ¿ves realista hacer una función de módulo 25000000? Eso implicaría tener 25000000 BUCKETS, ¡lo que quizás no es tan conveniente! Si sabes que la mayoría de datos está concentrado en un rango de 22.000.000 a 22.400.000 y que sólo en ese rango hay 160.000 entradas, quizás es más fácil llegar a algo que ocupe módulo 400000, o módulo 200000, etc.

Al final en esta clase de ejercicios tú decides el approach que le das a tu función de hash, en donde lo relevante termina siendo la justificación (idealmente que pongas cómo llegas a eso), el factor de carga, tamaño de tabla y cómo manejas colisiones.

Saludos!

[IgnacioHqz]

Perfecto muchas gracias!
Y que pasaría por ejemplo con un valor que sea menor a 22 millones? cómo se calcularía el valor de hash usando la función que está en la pauta? eso me causó extrañeza ya que quedaría un valor negativo y solo serviría para los valores mayores a 22 millones, no sé si estoy entendiendo bien. Entiendo que se hace una resta para que los datos empiecen desde el 0 y quedarían 200.000 buckets, pero solo se usarían 160.000 no?
También quisiera aprovechar para preguntar que en el caso de que la función sea RUN mod 200.000, el factor de carga sería 1 o cómo se calcularía en ese caso?
Muchas gracias!

[IgnacioHqz]

Holaa gracias por tu respuesta!
En relación al primer punto, ¿por qué solamente en la pauta se centran en el 80% y no consideran el otro 20%?
Y con respecto a la función que me comentas, por lo general las funciones de hash que hay que hacer siempre son del tipo mod? Lo pregunto ya que la verdad siento que me va a costar crear una función que no sea del tipo mod. Si me pudieras orientar a cómo poder crear una buena función te lo agradecería mucho, ya que la materia la entiendo, pero crear funciones me suelen costar :/

Con respecto al segundo punto, más que gana me preocupaban los casos en los que hubieran dos RUN con los mismos números antes del del DV, por lo que habría una colisión, por ejemplo 20.000.123-1 y 20.000.123-5 o se asume que esto no sucede?

[bcalfaro]

Hola! Respecto al tema del Rut, en la realidad el DV se calcula con una fórmula específica que siempre da el mismo resultado. Por ende, no debería haber dos números iguales en lo que corresponde a no-DV.
Aquí una noticia que explica un poco (se trabaja con un algoritmo en torno al módulo de 11)

[IgnacioHqz]

Perfecto muchas gracias! no sabía ese dato jajaj
muy agradecido :) !!

[luzmagurzua]

Holaa me uno a la discusión, para el inciso a) el dato de que el 80% está entre 22.000.000 y 22.400.000 no nos suma info importante, cierto? porque con que nos digan que 200 mil personas rinden la prueba entonces, altiro podemos obtener el numero de buckets que seria 200.000, y luego para la funcion de hash proponer RUT%200.000, así es como lo pensé