Tema 1: Estructuras de Datos - Tablas Hash

[Ing. Joe Llerena]

Saludos estimados estudiantes,

Estamos conociendo en esta asignatura, Estructuras de Datos,
diferentes códigos que nos proponen formas nuevas, complejas y
eficientes
de programar. Asimismo nuevas formas de implementar soluciones
que han dado origen a implementaciones con mayor consistencia
logrando plasmarlas en usos de otros software o hardware.

Las Tablas Hash son estructuras de asociación

http://es.wikipedia.org/wiki/Tabla_hash
http://www.slideshare.net/vicomanuel/tablas-hash-fash-vmaa

Luego de la lectura, conteste las siguientes preguntas:

1.- Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

2.- Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción
y eliminación, en la práctica difícilmente se cumple, explique
por qué. Investigue

3.- Implemente un ejercicio con Tablas Hash en Java.

Saludos cordiales
Ing. Joe Llerena I. Msig.

[Blanca Delgado]

DEBER DE ESTRUCTURAS

 

1.-  Para implementar una estructura abstracta, debemos considerar tres factores Velocidad de búsqueda, Uso de la memoria y La información deba estar ordenada o no,  ¿Cuál escogería usted como factor principal?, indique el por  qué  justificándolo con código en java.

 

Quizás el que menos importe para aplicaciones no-embebidas es el punto de la memoria. En general cualquier estructura que tenga un orden de búsqueda decente no utiliza memoria a mansalva.

 

Por lo que nos quedan dos pesos pesados bien claros, velocidad de búsqueda y si la información debe o no estar ordenada.

 

Las dos estructuras obvias que uno piensa en estos casos son: árboles binarios balanceados (AVL o rojo-negro por ejemplo) y la sencilla pero ingeniosa tabla hash.

 

BUSQUEDA HASHING

Existe otro método que puede aumentar la velocidad de búsqueda donde los datos no necesitan estar ordenados y esencialmente es independiente del número n. Este método se conoce como transformación de claves (clave- dirección) o hashing. El hashing consiste en convertir el elemento almacenado (numérico o alfanumérico) en una dirección (índice) dentro del array.

    La idea general de usar la clave para determinar la dirección del registro es una excelente idea, pero se debe modificar de forma que no se desperdicie tanto espacio. Esta modificación se lleva a cabo mediante una función que transforma la clave en un índice de una tabla y que se denomina función de randomización o Hash. Si H es una función hash y X es un elemento a almacenar, entonces H(X) es la función Hash del elemento y se corresponde con el índice donde se debe colocar X. En nuestro ejemplo, la función hash sería

 H(X) = X % 1000

    Los valores generados por H deben cubrir todo el conjunto de índices de la tabla.

 

n= número de elementos en el vector
x= valor a buscar  

void Hashing(){
    int d=0,dx=0;
    d=( x%n)+1;
    if(a[d] = = x )
         printf("valor encontrado");
    else{
        dx = d + 1;
        while(  (d < n)  &&  (a[dx] != x)  && (a[dx] != 0)  && (dx != d) ){
            dx = dx + 1;
             if(dx = = n)
                dx = 1;
        ^}
    }
}

  dx= posición en el vector del elemento a buscar

 

 2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en Búsqueda como inserción y eliminación, en la práctica difícilmente se cumple, explique Por qué. Investigue.

 

Esto en la práctica difícilmente se cumpla, ya que generar una clave hash única e irrepetible para cada elemento es una tarea casi imposible para una cantidad grande de elementos. Hablamos del orden de 10000 elementos o más.

 

3.- Implemente un ejercicio con Tablas Hash en Java.

 

import java.util.Dictionary;

import java.util.Hashtable;

 

class HTDemo {

            public static void main(String args[]) {

                        Hashtable ht = new Hashtable();

                        ht.put("title", "Manual de Java");

                        ht.put("author", "Algunos");

                        ht.put("email", "nise...@puesalli.es");

                        show(ht);

            }

                static void show(Dictionary d)  {

                        System.out.println("Titulo: " + d.get("title"));

                        System.out.println("Autor: " + d.get("author"));

                        System.out.println("E-mail: " + d.get("email"));

                        System.out.println("");

            }

}

 

[Paul Paredes Acosta]

FORO DE ESTRUCTURAS DE DATOS

PRIMERA PREGUNTA


Escogeria la primera Velocidad de busqueda como factor importante
porque orden de búsqueda de los arboles binarios balanceados es O(log2
(n)) siendo n la cantidad de elementos insertados. El orden de
inserción y eliminación de elementos a pesar de que tiene que realizar
operaciones para balancear el arbol, también tienden al mismo orden
que el de búsqueda.


public void buscarHash(Object elemb, int nmax){

int e=elemb.hashCode();


if(e<0){
e*=-1;
}

int pos=e%nmax;
if(th[pos]==null){

System.out.print("Elemento no encontrado");
}else{
if(th[pos].equals(elemb)){
System.out.print("Elemento encontrado,
"+elemb+ " su posicion es : "+ pos);
}else{
int j=pos+1;
if(j==th.length){
j=0;
}
while((th[j]!=elemb)&&(th[j]!=null)&&(j!
=pos)){
j++;
if (j>=th.length-1){
j=0;
}
}

if(th[j].equals(elemb)){
System.out.print("Elemento
encontrado, "+elemb+ " su posicion es : "+ j);
}else{
System.out.print("Elemento
no encontrado");
}
}
}
}



SEGUNDA PREGUNTA

Porque al generar una clave hash unica e irrepetible para cada

elemento es una tarea casi imposible para una cantidad grande de

elementos. Hablamos del orden de 10000 elementos o mas.


TERCERA PREGUNTA

import java.util.*;


public class hash {

public static void main (String args[]) throws Exception {
Hashtable hash = new Hashtable(10,10);

for (int i = 0; i <= 100; i++)
{
Integer entero = new Integer ( i );
hash.put( entero, "Numero : " + i);
}

for (Enumeration e = hash.keys(); e.hasMoreElements();)
{
System.out.println (hash.get(e.nextElement()));
}
}

}

[Tomas Coronel]

Respuestas

1era. respuesta
Con respeto a la pregunta podríamos decir que los dos elementos mas
importantes son La Velocidad de búsqueda y La Información debe estar
ordenada o no ya que ambos factores van unidos entre si, ya que la
búsqueda esta basada mediante una información ya dada; por eso también
podríamos decir que el uso de memoria no es tan indispensable.

Para buscar una información ya dada tenemos un metodo de busqueda
llamado HASHING.

Busqueda Hashing
• Método que puede aumentar la velocidad de búsqueda donde los datos
no necesitan estar ordenados.
• Independiente del número n.
• Transformación de claves (clave- dirección) o hashing.- El hashing

consiste en convertir el elemento almacenado (numérico o alfanumérico)
en una dirección (índice) dentro del array.

n= número de elementos en el vector
x= valor a buscar
void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !=
d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;
}
}
}
dx= posición en el vector del elemento a buscar

2da. respuesta


La teoría se cumple cuando podriamos estar hablando de pocos
elementos, pero es imposible que se cumpla cuando hablamos de muchos
elementos es decir 10000, 20000, 1000, etc.
Ya que una tabla hash genera una clave única para cada elemento, por
eso para pocos datos si es posible; pero para una cantidad de datos
extensa, es más propenso a que ocurra algún error.




3era. respuesta

import java.util.Dictionary;
import java.util.Hashtable;

class java817 {
public static void main( String args[] ) {

Hashtable ht = new Hashtable();

ht.put( "titulo","Tutorial de Java" );
ht.put( "autor","Agustin Froufe" );
ht.put( "email","fro...@arrakis.es" );
ht.put( "patria","Spain" );
ht.put( "edad",new Integer( 31 ) );
show( ht );
}

static void show( Dictionary d ) {
System.out.println( "Titulo: " + d.get( "titulo" ) );
System.out.println( "Autor: " + d.get( "autor" ) );

System.out.println( "E-mail: " + d.get( "email" ) );

System.out.println( "Pais: " + d.get( "patria" ) );
System.out.println( "Edad: " + d.get( "edad" ) );
}
}

//------------------------------------------- Final del fichero
java817.java

[jorge valdiviezo]

>>>>FORO DE ESTRUCTURAS DE DATOS<<<<

1.- Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

Pues a mi parecer el factor más importante a considerar es la
velocidad de la búsqueda ya que si nos ponemos a considerar los otros
factores, pues nos damos cuenta que estos son menos relevantes ya que
si hablamos del uso de la memoria nos damos cuenta q en este tiempo
disponemos de una cantidad enorme de memoria para poder trabajar y si
tomamos en cuenta el factor "Ordenamiento de Información" pues Las
tablas hash almacenan la información en posiciones pseudo-aleatorias,
así que el acceso ordenado a su contenido es bastante lento.Otras
estructuras como árboles binarios auto-balanceables son más rápidos en
promedio pero la información está ordenada en todo momento

public void buscarHash(Object elemb, int nmax){

int x=elemb.hashCode();
if(x<0){
x =-1;
}
int pos=x%nmax;
if(tabla[pos]==null){
System.out.println("El Elemento no se encontro");
}else{
if(tabla[pos].equals(elemb)){
System.out.print("Elemento encontrado

"+elemb+ " su posicion es : "+ pos);
}else{
int j=pos+1;

if(j==tabla.length){
j=0;
}
while((tabla[j]!=elemb)&&(tabla[j]!=null)&&
(j!=pos)){
j++;
if (j>=tabla.length-1){
j=0;
}
}
if(tabla[j].equals(elemb)){

System.out.print("Elemento
encontrado, "+elemb+ " su posicion es :"+j);
}else{
System.out.print("Elemento
no encontrado");
}
}
}
}

2.- Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción
y eliminación, en la práctica difícilmente se cumple, explique
por qué. Investigue

Pues esta teoría muy pocas veces se cumple en la práctica ya que
cuando trabajamos con tablas hash es cuando utilizamos una cantidad
enorme de elementos. Una tabla hash genera una clave única para cada

elemento, por eso para pocos datos si es posible; pero para una
cantidad de datos

extensa, queda más vulnerable a que caiga en errores.

3.- Implemente un ejercicio con Tablas Hash en Java.

import java.io.*;
import java.util.Dictionary;
import java.util.Hashtable;

class Palabra {
int codigo;
String palabra;
String ocurrencia;

//el constructor
public Palabra(int codigo, String palabra, String ocurrencia ){
this.codigo = codigo;
this.ocurrencia = ocurrencia;
this.palabra = palabra;

}

public static void main(String args[]){

Hashtable tabla = new Hashtable();
Palabra p = new Palabra(1,"Arroz","o");
Palabra a= new Palabra(2,"Pollo","M");
tabla.put(new Integer(p.codigo),p);
tabla.put(new Integer(a.codigo),a);

Palabra o = (Palabra) tabla.get(new Integer(2));
System.out.println(o.palabra) ;
}
}

[Eddin Ramirez]

Pregunta 1

Yo escojeria la opción de búsqueda porque debe tenerse en memoria principal la página sobre la cual vamos a buscar. Considérese el elemento a buscar x. Si la búsqueda es infructuosa dentro de la página se estará en una de las siguientes situaciones:

k_i < x < k_{i + 1} para 1 ≤i < n. La búsqueda continúa en la página r_i.

k_n < x. La búsqueda continúa en la página r_n.

x < k₁. La búsqueda continúa en la páginar₀. Si en algún caso la referencia es nula, es decir, si no hay página descendiente, entonces no hay ningún elemento x en todo el árbol y se acaba la búsqueda.

public boolean buscar(Object o)

 {

   if (o.equals(valor))

     return true;

   else if (o.compareTo(valor)<0)

     return buscar(getIzq(),o);

   else return buscar(getDer(),o);

 }

 

 

Pregunta 2

 

Difícilmente se cumple por el problema de colisiones ya que estas tienen que ser resueltas por una búsqueda lineal y la función tienden a generar valores similares.

Otro problema es el aglomeraniento cuando las llaves usadas comúnmente tiendan a caer muy cerca unas de otras o incluso consecutivamente en la tabla hash y esto degrada el funcionamiento y cuando la tabla se llena usando ciertas estrategias de resolución de colisiones, como el sondeo linea

 

Pregunta 3

[Kevin Utreras]

ESTRUCTURAS DE DATOS

1era PREGUNTA

Escogeria la primera Velocidad de busqueda como factor importante
porque orden de búsqueda de los arboles binarios balanceados es O
(log2

(n)) siendo cantidad de elementos insertados.

public void buscarHash(Object elemb, int nmax){

int e=elemb.hashCode();


if(e<0){
e*=-1;
}

int pos=e%nmax;
if(th[pos]==null){

System.out.print("Elemento no encontrado");

}else{
if(th[pos].equals(elemb)){
System.out.print("Elemento encontrado,

"+elemb+ " su posicion es : "+ pos);
}else{
int j=pos+1;

if(j==th.length){
j=0;
}
while((th[j]!=elemb)&&(th[j]!=null)&&(j!
=pos)){
j++;
if (j>=th.length-1){
j=0;
}
}

if(th[j].equals(elemb)){

System.out.print("Elemento
encontrado, "+elemb+ " su posicion es : "+ j);
}else{
System.out.print("Elemento
no encontrado");
}
}
}
}

2da.- PREGUNTA

Inserción.- Para almacenar un elemento en la tabla hash se ha de
convertir su clave a un número. Esto se consigue aplicando la función
resumen a la clave del elemento.
El resultado de la función resumen ha de mapearse al espacio de
direcciones del array que se emplea como soporte, lo cual se consigue
con la función módulo. Tras este paso se obtiene un índice válido para
la tabla.
El elemento se almacena en la posición de la tabla obtenido en el paso
anterior.
Si en la posición de la tabla ya había otro elemento, se ha producido
una colisión. Este problema se puede solucionar asociando una lista a
cada posición de la tabla, aplicando otra función o buscando el
siguiente elemento libre. Estas posibilidades han de considerarse a la
hora de recuperar los datos.

Búsqueda.- Para recuperar los datos, es necesario únicamente conocer
la clave del elemento, a la cual se le aplica la función resumen.
El valor obtenido se mapea al espacio de direcciones de la tabla.
Si el elemento existente en la posición indicada en el paso anterior
tiene la misma clave que la empleada en la búsqueda, entonces es el
deseado. Si la clave es distinta, se ha de buscar el elemento según la
técnica empleada para resolver el problema de las colisiones al
almacenar el elemento.


TERCERA PREGUNTA

import java.util.*;

private static int Hash1(String Clave) {

int valor = Clave.charAt(0);
int tam = Clave.length();

for (int i = 1; i < tam ;i++) {

valor += Character.getNumericValue( Clave.charAt(i));

}

return (valor % N);

}

[Carolina López]

1.-  Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

Una buena función hash es esencial para el buen rendimiento de una
tabla hash. Las colisiones son generalmente resueltas por algún tipo
de búsqueda lineal, así que si la función tiende a generar valores
similares, las búsquedas resultantes se vuelven lentas.

En una función hash ideal, el cambio de un simple bit en la llave
(incluyendo el hacer la llave más larga o más corta) debería cambiar
la mitad de los bits del hash, y este cambio debería ser independiente
de los cambios provocados por otros bits de la llave. Como una función
hash puede ser difícil de diseñar, o computacionalmente cara de
ejecución, se han invertido muchos esfuerzos en el desarrollo de
estrategias para la resolución de colisiones que mitiguen el mal
rendimiento del hasheo. Sin embargo, ninguna de estas estrategias es
tan efectiva como el desarrollo de una buena función hash de
principio.

Es deseable utilizar la misma función hash para arrays de cualquier
tamaño concebible. Para esto, el índice de su ubicación en el array de
la tabla hash se calcula generalmente en dos pasos:

1. Un valor hash genérico es calculado, llenando un entero natural
de máquina
2. Este valor es reducido a un índice válido en el arreglo
encontrando su módulo con respecto al tamaño del array.

El tamaño del arreglo de las tablas hash es con frecuencia un número
primo. Esto se hace con el objetivo de evitar la tendencia de que los
hash de enteros grandes tengan divisores comunes con el tamaño de la
tabla hash, lo que provocaría colisiones tras el cálculo del módulo.
Sin embargo, el uso de una tabla de tamaño primo no es un sustituto a
una buena función hash.

Un problema bastante común que ocurre con las funciones hash es el
aglomeramiento. El aglomeramiento ocurre cuando la estructura de la
función hash provoca que llaves usadas comúnmente tiendan a caer muy
cerca unas de otras o incluso consecutivamente en la tabla hash. Esto
puede degradar el rendimiento de manera significativa, cuando la tabla

se llena usando ciertas estrategias de resolución de colisiones, como

el sondeo lineal.

Cuando se depura el manejo de las colisiones en una tabla hash, suele
ser útil usar una función hash que devuelva siempre un valor
constante, como 1, que cause colisión en cada inserción.


registro par { llave, valor }
var arreglo de pares casilla[0..numcasillas-1]

function buscacasilla(llave) {
i := hash(llave) módulo de numcasillas
loop {
if casilla[i] esta libre or casilla[i].llave = llave
return i
i := (i + 1) módulo de numcasillas
}
}

function busqueda(llave)
i := buscacasilla(llave)
if casilla[i] está ocupada // llave en la tabla
return casilla[i].valor
else // llave es está en la tabla
return no encontrada

function asignar(llave, valor) {
i := buscacasilla(llave)
if casilla[i] está ocupada
casilla[i].valor := valor
else {
if tabla casi llena {
hacer tabla más grande (nota 1)
i := buscacasilla(llave)
}
casilla[i].llave := llave
casilla[i].valor := valor

}
}



 2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción
y eliminación, en la práctica difícilmente se cumple, explique
por qué. Investigue

Por otro lado, la tabla hash teórica tiende a un orden mínimo tanto en
búsqueda como inserción y eliminación, que sería O(1). Esto en la
práctica dificilmente se cumpla, ya que generar una clave hash unica e

irrepetible para cada elemento es una tarea casi imposible para una
cantidad grande de elementos. Hablamos del orden de 10000 elementos o

mas. Si querés ver mas sobre tablas hash podes verlo

 3.- Implemente un ejercicio con Tablas Hash en Java.

unsigned int jenkins_one_at_a_time_hash(void *vkey)
{
unsigned hash = 0;
size_t i;
unsigned char *key;
int key_len;


key = (unsigned char *)vkey;

key_len = strlen(key);

for (i = 0; i < key_len; i++) {
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}

[Carolina López]

Carito


 

Para implementar una estructura abstracta, debemos considerar
 tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

 2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en

 búsqueda como inserción

y eliminación, en la práctica difícilmente se cumple, explique

por qué. Investigue



Por otro lado, la tabla hash teórica tiende a un orden mínimo tanto en búsqueda como inserción y eliminación, que sería O(1). Esto en la práctica dificilmente se cumpla, ya que generar una clave hash unica e irrepetible para cada elemento es una tarea casi imposible para una cantidad grande de elementos. Hablamos del orden de 10000 elementos o mas. Si querés ver mas sobre tablas hash podes verlo

 3.- Implemente un ejercicio con Tablas Hash en Java.

[joselyne garcia]

1er Tema:

Los factores mas importantes que podemos considerar son dos:
1. La velocidad de busqueda.
2. Los datos deben estar ordenados o no

ya que usar la memoria seria un gran desperdicio.

para eso temenos un algoritmo conocido como Hashing
Ejemplo:

void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !=
d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;
}
}
}

2do. Tema:

Las tablas hash generan un codigo de identificacion unico.
Esto en la practica no se cumple ya que para muchos datos
(1000,5000,10000,etc) es mas propenso a errores.
esto si funcionaria si estariamos hablado de pocos Datos ya que la
posiblilidades de errores son minimas.




3er. Tema:

[joselyne garcia]

FORO

1er. Tema

Los factores más importantes que podemos considerar son dos:
 1. La velocidad de búsqueda.

 2. Los datos deben estar ordenados o no

ya que usar la memoria sería un gran desperdicio.

para eso temenos un algoritmo conocido como Hashing
Ejemplo:
void Hashing(){
   int d=0,dx=0;
   d=( x%n)+1;
   if(a[d] = = x )
        printf("valor encontrado");
   else{
       dx = d + 1;
       while(  (d < n)  &&  (a[dx] != x)  && (a[dx] != 0)  && (dx !=
d) ){
           dx = dx + 1;
            if(dx = = n)
               dx = 1;
       }
   }
}






2do. Tema:

Las tablas hash generan un código de identificación único.
Esto en la práctica no se cumple ya que para muchos datos

(1000,5000,10000,etc) es mas propenso a errores.

Esto si funcionaría si estaríamos hablado de pocos Datos ya que la
posiblilidades de errores son mínimas.

[Pamela Franco]

*DEBER DE ESTRUCTURAS DE DATOS*


*1.-) Para implementar una estructura abstracta, debemos considerar

tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por

qué justificándolo con código en java.*


Un mundo virtual es un espacio representado por medio de un programa
de
software ejecutado en una computadora. Este espacio tiene un conjunto
definido de reglas que controlan las interacciones entre grupos de
actores
independientes que lo habitan.
El mundo virtual cuenta con un modulo central que controla las
interacciones
de los diferentes actores; una forma de ejercer este control es
mediante una
estructura tipo cola de prioridades mediante la cual se simula un
flujo infinito
de acciones ejecutadas por los diferentes Actores del mundo.
Esta estructura ordena los actores del mundo tomando en cuenta el
tiempo
que les resta para ejecutar una acción nuevamente. El módulo central
toma
el primer Actor de la estructura y llama a su Selector de Acción con
el fin de
obtener la acción que este ejecutará; luego de la ejecución de la
acción el
Actor es relocalizado en un lugar de la estructura dependiendo del
costo en
tiempo asociado con la acción que ejecutó.
Por lo tanto, cada Actor que habita el mundo debe tener la capacidad
de
decidir que acciones ejecutar independientemente de los demás Actores

import java.util.*;


public class hash {

public static void main (String args[]) throws Exception {
Hashtable hash = new Hashtable(10,10);

for (int i = 0; i <= 100; i++)
{
Integer entero = new Integer ( i );
hash.put( entero, "Numero : " + i);
}

for (Enumeration e = hash.keys(); e.hasMoreElements();)
{
System.out.println (hash.get(e.nextElement()));
}
}

}

*2.-) Las tablas Hash, teóricamente tiende a un orden mínimo tanto

en
búsqueda como inserción
y eliminación, en la práctica difícilmente se cumple, explique

por qué. Investigue. *


Más formalmente, la función de hash está definida por su dominio
(cadenas de bytes de longitud variable), su imagen (secuencias de
bytes de longitud fija) y por la función que relaciona dichos
conjuntos (llamada función H). La característica deseada en una
función Hash es:

Primer criterio:

Desafortunadamente esta idealización (denominada colisiones de hash)
es precisa pero indeterminada. Si el conjunto de valores que puede
tomar H(x) es mucho menor que las posibilidades de x, entonces esto no
puede ser cierto siempre que todos los valores de x pueden ser
igualmente probables. Entonces, existe una segunda condición para
hacer la función útil. Por ejemplo:

Segundo criterio (1): dado un H(x) es complejo encontrar y tal que H
(y) = H(x).

Segundo criterio (2): dados x y H(x + s) no es sencillo encontrar s.

En estos ejemplos anteriores, al referirse al grado de dificultad de
una tarea se habla siempre en un sentido puramente computacional. Esto
es, que el tiempo necesario para ejecutar dicha tarea sea
increíblemente grande (ver NP-C). Además, + puede ser cualquier
operación válida sobre el conjunto de partida.

En la práctica, para la mayoría de las aplicaciones sin contar la
corrección de errores las funciones hash criptográficas son
suficientemente útiles. Los algoritmos MD5 y SHA-1 son dos de los más
populares.

Las tablas hash, una de las aplicaciones más extendidas de las
funciones de hash, aceleran el proceso de búsqueda de un registro de
información según una clave (nota: este uso de la palabra poco se
relaciona con su significado habitual). Por ejemplo, una cadena
alfanumérica puede ser utilizada para buscar la información de un
empleado en la base de datos de un sistema.

La utilización de tablas hash provee un acceso casi directo a dichos
registros, lo que significa que, en promedio, una búsqueda puede
llegar a requerir sólo uno o dos intentos en la memoria o el archivo
que contiene la información. Naturalmente, se prefiere una buena
función de hash que evitará colisiones de hash.

Si asumimos que la clave es una cadena de bytes, entonces la función
de hash debería ser como un índice de los registros que tiene una
distribución aleatoria sobre las cadenas de entrada esperadas. De otra
forma, habría más colisiones de hash degradando así el tiempo de
búsqueda. Si, por ejemplo, la clave es alfabética, cada byte puede
tener sólo 26 de sus 256 valores posibles. Funciones tan simples no
distribuirán los índices de una forma pareja.

Para una comparación de velocidad y calidad de varias funciones de
hash, referirse a los enlaces externos.



* 3.-) Implemente un ejercicio con Tablas Hash en Java. *

TablaHash CrearTablaHash ()
{
TablaHash t;
register i;

t=(TablaHash)malloc(NCASILLAS*sizeof(char *));
if (t==NULL)
error("Memoria Insuficiente.");

for (i=0;i<NCASILLAS;i++)
t[i]=VACIO;

return t;
}

void DestruirTablaHash (TablaHash t)
{
register i;

for (i=O;i<NCASILLAS;i++)
if (t[i]!=VACIO && t[i]!=BORRADO)
free(t[i]);

free t;
}

int Hash (char *cad)
{
int valor;
unsigned char *c;

for (c=cad, valor=0; *c; c++)
valor += (int)*c;

return (valor%NCASILLAS);
}

int Localizar (char *x,TablaHash t)

/* Devuelve el sitio donde esta x o donde deberia de estar. */
/* No tiene en cuenta los borrados. */

{
int ini,i,aux;

ini=Hash(x);

for (i=O;i<NCASILLAS;i++) {
aux=(ini+i)%NCASILLAS;
if (t[aux]==VACIO)
return aux;
if (!strcmp(t[aux],x))
return aux;
}
return ini;
}

int Localizar1 (char *x,TablaHash t)

/* Devuelve el sitio donde podriamos poner x */

{
int ini,i,aux;

ini=Hash(x);

for (i=O;i<NCASILLAS;i++) {
aux=(ini+i)%NCASILLAS;
if (t[aux]==VACIO || t[aux]==BORRADO)
return aux;
if (!strcmp(t[aux],x))
return aux;
}

return ini;
}

int MiembroHash (char *cad,TablaHash t)
{
int pos=Localizar(cad,t);

if (t[pos]==VACIO)
return 0;
else
return(!strcomp(t[pos],cad));
}

void InsertarHash (char *cad,TablaHash t)
{
int pos;

if (!cad)
error("Cadena inexistente.");

if (!MiembroHash(cad,t)) {
pos=Localizar1(cad,t);
if (t[pos]==VACIO || t[pos]==BORRADO) {
t[pos]=(char *)malloc((strlen(cad)+1)*sizeof(char));
strcpy(t[pos],cad);
} else {
error("Tabla Llena. \n");
}
}
}

void BorrarHash (char *cad,TablaHash t)
{
int pos = Localizar(cad,t);

if (t[pos]!=VACIO && t[pos]!=BORRADO) {
if (!strcmp(t[pos],cad)) {
free(t[pos]);
t[pos]=BORRADO;
}
}
}

[Enrique Lucas]

1.- Para implementar una estructura abstracta, debemos considerar
tres factores Velocidad de búsqueda, Uso de la memoria y La
información deba estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el porqué
justificándolo con código en java

Yo escogeria el uso de la memoria ya que una tabla hash asigna memoria
y si esta es muy pequeña aumentaran el número de colisiones.El
siguiente es un código que solo relaciona números con más números de
forma aleatoria.

Import java.util.*;

public class hash{

public static void main(String args[])throws Exception{

Hashtable hash= new HashTable(10,10);

for(int i=0;i<=100;i++);
{
Integer entero=new Integer(i);
Hash.put(entero,”Numero: ”+ i);
}


for(Enumeration e=hash.keys(); e.hasMoreElements();)
}

System.out.println(hash.get(e.nextElement()));

}
}


2.- Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción y eliminación, en la práctica difícilmente se
cumple, explique por qué. Investigue

En las tablas Hash los datos se guardan de acuerdos a valores y de
acuerdo a esto se realiza la busqueda la momento de devolver un valor.
Pero en la practica la busqueda se la hace en forma lineal es decir
que se busca una a una y mientras mas grande sea la tabla Hash mas
consumo de memoria tendra.




-3.- Implemente un ejercicio con Tablas Hash en Java.


public class CHash{

int aClave=0;
int [] aArreglo=new int[n];

public CHash(){
}

public int FuncionHash(int pElement){
}


public int FuncionHash2(string pelement){
}

public int solucionarColision(int pElement,int pNroCol){
}

public void Insertar(string pRegistro){
}

public void Buscar(string pElement,ref int posicion,ref bool Exist){
}

public void EliminarElemento(string pElement){
}



}

[Aldo Alvear]

1.- Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

1. Al decir verdad lo mas importante ya sea en una estructura
abstracta como en cualquier
otra impolementación debe ser el uso de memoria ya que de nada sirve
que la información
sea ordenada o no, o peor la busqueda si la memoria es lenta la
busqueda será lenta y a
su vez los datos serán lentos en verse


import java.util.*;

public class Direccion {
public static void main(String[] args) {

Hashtable direccion = new Hashtable();

Integer ocho = new Integer(8000);
direccion.put("calle","Primavera");
direccion.put("numero", ocho);
direccion.put("colonia"," La Silla ");
direccion.put("ciudad"," Monterrey ");
direccion.put("estado"," Nuevo Leon ");
direccion.put("pais","Mexico");

String miciudad = (String) direccion.get("ciudad");
String miestado = (String) direccion.get("estado");
String micalle = (String) direccion.get("calle");
Integer minumero = (Integer) direccion.get("numero");

System.out.println("Direccion : " + micalle + " " + minumero);
System.out.println("Lugar: " + miciudad + "," + miestado);

}
}


2. Las tablas hash botan un código único.

Esto en la práctica no se cumple ya que para muchos datos

mas de 10000, es mas propenso a errores. con menos datos bajo de 5000
es menos propenso a errores



3.Hashtable

Una Hashtable es una implementación concreta de un Dictionary. Se
puede utilizar una instancia de Hashtable para almacenar objetos
arbitrarios que están indexados por cualquier otro objeto arbitrario.
La utilización mas habitual de una Hashtable es utilizar una String
como clave para almacenar objetos como valores. El ejemplo siguiente
crea una Hashtable para almacenar información acerca de este libro:

import java.util.Dictionary;
import java.util.Hashtable;

class HTDemo {
public static void main(String args[]) {

Hashtable ht = new Hashtable();

ht.put("title", "Manual de Java");
ht.put("author", "Algunos");
ht.put("email", "nise...@puesalli.es");
show(ht);
}
static void show(Dictionary d) {

System.out.println("Título: " + d.get("title");
System.out.println("Autor: " + d.get("author");
System.out.println("E-mail: " + d.get("email");
}
}

La salida de este programa muestra cómo el método show, que toma un
Dictionay abstracto como parámetro, es capaz de recuperar todos los
valores que se han almacenado en el método main.

Properties

Properties en una subclase de Hashtable que añade algunos métodos
adecuados para obtener valores que puede que no estén definidos. Se
puede especificar un valor por omisión junto con el nombre en el
método getProperty; por ejemplo, getProperty("nombre","valor por
omisión"). Si no se encuentra la propiedad "nombre", se devuelve
"valor por omisión". Además, cuando se construye un objeto Properties,
se le puede pasar otra instancia de Properties en el constructor para
que se utilice como propiedades por omisión de la nueva instancia.

[Brian Cirino]

Pregunta 1:

Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el por
qué justificándolo con código en java.

RESPUESTA:
Mi respuesta seria la Velocidad de Búsqueda y la Información debe
estar ordenada o no ya que ambas están relacionadas entre sí, pero el
uso de Memoria no es indispensable ya que es un desperdicio en vano.
Entre muchos métodos de búsqueda tenemos el método de HASHING
Este método de búsqueda no necesariamente los datos deben estar
ordenados, no dependen de un número de elementos, y transforman los
datos en una dirección única
Ejemplo:

n= número de elementos en el vector
x= valor a buscar

void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !=
d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;
}
}
}

dx= posición en el vector del elemento a buscar

Pregunta 2:

Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción y eliminación, en la práctica difícilmente se
cumple, explique
por qué. Investigue

RESPUESTA:
No se cumple ya que al tener muchos datos las posibilidades de errores
son muchas que para pocos elementos, osea hablamos de 10000, 3990,
34343, etc,


Pregunta 2:

Implemente un ejercicio con Tablas Hash en Java.

RESPUESTA:
import java.io.*;

import java.util.*;

public class hash {

public static void main(String args[]) throws IOException {
int n = Integer.parseInt(args[0]);
int i, c;
String s = "";
Integer ii;

HashMap ht = new HashMap();

c = 0;
for (i = 1; i <= n; i++)
ht.put(Integer.toString(i, 16), new Integer(i));
for (i = 1; i <= n; i++)
if (ht.containsKey(Integer.toString(i, 10)))
c++;

System.out.println(c);
}
}

[Paul Paredes Acosta]

FORO DE ESTRUCTURAS DE DATOS

PRIMERA PREGUNTA


Escogería la primera Velocidad de búsqueda como factor importante
porque orden de búsqueda de los árboles binarios balanceados es O
(log2

(n)) siendo n la cantidad de elementos insertados. El orden de
inserción y eliminación de elementos a pesar de que tiene que realizar

operaciones para balancear el árbol, también tienden al mismo orden
que el de búsqueda.

SEGUNDA PREGUNTA

Porque al generar una clave hash única e irrepetible para cada

elemento es una tarea casi imposible para una cantidad grande de

elementos. Hablamos del orden de 10000 elementos o más.


TERCERA PREGUNTA

import java.util.*;


public class hash {

[Enrique Lucas]

> 1.-  Para implementar una estructura abstracta, debemos considerar
> tres factores Velocidad de búsqueda, Uso de la memoria y La
> información deba estar ordenada o no,
>    ¿Cuál escogería usted como factor principal?, indique el porqué
> justificándolo con código en java
>
> Yo escogeria el uso de la memoria ya que una tabla hash asigna memoria

> y si esta  es muy pequeña aumentarán el número de colisiones.El

> siguiente es un código que solo relaciona números con más números de
> forma aleatoria.
>
> Import java.util.*;
>
>  public class hash{
>
>                public static void main(String args[])throws Exception{
>                Hashtable hash= new HashTable(10,10);
>
>                for(int i=0;i<=100;i++);
>                 {
>                     Integer entero=new Integer(i);
>                     Hash.put(entero,”Numero: ”+ i);
>                 }
>
>                 for(Enumeration e=hash.keys(); e.hasMoreElements();)
>            }
>
>               System.out.println(hash.get(e.nextElement()));
>
>         }
>         }
>
> 2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
> búsqueda como inserción y eliminación, en la práctica difícilmente se
> cumple, explique por qué. Investigue
>
>  En las tablas Hash los datos se guardan de acuerdos a valores y de

> acuerdo a esto se realiza la búsqueda al momento de devolver un valor.
> Pero en la práctica la búsqueda se la hace en forma lineal es decir
> que se busca una a una y mientras más grande sea la tabla Hash más
> consumo de memoria tendrá.

>
> -3.- Implemente un ejercicio con Tablas Hash en Java.
>
> public class CHash{
>
>       int aClave=0;
>       int [] aArreglo=new int[n];
>
>      public CHash(){
>                           }
>
>      public int FuncionHash(int pElement){
>                                         }
>
>     public int FuncionHash2(string pelement){
>                                         }
>
>     public int solucionarColision(int pElement,int pNroCol){
>                                         }
>
>    public void Insertar(string pRegistro){
>                                        }
>
>   public void Buscar(string pElement,ref int posicion,ref bool Exist){
>                                         }
>
>   public void EliminarElemento(string pElement){
>                                         }
>
>
>

> }- Ocultar texto de la cita -
>
> - Mostrar texto de la cita -

[Joyce Jara]

 Estructuras De Datos 

> 1.- Para implementar una estructura abstracta, debemos considerar tres factores
> Velocidad de búsqueda, Uso de la memoria y La información deba estar ordenada o no,

> ¿Cuál escogería usted como factor principal?, indique el porqué justificándolo con código en java.

Pienso, que lo primero que uno se pregunta, es que estructura es la
más adecuada. Para contestarla correctamente debemos tener en cuenta
tres factores. Velocidad de búsqueda,
uso de la memoria y si la información debe estar ordenada o no.

Quizás el que menos importe para aplicaciones no-embebidas es el
punto
de la memoria. En general cualquier estructura que tenga un orden de

búsqueda decente no utiliza memoria al azar. Por lo que nos quedan dos

pesos pesados bien claros, velocidad de búsqueda y si la información
debe o no estar ordenada.

package arreglos;
public class Hash {
//Atributo
Object [] th;
//Constructor
public Hash(int n){
th=new Object[n];
for(int i=0; i<n;i++){
th[i]=null;
}
}
//Métodos
public void creaTabla(Object[]a, int nmax){
int pos;
for(int i=0; i<a.length;i++){
//Genera la posición del elemento a insertar
//Haciendo uso de una función hash
pos=a[i].hashCode()%nmax;
System.out.println("Elemento :"+a[i]+ " pos = " + pos);
//cuando la función devuelve un valor negativo
if(pos<0){
pos*=-1;
}
if(th[pos]==null){
//Inserta en la tabla sin colisión
th[pos]=a[i];
}else{
while(th[pos]!=null){
pos++;
if(pos==th.length){
pos=0;
}
}
//Inserta el valor en la tabla hash despues de una colicion
th[pos]=a[i];
}
}
presenta("TABLA HASH",th);

}
public void buscarHash(Object elemb, int nmax){
int e=elemb.hashCode();

Curso de Estructuras de Datos Orientada a Objetos
6

if(e<0){
e*=-1;
}
int pos=e%nmax;
if(th[pos]==null){
System.out.print("Elemento no encontrado");
}else{
if(th[pos].equals(elemb)){
System.out.print("Elemento encontrado, "+elemb+ " su posicion es : "+
pos);

}irse{

int j=pos+1;
if(j==th.length){
j=0;
}
while((th[j]!=elemb)&&(th[j]!=null)&&(j!=pos)){
j++;

if(j>=th.length-1){

j=0;
}
}
if(th[j].equals(elemb)){
System.out.print("Elemento encontrado, "+elemb+ " su posicion es : "+
j);
}else{
System.out.print("Elemento no encontrado");
}
}
}
}

public void presenta(String msg,Object a[]){
System.out.print(msg+" [");
for(int i=0; i<=a.length-1;i++){
if(i<a.length-1){
System.out.print(a[i]+",");
}else{
System.out.print(a[i]+"]");
}
}
System.out.print("\n");
}
public static void main(String args[]){
Object l[]= {12,45,76,34,90,45,56,78};
Hash bh=new Hash(l.length*2);
bh.presenta("Elementos a insertar en la Tabla Hash",l);
bh.creaTabla(l,l.length);
bh.buscarHash(34,l.length);
}
}
> 2.- Las tablas Hash, teóricamente tiende a un orden mínimo tanto en búsqueda como inserción y eliminación, en la práctica difícilmente se cumple, explique por qué. Investigue.
La tabla hash teóricamente tiende a un orden mínimo tanto en búsqueda
como inserción y eliminación, que sería O (1).
Esto en la práctica difícilmente se cumpla, ya que generar una clave

hash única e irrepetible para cada elemento es una tarea casi

imposible para una cantidad grande de elementos, hablamos del orden de
10000 elementos o más.

> 3.- Implemente un ejercicio con Tablas Hash en Java.

import java.util.*;
public class hash {

[Roberto Fernando Yépez Cárdenas]

FORO DE ESTRUCTURAS DE DATOS


PRIMERA PREGUNTA

La velocidad de búsqueda y la información debe estar ordenada ya que
ambos factores van unidos entre si, y la búsqueda debe estar basada

mediante una información ya dada; por eso también podríamos decir que
el uso de memoria no es tan indispensable.

Para buscar una información ya dada tenemos un metodo de busqueda
llamado HASHING.

Busqueda Hashing.- Método que puede aumentar la velocidad de búsqueda

donde los datos no necesitan estar ordenados. Independiente del número

n. Transformación de claves (clave - dirección) o hashing.- El hashing

consiste en convertir el elemento almacenado (numérico o alfanumérico)
en una dirección (índice) dentro del array.

n= número de elementos en el vector
x= valor a buscar
void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !
=d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;

dx= posición en el vector del elemento a buscar

SEGUNDA PREGUNTA

Las Tablas Hash tienden a un orden mínimo tanto en búsqueda como
inserción y eliminación porque al generar una clave hash unica e

irrepetible para cada elemento es una tarea casi imposible para una

cantidad grande de elementos. Hablamos del orden de 10000 elementos o
mas. Difícilmente se cumple por el problema de colisiones ya que estas

tienen que ser resueltas por una búsqueda lineal y la función tienden
a generar valores similares. Otro problema es el aglomeraniento cuando
las llaves usadas comúnmente tiendan a caer muy cerca unas de otras o
incluso consecutivamente en la tabla hash y esto degrada el

funcionamiento y cuando la tabla se llena usando ciertas estrategias
de resolución de colisiones, como el sondeo linea.





TERCERA PREGUNTA

Implementación de un ejercicio con Tabla Hash en Java.

[Carolina López]

1: Un algoritmo de búsqueda es el Hashing las cuales una de sus
características dice que la velocidad de búsqueda es mayor y no es
necesario que los datos estén ordenados.
Entonces podríamos decir que los dos factores más importantes son la
velocidad de búsqueda y que la información este ordenada o no.
El uso de memoria no sería tan importante ya que un momento dado se la
desperdiciaría.
Ejemplo:

n= número de elementos en el vector
x= valor a buscar
void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !=
d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;
}
}
}

2: la tabla hash teórica tiende a un orden mínimo tanto en
búsqueda como inserción y eliminación, que sería O(1). Esto en la

práctica difícilmente se cumpla, ya que generar una clave hash única

e
irrepetible para cada elemento es una tarea casi imposible para una
cantidad grande de elementos. Hablamos del orden de 10000 elementos o

más.

3:

import java.util.Dictionary;
import java.util.Hashtable;
class HTDemo {

public static void main(String args[]) {

Hashtable ht = new Hashtable();
ht.put("title", "Manual de Java");
ht.put("author", "Algunos");

ht.put("email", "nises...@puesalli.es");

show(ht);
}
static void show(Dictionary d) {

System.out.println("Titulo: " + d.get

("title"));
System.out.println("Autor: " + d.get
("author"));

System.out.println("E-mail: " + d.get
("email"));
System.out.println("");
}

[Victor Jaramillo]

1.-  

Pues a mi parecer el factor más importante a considerar es la
velocidad de la búsqueda ya que si nos ponemos a considerar los otros
factores, pues nos damos cuenta que estos son menos relevantes ya que

si hablamos del uso de la memoria nos damos cuenta que en este tiempo

disponemos de una cantidad enorme de memoria para poder trabajar y si
tomamos en cuenta el factor "Ordenamiento de Información" pues Las
tablas hash almacenan la información  en posiciones pseudo-aleatorias,
así que el acceso ordenado a su contenido es bastante lento.

public void buscarHash(Object elemb, int nmax){

          int x=elemb.hashCode();

           if(x<0){
           x =-1;
            }
                 int pos=x%nmax;
                 if(tabla[pos]==null){
                System.out.println("El Elemento no se encontro");
                 }else{
                          if(tabla[pos].equals(elemb)){

                           System.out.print("Elemento encontrado

"+elemb+ " su posicion es : "+ pos);

                           }else{
                           int j=pos+1;

                           if(j==tabla.length){
                           j=0;
                           }
                           while((tabla[j]!=elemb)&&(tabla[j]!=null)&&
(j!=pos)){
                            j++;
                                 if (j>=tabla.length-1){
                                            j=0;
                                 }
                           }
                           if(tabla[j].equals(elemb)){

                                           System.out.print("Elemento
encontrado, "+elemb+ " su posicion es :"+j);
                           }else{
                                         System.out.print("Elemento
no encontrado");
                                   }
                                 }
                              }
}

 

 

2.-

La teoría se cumple cuando podriamos estar hablando de pocos
elementos, pero es imposible que se cumpla cuando hablamos de muchos

elementos.
Ya que una tabla hash genera una clave única para cada elemento, por

eso para pocos datos si es posible; pero para una cantidad de datos

extensa, es más propenso a que ocurra algún error.

 

3.-

[Adrian Leon]

>  1.-  Para implementar una estructura abstracta, debemos considerar
> tres factores
>        Velocidad de búsqueda, Uso de la memoria y La información deba
> estar ordenada o no,
>        ¿Cuál escogería usted como factor principal?, indique el por
> qué justificándolo con código en java.

Dictionary<string, string> tabla = new Dictionary<string, string>();
try
{
using (StreamReader sr = new StreamReader
(Environment.CurrentDirectory + "\\Diccionario.txt"))
{
string linea = string.Empty;
while ((linea = sr.ReadLine()) != null)
{
string[] datos = linea.Split(':');
//Adicionamos la clave en mayusculas para que
no interfiera con la busqueda.
string clave = datos[0].ToUpper();
string valor = datos[1];
tabla.Add(clave, valor);
}
}
Console.WriteLine("Digite la clave que desea buscar o
teclee \"EXIT\" para salir");
string Comando = Console.ReadLine().ToUpper();
//Si se teclea "EXIT" se cierra el programa.
while (Comando.ToUpper() != "EXIT")
{
if (tabla.ContainsKey(Comando))
{
string valor = tabla[Comando];
Console.WriteLine("La definición para {0} es:
{1}", Comando, valor);
}
else
{
//La Clave no existe.
Console.WriteLine("La clave buscada no
existe.");
}
Console.WriteLine("Oprima una tecla para realizar
otra busqueda");
Console.ReadLine();
Console.Clear();
Console.WriteLine("Digite la clave que desea
buscar o teclee \"EXIT\" para salir");
Comando = Console.ReadLine().ToUpper();

}
}
catch (Exception e)
{
Console.WriteLine("Error en el archivo: ");
Console.WriteLine(e.Message);
}




Quizas el que menos importe para aplicaciones no-embebidas es el punto

de la memoria. En general cualquier estructura que tenga un orden de

búsqueda decente no utiliza memoria a mansalva.

Por lo que nos quedan dos pesos pesados bien claros, velocidad de
búsqueda y si la información debe o no estar ordenada.

Las dos estructuras obvias que uno piensa en estos casos son: arboles

binarios balanceados (AVL o rojo-negro por ejemplo) y la sencilla pero
ingeniosa tabla hash.

Recordemos que el órden de búsqueda de los arboles binarios
balanceados es O(log2(n)) siendo n la cantidad de elementos
insertados.





>

>  2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
> búsqueda como inserción
>       y eliminación, en la práctica difícilmente se cumple, explique
> por qué. Investigue

La tabla hash teórica tiende a un orden mínimo tanto en búsqueda como

inserción y eliminación, que sería O(1). Esto en la práctica

dificilmente se cumple, ya que generar una clave hash única e

irrepetible para cada elemento es una tarea casi imposible para una
cantidad grande de elementos.


>

>  3.- Implemente un ejercicio con Tablas Hash en Java.
>

[Roberto Rodriguez]

.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-..-.-.-.-.-.-.-.-.-.-.-.-.-.-

...:::
1er. Tema :::..

Para implementar una estructura abstracta, debemos considerar tres

factores:
- Velocidad de
búsqueda
- Uso de la
memoria
- La información deba estar ordenada o no,

¿Cuál escogería usted como factor
principal?

Para mí las más importantes son:
1.- Velocidad de Búsqueda.
(Para que el programa sea más eficiente a la hora de la búsqueda de un
archivo)

2.- La información deba estar ordenada o no.
(Es muy importante ya que así podemos editar, encontrar y a su vez
tener información más rápido)

Programa:

void HASHING(){
int A=0,E=0;
A=(x%n)+1;
if (a[A] = = x)
printf("NUMERO NO EXISTENTE");

else{
dx = A + 1;
while( (A<n) && (a[E] != x) && (a[E] != 0) && (E !=d) ){
E = E + 1;
if(E == n)
E = 1;
}
}
}
._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._.._._._._._._._._._.





.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-..-.-.-.-.-.-.-.-.-.-.-.-.-.-
...::: 2do.
Tema :::...

Para la segunda pregunta la respuesta seria que las Tablas Hash dan a
cada archivo un código único, pero cuando se la aplica (Tabla Hash)
tiende a tener algunos errores.

Cuando las Tablas Hash se la aplican para muchos archivos o números
muy extensos hay errores, entonces este código se lo aplicaría cuando
los números o datos son pequeños ya que así tendría menos errores.

._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._.._._._._._._._._._





.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-..-.-.-.-.-.-.-.-.-.-.-.-.-.-
...:::
3er. Tema :::...
...::: EJERCICIO CON TABLAS
HASH EN JAVA :::...

public class hash {
public static void main(String arg[]) {

Hashtable xd = new Hashtable();
xd.put("Name", "Roberto Rodriguez");
xd.put("University", "Universidad Politecnica
Salesiana");
xd.put("Carrera", "Ingenieria en sistema");
show(xd);
}
static void show (Dictionary h) {

System.out.println("Nombre: " + h.get
("Name"));
System.out.println("Universidad: " + h.get
("University"));
System.out.println("Carrera: " + h.get
("Carrera"));

}

}
._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

[Roberto Rodriguez]

EJERCICIO CON TABLAS HASH EN JAVA

public class hash {
public static void main(String arg[]) {

Hashtable xd = new Hashtable();
xd.put("Name", "Roberto Rodriguez");
xd.put("University", "Universidad Politecnica Salesiana");
xd.put("Carrera", "Ingenieria en sistema");
show(xd);
}
static void show (Dictionary h) {

System.out.println("Nombre: " + h.get("Name"));
System.out.println("Universidad: " + h.get("University"));

[johan gosdenovich]

1.-) Para implementar una estructura abstracta, debemos considerar
tres factores
Velocidad de búsqueda, Uso de la memoria y La información deba
estar ordenada o no,

¿Cuál escogería usted como factor principal?, indique el por

qué justificándolo con código en java.*

Respuesta-->>
Yo podria escoger el uso de la memoria debido que una tabla hash
asigna memoria
y si 'esta es de tamaño pequeño aumentarián el número de las
colisiones realizadas.

El tamaño N es un parámetro de vital importancia para el correcto
funcionamiento de
la estructura. Si N es demasiado alto, las operaciones serán muy
eficientes, pero
desperdiciaremos demasiado espacio. Si por el contrario, N es
demasiado bajo, las
colisiones se dispararán y la estructura tendrá un rendimiento muy
parecido a la
solución trivial propuesta al principio del artículo. Por tanto,
elegir N no es en
absoluto banal. Además, uno de los fundamentales problemas de las
tablas Hash es que
una vez puesta en funcionamiento, la única forma de hacer crecer N es
hacer una
estructura nueva y copiar los datos que ya hubiera en la antigua: N no
se puede
cambiar dinámicamente.
Además, el N adecuado depende de la estrategia empleada en la
resolución de colisiones.
En el caso de la dispersión cerrada:


Nº de elementos en la tabla/N < 0,5 es decir, si planeamos tratar con
un máximo de,
por ejemplo 5000 registros, se tiene 5000 / N < 0,5, de donde N >
5000*2, es decir
, tomaríamos como N el primer primo mayor que 10000.


Nosotros utilizaremos funciones basadas en la operación módulo. En
primer lugar,
obtenemos un numero a partir de la clave alfanumérica utilizada y
luego hacemos
la operación modulo N sobre ese numero. Así obtendremos una posición
donde almacenar
nuestro elemento. A tener en cuenta que N (el tamaño de la tabla) ha
de ser un
número primo, pues sino, solo influirían en la determinación de la
posición
correspondiente a un determinado elemento las últimas cifras del
número generado a
partir de la clave alfanumérica .

private static int Hash1(String Clave) {

int valor = Clave.charAt(0);
int tam = Clave.length();

for (int i = 1; i < tam ;i++) {

valor += Character.getNumericValue( Clave.charAt(i));

}

return (valor % N);

}

2.-) Las tablas Hash, teóricamente tiende a un orden mínimo tanto en

búsqueda como
inserción y eliminación, en la práctica difícilmente se cumple,
explique por qué.

Investigue. *


respuesta--->>>

Esto dificilmente se cumpledebido a que generar una clave hash unica e

irrepetible
para cada elemento es una tarea casi imposible para una cantidad
grande de elementos.

Hablamos del orden de 10000 elementos o mas.

unsigned int jenkins_one_at_a_time_hash(void *vkey)
{
unsigned hash = 0;
size_t i;
unsigned char *key;
int key_len;


key = (unsigned char *)vkey;

key_len = strlen(key);

for (i = 0; i < key_len; i++) {
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}

Al ser algo inevitable la repetición de entradas podemos aprovechar
esto como un fuerte
para disminuir el uso de los lugares no utilizados, un buen número
para la longitud de
la tabla es entre un 30% y un 60% del total de los items que tenemos
(o planeamos tener).
Por lo tanto, para 10.000 elementos deberiamos tener una tabla de
3.000 a 6.000 elementos.

3.- Implemente un ejercicio con Tablas Hash en Java.

Respuesta--->>>

Supongamos que una ferretería nos contrata para que les implantemos un
sistema de gestión
de sus proveedores. Para cada proveedor desean guardar el nombre de
proveedor, el nombre
de la persona de contacto, el número de teléfono, el correo
electrónico y el descuento sobre
la tarifa base. Desean poder acceder a toda la información de un
proveedor a partir de su NIF.

public class TProveedor {

/**************
** Atributos **
**************/

// Datos que vamos a guardar de cada proveedor
private String NIF;
private String nomEmpresa;
private String nomContacto;
private String numTelefono;
private String email;
private int dto = 0;

/******************
** Constructores **
******************/

// Constructor General de la clase Proveedor: inicializa los Strings
public TProveedor (String NIF,String empresa,String contacto,String
email,String Tlf,int dto) {

this.NIF = NIF;
this.nomEmpresa = empresa;
this.nomContacto = contacto;
this.email = email;
this.numTelefono= Tlf;
this.dto = dto;
}

// Constructor compacto
public TProveedor (String NIF,String empresa) {

this.NIF = NIF;
this.nomEmpresa = empresa;
}

/*********************
** Metodos publicos **
*********************/

// gets para obtener los datos de un proveedor

public String getNif() {

return this.NIF;
}

// **************************************
public String getEmpresa() {

return this.nomEmpresa;
}

// **************************************
public String getContacto() {

return this.nomContacto;
}

// **************************************
public String getTlf() {

return this.numTelefono;
}

// **************************************
public int getDto() {

return this.dto;
}

// **************************************
public String getMail() {

return this.email;
}

// sets complementarios:

public void setNIF (String N) {

this.NIF = N;
}

// **************************************
public void setEmpresa (String N) {

this.nomEmpresa = N;
}

// **************************************
public void setContacto (String N) {

this.nomContacto = N;
}

// **************************************
public void setTlf (String N) {

this.numTelefono = N;
}

// **************************************
public void setDto (int nuevo) {

this.dto = nuevo;
}

// **************************************
public void setMail (String nuevo) {

this.email = nuevo;
}
}

Saludos.
Johan
Gosdenovich
WOW

[rony andres teran marin]

rony teran marin

>  1.-  Para implementar una estructura abstracta, debemos considerar

> tres factores
>        Velocidad de búsqueda, Uso de la memoria y La información deba
> estar ordenada o no,
>        ¿Cuál escogería usted como factor principal?, indique el por
> qué justificándolo con código en java.

-Yo escojeria como factor principal a la velocidad de búsqueda y a que
la información deba estar ordenada o no, el orden de inserción y

eliminación de elementos a pesar de que tiene que realizar
operaciones para balancear el árbol, también tienden al mismo orden
que el de búsqueda.

aquí lo justifíco con el siguiente programa:

import java.util.*;

public class hash {

public static void main (String args[]) throws Exception {
Hashtable hash = new Hashtable(10,10);

for (int i = 0; i <= 100; i++)
{
Integer entero = new Integer ( i );
hash.put( entero, "Numero : " + i);
}

for (Enumeration e = hash.keys(); e.hasMoreElements();)
{
System.out.println (hash.get(e.nextElement()));
}
}
}

>  2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en

> búsqueda como inserción
>       y eliminación, en la práctica difícilmente se cumple, explique

> por qué. Investigue:

La función de hash está definida por su dominio

(cadenas de bytes de longitud variable), su imagen (secuencias de
bytes de longitud fija) y por la función que relaciona dichos

conjuntos (llamada función H). Ya que una tabla hash genera una clave

única para cada elemento, por
eso para pocos datos si es posible; pero para una cantidad de datos

extensa, es más propenso a que ocurra algún error o algo que nos pueda
hacer caer el programa.

>  3.- Implemente un ejercicio con Tablas Hash en Java.

public int hash(int codi){
int cont1=codi;
int cont2=codi;
int cont3=codi;
int posi=0;
cont1=cont1/10000;
cont2=(cont2-cont1*10000)/100;
cont3=(cont3-(cont1*10000))-cont2*100;
posi=cont1+cont2+cont3;
return posi;
}


> Saludos cordiales
> RONY TERAN MARIN

[rony andres teran marin]

Rony Andrés Terán Marín

[rommel zuñiga]

Ya que una tabla hash genera una clave única para cada elemento, por
eso para pocos datos si es posible; pero para una cantidad de datos

extensa, es más propenso a que ocurra algún error.
3.-
import java.util.*;

[Lelibeth]

1.-  Para implementar una estructura abstracta, debemos considerar
tres factores Velocidad de búsqueda, Uso de la memoria y La
información deba estar ordenada o no,
¿Cuál escogería usted como factor principal?, indique el porqué
justificándolo con código en java.

El factor principal es la velocidad de búsqueda ya que permite el
acceso a los elementos (teléfono y dirección, por ejemplo) almacenados
a partir de una clave generada usando el nombre, número de cuenta o
id. Funciona transformando la clave con una función hash en un hash,
un número que la tabla hash utiliza para localizar el valor deseado.

import java.io.*;
public class Hash
{
String datos[];
File archivo;
BufferedReader flujo;
public Hash(String tipodearchivo)
{
try
{
archivo=new File(tipodearchivo);
flujo= new BufferedReader(new FileReader(archivo) );
}catch(Exception e){};
datos=new String[1000];
for(int i=0;i<datos.length;i++)
{
datos[i]="";
}
}
public void truncamiento()
{
String nombre;
String cifras="";
try
{
System.out.println("Datos de la lista:");
while((nombre=flujo.readLine())!=null)
{
System.out.println(nombre);
byte bt[]=nombre.getBytes();
for(int i=0;i<nombre.length();i++)
{
cifras+=bt[i];
}
cifras=truncar(cifras);
validar(Integer.parseInt(cifras),nombre);
cifras="";

}
}catch(Exception e){};
}
public String truncar(String cadena)
{
String truncado;
truncado=cadena.substring(0,1)+cadena.substring(2,3)+cadena.substring
(cadena.length()-1,cadena.length());
return truncado;
}
public void validar(int posicion,String elemento)
{
if(datos[posicion].equals(""))
{
datos[posicion]=elemento;
}
else
{
colicionar(elemento);
}
}
public void colicionar(String elemento)
{
for(int i=0;i<datos.length;i++)
{
if(datos[i].equals(""))
{
datos[i]=elemento;
break;
}
}
}
public void busqueda(String elemento)
{
String posicion="";
byte bt[]=elemento.getBytes();
for(int i=0;i<elemento.length();i++)
{
posicion+=bt[i];
}
posicion=truncar(posicion);
buscar(Integer.parseInt(posicion),elemento);
}
public void buscar(int posicion,String elemento)
{
if(datos[posicion].equals(elemento))
{
System.out.println(datos[posicion]+". Elemento en la posicion:
"+posicion);
}
else
{
encontrar(elemento);
}
}
public void encontrar(String nombre)
{
int j=0;;
for( int i=0;i<datos.length;i++)
{
if(datos[i].equals(nombre))
{
System.out.println(datos[i]+". Elemento en la posicion: "+i);
break;
}
j++;
}
if(j>999)
{
System.out.println("El elemento no fue encontrado cheque que se
\nencuentre en la lista o verifique su gramatica: ");

}
}
public static void main(String args[])
{

try
{
String archivo;
archivo=args[0];
Hash hash=new Hash(archivo);
hash.truncamiento();
BufferedReader b=new BufferedReader(new InputStreamReader
(System.in));
System.out.println("busqueda de:");
String nombre =b.readLine();
hash.busqueda(nombre);
}catch(Exception e){System.out.println("TIenes que introducir por
consola el nombre del archivo\nnombres.txt");}

}
}

 2.-  Las tablas Hash, teóricamente tiende a un orden mínimo tanto en
búsqueda como inserción y eliminación, en la práctica difícilmente se
cumple, explique por qué. Investigue

En la práctica dificilmente se cumple, ya que generar una clave hash
única e irrepetible para cada elemento es una tarea casi imposible

para una cantidad grande de elementos. Hablamos del orden de 10000
elementos o mas.

3.- Implemente un ejercicio con Tablas Hash en Java.

Esta es una implementación de una hashtable en java, solo relaciona
numeros con mas números de forma automática.

[Isaac Guerrero Palacios]

1era PREGUNTA
La más importante seria velocidad de busqueda,y luego si la
informacion esta ordenada o no. La memoria no es importante ya que
ahora vienen con mucho mas memoria y eso no es problema en las nuevas
pc.
Las tablas hash almacenan la informacion en posiciones
pseudoaleatorias, asi que el acceso ordenado a su contenido es
bastante lento. Otras estructuras como arboles binarios auto-
balanceables son más lentos en promedio (tiempo de busqueda O(log n))
pero la informacion esta ordenada en todo momento. Las tablas hash son
mas utiles cuando se almacenan grandes cantidades de informacion.
Ejemplo

void Hashing(){
int d=0,dx=0;
d=( x%n)+1;
if(a[d] = = x )
printf("valor encontrado");
else{
dx = d + 1;
while( (d < n) && (a[dx] != x) && (a[dx] != 0) && (dx !=
d) ){
dx = dx + 1;
if(dx = = n)
dx = 1;
}
}
}

2da PREGUNTA
Se cumpliria siempre y cuando sean pocos elementos, ya que una tabla
has genrea una clave para cada elemento. Pero al hablar de 10000
elementos es imposible.

3era PREGUNTA
import java.util.Dictionary;
import java.util.Hashtable;
class Foro {

public static void main(String args[]) {

Hashtable ht = new Hashtable();

ht.put("title", "Libro de Java");
ht.put("author", "NN");
ht.put("email", "prof...@ups.ec");
ht.put("direccion", "Mall Sur Local 78");

show(ht);
}
static void show(Dictionary d) {
System.out.println("Titulo: " + d.get
("title"));
System.out.println("Autor: " + d.get
("author"));
System.out.println("E-mail: " + d.get
("email"));

System.out.println("Direccion: " + d.get
("direccion"));
System.out.println(""); }

[Guillermo Vinces]

1.- Para implementar una estructura abstracta, debemos considerar
tres factores:

Velocidad de búsqueda, Uso de la memoria y la información deba
estar ordenada o no... ¿Cuál escogería usted como factor principal?

Escogería velocidad de búsqueda, porque usualmente buscamos
información en base a un criterio (o clave) y las tablas hash ofrecen
una forma sencilla de hacerlo.


Este ejemplo crea una tabla Hash de número. Esta tabla utiliza el
nombre del número como llave (clave) de búsqueda:

Hashtable numbers = new Hashtable();
numbers.put("uno", new Integer(1));
numbers.put("dos", new Integer(2));
numbers.put("tres", new Integer(3));

Para recuperar un número utilizamos el siguiente código:

Integer n = (Integer) numbers.get("dos");
if (n != null) {
System.out.println("dos = " + n);

}


2.- Las tablas Hash, teóricamente tiende a un orden mínimo tanto
en búsqueda como inserción y eliminación, en la práctica difícilmente

se cumple;
explique por qué. Investigue.

Para una cantidad pequeña de datos se cumple teóricamente el orden
mínimo de busqueda para la inserción y la eliminación, sin embargo, en
grandes cantidades de datos generar una clave HASH única para cada
registro es casi imposible, con lo cual el orden mínimo de busqueda no
se cumple.

Por otra parte, considere un pequeño grupo de datos de estudiantes de
un curso cualquiera donde la clave HASH está basada en la fecha de
nacimiento, la generación de claves HASH puede llegar a duplicarse
(colisionar) en pocos registros.

3.- Implemente un ejercicio con Tablas Hash en Java.

// Usar iteraciones con una tabla Hash
import java.util.*;

class HTDemo1 {

public static void main(String args[]) {

Hashtable balance = new Hashtable();

String str;
double bal;

balance.put("Roggenio Solm", new Double(3434.34));
balance.put("Eduardo Mite", new Double(123.22));
balance.put("Emilio Menjivar", new Double(1378.00));
balance.put("Eduardo Menjivar", new Double(99.22));
balance.put("Ricardo Wolf", new Double(-19.08));

// Mostrar todos los balances en la hashtable
Set set = balance.keySet(); // obtener el conjunto de claves

// Obtener las iteraciones
Iterator itr = set.iterator();

while(itr.hasNext()) {
str = (String) itr.next();
System.out.println(str + ": " + balance.get(str));
}

System.out.println();

// Depositar 1,000 en la cuenta de Eduardo Mite
bal = ((Double) balance.get("Eduardo Mite")).doubleValue();
balance.put("Eduardo Mite", new Double(bal+1000));

System.out.println("Eduardo Mite (nuevo balance): " +
balance.get("Eduardo Mite"));
}
}