Implementacion de tabla Hash

[Gunder]

                                Wenas a todos,

quiero implementar una tabla hash y como no he ido a la Universidad, se supone q es donde se explican estas cosas, no tengo ni idea de como hacerlo.

He pensado en utilizar la suma de los 4 primeros caracteres, y usar este valor como indice de entrada en la tabla ( tabla de 256 indices ). Luego, almacenar las colisiones en una lista enlazada para cada indice.

Please, si alguien me puede hechar un cable pues se lo agradeceria.


[ Este Mensaje fue editado por: Gunder el 2002-04-03 18:12 ]                                

[ProD]

                                Podrias intentar utilizar el template "map" de la STL, ya que se compone de una clave y el objeto que guardas con esa clave, echale un ojo, podría servirte.

Un saludo.
                               

[Emotion]

                                Hola Gunder,

pues la verdad es que tu duda me deja un poco confuso, ya que no dices el motivo por el cual quieres utilizarlo. Si, por ejemplo, lo quieres para ordenar poligonos en profundidad (es el metodo que implementa la PSX, ya que esta carece de z-buffer), es mejor que MULTIPLIQUES los indices Z por una constante, ya que luego el acceso a los elementos almacenados es muy rapido.

En cuanto a lo de almacenar las colisiones aparte, no es lo mejor, ya que entre los datos 'limpios' tambien se pueden dar colisiones y al carecer de espacio para ordenar dichas colisiones, obtendrias alguna clase de error en la implementacion.

No obstante, hay que recordar que, segun el esquema basico de la implementacion de Hash debes disponer del 20% de espacio en memoria asignado para los elementos para las colisiones, es decir, que si has reservado, digamos, 1000Kb para la tabla, 200Kb deben ser para las colisiones

Por otro lado, puedes utilizar tu implementacion y luego sobre la tabla de colisiones volver a hacer el hash, lo cual se llama comunmente REHASHING.

Saludos
                               

[_Grey]

                                Disculpen mi ignorancia, pero... cuando dicen hash , quieren decir secuencial indexada??

Gracias, y disculpas por las molestias.

Saludos.                                

[Gunder]

                                Todo mi conocimiento de tablas hash se reduce a que se basa en la programacion de una funcion que retorna un identificador unico para una cadena. Esto se usa mucho en compiladores.

Respecto a usar un map de las STL, creo q seria mas optimo usar la template hash, pero lo q quiero es saber como se implementa una tabla hash y ya que estamos, un arbol binario no es nada optimo para pocos elementos, seria mas optimo usar una lista enlazada q es loq ue estoy haciendo ahora.

Respecto a la repuesta de Emotion, me sorprende la imaginacion de la gente ya q nunca se me ocurriria usar una tabal hash para ordenar, pero todo es ponerse. En serio Emotion, creo q te has liado con el metodo de ordenacion RADIX ( u ordenacion por residuos ). Y ya q estamos, la PSX no implenta ningun tipo de ordenacion, lo impementan los programdores.


                               

[mallrat]

                                Hola Gunder, creo que lo que buscas es una función que calcule el valor Hash de una cadena de texto, esta suele darme buen resultado:

Código [Seleccionar] Expand



int vdisp( const char *texto )

{

unsigned int v = 0;

for (; *texto; texto++ )

   {

   v = (v<<4) + (unsigned char)*texto;

   if ( v & 0xf0000000UL )

       {

       v ^= (v>>24)&0xF0;

       v &= 0xfffffffUL;

       }

   }

v = v % nElem;

return (int)v;

}



nElem sería 256 en tu caso aunque es mejor que hagas pruebas, es posible que usando un número primo consigas menor tasa de colisiones, pero lo mejor es hacer unas cuantas pruebas con datos reales, como siempre...


[ Este Mensaje fue editado por: mallrat el 2002-04-04 06:45 ]                                

[Gunder]

                                Nuchas gracias mallrat
                               

[Emotion]

                                no Gunder, no me he liado... es un metodo que da relativamente buen resultado para ordenar poligonos, y si no me crees busca por ahi documentos sobre programacion 3D por software, ahi por ahi un par de paginas que lo explican. y la PSX si hace ordenamiento usando la tabla hash (solo que no lo hace de un modo visible, y si no mira el juego de instrucciones para el 3D que lleva, hay estas dos instruccion que usan el ordenamiento del que hablo)

[ Este Mensaje fue editado por: Emotion el 2002-04-04 11:06 ]                                

[Gunder]

                                Hola emotion,

como veo q usas bien el google y q ademas sabes ingles, voy a dar una clase practica sobre el uso de este maravilloso buscador:

- Ponemos a buscar: "hash 3d efficient sorting". Alfin y alcabo, la gente habla de 3d en este foro, el palomo pregunto por hash y el resto de palabras me molan "efficient" ya que esto es tiempo real t sorting porque me suena q el hash es para ordenar.

- Damos a buscar y ... Maravilla, nos metemos en el primer hit.

- Leemos, y sin enterarnos mucho de lo q nos estan contando, posteamos una pseudo traduccion de la pagina en el foro.

- A ser posible, que lo posteado no resuelva la duda de la pregunta a la vez q metemos ciertos aspectos tecnicos para demostrar nuestro nivel como programdor.

- Si vemos un reply, contestarlo reafirmando nuestra postura.

- Y todo esto aderezado con una pizca de mofa.

Si quereis ver la pagina sin realizar esta dificil busqueda en el Google, este es el link:

http://www.3dica.org/frenzy/sort.htm



MALLRAT GRACIAS!!!!!!!!!!!!!!!!!!!!

_________________


[ Este Mensaje fue editado por: Gunder el 2002-04-04 13:16 ]                                

[Milinko]

                                Sobre lo expuesto por mallrat, efectivamente la teoria dice que es mejor usar números primos para evitar colisiones.

Puedes probar a usar 257 como nElem y puede ir bien                                

[Gunder]

                                Gracias Milinko.
                               

[Emotion]

                                Para Gunder:

Como veo que estamos un pelin graciosos, creo que tendre que hacer una oportuna explicacion al respecto:

1. Efectivamente, se ingles y me gusta el google, aunque no con los fines que tu mencionas arriba. Yo me dedico a la programacion y NO a buscarle los fallos a la gente

2. Cuando tengas tiempo intenta pillar por ahi la documentacion sobre la Net Yaroze (la PSX negra, es decir, la de programar) y veras que lo que te digo no difiere en absoluto de lo que he posteado.

3. Cuando yo digo algo, no lo digo por que si, sino porque ya lo he probado, funciona, y sobre todo, se que puede ser de relativa utilidad, pero que tu lo consideres una memez no significa necesariamente que el metodo sea una mierda.

4. Cuando yo busco algo por internet, rara vez suelo usar el google, ya que no es especifico para programacion, ya que la informacion mas interesante suele estar en los foros y en los tutoriales que hay por ahi sueltos, como los de Gamedev, Flipcode, NeHe, Romka, Gametutorials (algo mas flojos pero igual de buenos), etc, etc, etc. El google, 'amigo' mio, solo se usa cuando estas mas perdido que el barco del arroz...

5. SI, conozco ese articulo, ya que hace mucho tiempo visite la web de frenzy y otras mas interesantes para el tema de la programacion en 3D por software, y como el bien dice y yo te dije (y no solo porque lo dijo frenzy sino por otras personas que conozco PERSONALMENTE), la PSX usa un metodo para ordenar poligonos, si bien tal vez yo induje a confusion con lo de la ordenacion en profundidad, ya que la ordenacion es a nivel de vertice, como si fuera una precarga de vertices para hacer triangle striping, aunque a un nivel mas flojo. por eso te digo, LEETE EL MANUAL DE LA PSX antes de decir chorradas o criticar a los demas, para lo cual veo que no has perdido el tiempo...

y 6. QUE SEA LA ULTIMA VEZ que recibo semejante clase de afrenta en un post. antes de ponerte a criticar a nadie, ponte a analizar tus propios fallos. AH, casi se me olvidaba, MOFA no es precisamente lo que yo hago aqui, sino APRENDER y AYUDAR en la medida de lo posible. puede que TU te quejes, pero yo no he recibido queja alguna hasta la fecha. no se, puede que sea casualidad, pero parece que pueden haber sido de ayuda mis consejos. asi que... lo dicho... que sea la ultima vez

Me encantaria decir lo tipico de 'Saludos', pero la verdad... no suelo hacerlo despues de que me hayan arrojado un guantelete a la cara, asi que, simplemente, adios y buenas tardes.

_________________
Julio Meca
ALPHA SOFTWARE

[ Este Mensaje fue editado por: Emotion el 2002-04-04 17:56 ]                                

[Gunder]

                                Cuñaaaooo q me meo!!!!

graciosos lo q se dice graciosos, no.

Emotion, te recomiendo que elimimes tu DNS y uses direcciones IP directamente sobre tu navegador modo texto.

Es cierto q el google no es especifico para programadores pero me llevó a la pagina q tu consultastes hace 3 siglos, me gustaria ver tus favoritos si tienes una pagina q se actualizó por ultima vez en el 99, debe ser grande.

Por otro lado, si te he criticado es por tirarte el moco y no postear la URL del link y comentarme q la mire por si me sirve. Así como esas notas tecnicas q ni van ni vienen. La verdad esque no me importa si conoces a gente q ha programado la PSX o la Yaroze.

Y por supuesto, las respuestas se agradecen, pero eso si, se agradecen mas si se ha entendido la pregunta. Almenos ProD, mallrat y milinko se han enterado de ella. Y si te fijas Grey_ contra pregunta para decirme q no he me explicado bien y no decir chorradas.

Respecto al manual de la PSX, si lo quieres te lo posteo mañana. Solo pidelo.

Y por ultimo, la advertencia, si no te mola como se te trata en este foro, no escribas. Yo no llorare por la falta de tus respuestas.

Por cierto, te dan un premio por contestar a todo? es increible q sepas tanto... y eso q solo llevas 13 años en esto.


[ Este Mensaje fue editado por: Gunder el 2002-04-04 19:11 ]                                

[Emotion]

                                Vaya Gunder... veo que sigues dandole vueltas al tema, pues bien... respondere a este post POR ULTIMA VEZ.

Yo no se, sinceramente, cuantos años llevaras tu en esto metido, pero me da la sensacion de que no muchos, ya que si fuera asi no dirias las tonterias que dices, pero OJO: es MI CRITERIO PERSONAL. nada mas.

Por otro lado, no considero muy honesto por tu parte meter en el fregado a los demas, creo que se merecen mas respeto del que TU muestras con este desagradable asunto.

Ah, por cierto... el manual de la PSX me lo pasaron legalmente y si tu lo posteas aqui, seria ILEGAL, ya que aun es propietario. No creo que el personal del foro de Stratos quiera hacer frente a un posible litigio con Sony por tu culpa. listillo... ;D

y por ultimo, decir que... no te molestes en contestar, ya que no pienso volver a entrar en este topic. creo que ya he visto bastante y no pienso ponerme a tu altura.

P.D. ya se que no fuiste a la universidad (tu mismo lo dijiste), pero... fuiste al colegio? porque creo que mi hermano de 15 años es mas... coherente con sus insultos... venga hombre... que el cuñao ya ha pasado de moda...

y para que veas que no te guardo rencor...

Saludos
                               

[Gunder]

                                Tio, te has pasado.

NO TE PERMITO Q DIGAS Q LOS CUÑAAAOOS ESTAN PASADOS DE MODA.

Pavo, Pavo, pavito....