Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 154 vistas

    HashTables en Java

    Cargado por

    a3ito
    El documento describe las tablas hash y cómo se utilizan para implementar estructuras de datos de diccionario. Explica que las tablas de direccionamiento directo solo funcionan para conjuntos pequeños de datos, mientras que las tablas hash pueden manejar conjuntos más grandes al almacenar los datos en cadenas enlazadas para manejar colisiones cuando las funciones hash generan la misma posición para claves diferentes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd

    HashTables en Java

    Cargado por

    a3ito
    154 vistas25 páginas
    El documento describe las tablas hash y cómo se utilizan para implementar estructuras de datos de diccionario. Explica que las tablas de direccionamiento directo solo funcionan para conjuntos pequeños de datos, mientras que las tablas hash pueden manejar conjuntos más grandes al almacenar los datos en cadenas enlazadas para manejar colisiones cuando las funciones hash generan la misma posición para claves diferentes.

    Título original

    HashTables en java

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe las tablas hash y cómo se utilizan para implementar estructuras de datos de diccionario. Explica que las tablas de direccionamiento directo solo funcionan para conjuntos pequeños de datos, mientras que las tablas hash pueden manejar conjuntos más grandes al almacenar los datos en cadenas enlazadas para manejar colisiones cuando las funciones hash generan la misma posición para claves diferentes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    154 vistas25 páginas

    HashTables en Java

    Cargado por

    a3ito
    El documento describe las tablas hash y cómo se utilizan para implementar estructuras de datos de diccionario. Explica que las tablas de direccionamiento directo solo funcionan para conjuntos pequeños de datos, mientras que las tablas hash pueden manejar conjuntos más grandes al almacenar los datos en cadenas enlazadas para manejar colisiones cuando las funciones hash generan la misma posición para claves diferentes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 25

    Hash Tables

    Ing. Andrea Quan

    Diccionarios
    Algunas aplicaciones necesitan una estructura de datos que soporte las operaciones de un diccionario: insert, search y delete Este tipo de Estructuras, se enfocan en estas tres operaciones y buscan eficientizarlas. Una HashTable es una buena forma de guardar una estructura de diccionario, sobretodo porque facilita la bsqueda de los elementos

    Direct-address Tables
    Un Direct-address table es una forma simple de implementar una estructura de diccionario cuando el nmero de datos a guardar es relativamente pequeo. Se caracteriza por manejar los datos por medio de una llave o key:
    Cada dato a guardar tiene una llave o key asociada, que es nica. Para cada key existe una nica posicin en la tabla.

    Direct-address Tables
    Como se implementara:
    Si tenemos un conjunto de datos cuyas keys asociadas estn dentro del conjunto U = {0,1 .. , m-1} donde m es un nmero relativamente pequeo. Para representar una Direct-Address table utilizamos un arreglo T de m casillas, en el cual cada casilla corresponde a una key en U

    Direct-address Tables
    En Java:
    public class DAddressTable { Object[] tabla; public DAddressTable(int numberofkeys){ tabla = new Object[numberofkeys]; }

    Direct-address Tables
    T
    0 1 2

    Tabla en donde se guardaran los datos

    Direct-address Tables
    T
    0 1 2 DATO

    Direct-address Tables
    T
    0 1 2 key(dato) k k DATO

    Direct-address Tables
    T
    0 1 2 key(dato) k k DATO

    El key representa la posicin en la que el dato debe ir


    m

    Direct-address Tables
    0 1 2

    DATO

    Direct-address Tables
    El diccionario opera trivialmente con estas operaciones: INSERT x T[key(x)] = x DELETE x T[key(x)] = null SEARCH x return T[key(x)] SEARCH key return T[key] o

    Direct-address Tables
    public int key(Object dato) { } public void insert(Object dato) { tabla[this.key(dato)] = dato; } public void delete(Object dato) { tabla[this.key(dato)]= null; } public boolean search(Object dato) { return !(table[this.key(dato)] == null); } public boolean search(int key) { return !(table[key] == null); }

    Direct Address Table Hash Tables


    Cual es el problema con las Direct Address Tables?
    Si el numero de datos a guardar es muy grande, poder guardar un arreglo de ese tamao seria impractico, o imposible por la memoria. El numero real de datos en la tabla puede ser muy pequeo en comparacin con el tamao de la tabla.

    Solucin: HASHTABLES!!
    Cuando el set de keys guardadas en un diccionario es mucho mas pequeo que el universo de posibles keys, una hash table requiere mucho menos almacenamiento que una direct-address table.

    Direct Address Table Hash Tables


    Cual es el problema con las Direct Address Tables?
    Si el numero de datos a guardar es muy grande, poder guardar un arreglo de ese tamao seria impractico, o imposible por la memoria. El numero real de datos en la tabla puede ser muy pequeo en comparacin con el tamao de la tabla.

    Solucin: HASHTABLES!!
    Cuando el set de keys guardadas en un diccionario es mucho mas pequeo que el universo de posibles keys, una hash table requiere mucho menos almacenamiento que una direct-address table.

    Direct Address Table Hash Tables


    Cual es el problema con las Direct Address Tables?
    Si el numero de datos a guardar es muy grande, poder guardar un arreglo de ese tamao seria impractico, o imposible por la memoria. El numero real de datos en la tabla puede ser muy pequeo en comparacin con el tamao de la tabla.

    Solucin: HASH TABLES!!


    Cuando el set de keys guardadas en un diccionario es mucho mas pequeo que el universo de posibles keys, una hash table requiere mucho menos almacenamiento que una direct-address table.

    Hash Tables
    A diferencia de un Direct Adress Table, el HashTable tiene un tamao menor al numero de elementos posibles (U) El key, ya no representa la posicin del dato, y puede ahora ser de cualquier tipo. Las posiciones de los datos, son calculadas de diferente forma, ya que ahora ya no pueden existe una asociacin directa key-posicin.

    Hash Tables
    DATO key (dato)
    K Key del dato

    El hash value es la posicin en la que se guardar el dato en la hash table

    hashfunction (k)

    Hash value o hashcode

    Hash Tables
    0 1 2 k H Hashfunction(k) DATO key(dato)

    Hash Tables
    0 U h (k2)

    k2 K k3 k1 k4

    h (k1) h (k4)

    h (k3) m

    Hash Tables
    Qu problema hay con tener una tabla de tamao mas pequeo al nmero de keys posibles?

    Collision
    Dato 1 Dato 2

    k1

    k2

    h(k1)

    h(k2)

    Collision
    0 U h (k1) = h (k2)

    k2 K k3 k1 k4 h (k4)

    h (k3) m

    Chaining
    Existen varias formas de solucionar el problema de colisiones, pero una de las mas utilizadas es: chaining. Chaining consiste en que cada casilla de la tabla guarda una lista encadenada, y no solo un dato.

    Chaining
    0 U k1 k2

    k2 K k3 k1 k4 k6 k5 k4 k5 k6

    k3 m

    Hashtable
    import java.util.LinkedList; import java.util.ArrayList; public abstract class HashTable<E> { ArrayList<LinkedList<E>> table; public HashTable(int size) { table = new ArrayList<LinkedList<E>>(size); for (int i=0; i<size; i++) { table.add(i,new LinkedList<E>()); } } public abstract Object key(E dato); public abstract int hashfunction(Object key); public abstract void insert(E dato); public abstract E delete(Object key); public abstract boolean searchDato(E dato); public abstract E searchKey(Object key); }

    También podría gustarte