Taules Hash

  • ¿Cual es el principal problema de usar un Array a usar una Tabla Hash a la hora de insertar, eliminar o buscar un elemento? Victor Costa Vidal
    • Que el array es un tipo de dato muy inflexible, mientras que una Tabla Hach es mucho más flexible, permitiendo trabajar mejor con sus elementos.
  • En que consisteix el rehasing? Jose Daniel Ferrando Ferrer
    • El rehashing consisteix en incrementar el tamany de la taula de dispersió, reduint aixina el seu factor de carrega.
  • Quan ocorre una col·lisió? Jordi Belda Felipe
    • Una col·lisió es produix quan una funció de dispersió genera un mateix index de vector (cubeta) per a elements diferents. Aquesta és inevitable si hi ha més tipus de clau que posicions en el vector.
  • En que consisteix el menanisme de resolució de col·lisions d'encadenament(adreçament tancat)? Joan Pedro Martí
    • Cada cubeta conté una llista amb tots els parells(clau, valor) corresponents a aquelles claus que han produït l'index corresponent per mitjà de la funció de dispersió.
  • Anomena dos tipus de mecanismes per a tractar les col·lisions. David García Agost
    • Adreçament obert(open addressing) i Encadenament(separate chaining)o adreçament tancat.
  • En general, quines tres característiques té una taula de dispersió (hash)? Iris López Martínez
    • L'ús d’un vector per a accedir a les dades les components del qual es denominen cubetes, una funció de dispersió per a obtenir un índex del vector a partir de la clau a cercar o a inserir i un mecanisme per a resoldre les col·lisions.
  • Quines propietats ha de complir la funció hash o de dispersió? Héctor Serrano
    • Obligatori: Que siga determinista i que done el mateix valor per a claus iguals segons equals.
    • Inevitable: És possible que dos valors diferents acaben caient en la mateixa cubeta (col·lisió). És inevitable si hi han més claus que cubetes.
    • Desitjable: Que siga ràpida d’avaluar i que totes les cubetes reben aproximadament el mateix nombre d’elements.
  • Què es coneix con dispersió perfecta(perfect hashing) i per a que serveix? Daniel Sanchez
    • El perfect hashing es coneix com una funció de dispersió ad-hoc per al conjunt de claus conegut a priori de manera que no es produïsquen col.lisions. Permet implementacions molt eficients de diccionaris estàtics.
  • Quins inconvenients tenen les taules de dispersió amb adreçament obert? José Joaquin Rubio Iñigo
    • No permeten emmagatzemar un nombre d’elements major que la talla del vector.
    • El cost d’inserir creix de manera dramàtica quan la taula comença a omplir-se.
    • En esborrar un element cal marcar la posició de manera especial per a saber que en cercar cal seguir cercant però en inserir es pot considerar un buit.
  • Explica el procés de redispersió (rehashing) per a passar de N1 a N2 cubetes: Javier Martínez Bernia
    • Fase 1: Crear una taula nova amb N2 cubetes sense perdre la referència a la taula anterior.
    • Fase 2: Traslladar cadascun dels nodes a la nova taula. S'ha de calcular de nou el hashCode perquè els nodes canviaran de cubeta.
    • Fase 3: Deixar de referenciar la taula original per a que el recol·lector de brossa la puga eliminar.
  • Què és un map i per a què servix? Ana Maria Adam Lieberos
    • És un diccionari o un array associatiu el qual guarda parells clau, valor on ninguna clau es repetida. Aquest mecanisme permet buscar per clau ja que, donada una clau qualsevol, busca si està en el map i recupera el seu valor associat.
  • En l'implementació d'un Map amb una llista enllaçada, Quin es el cost d'inserir, cercar i esborrar? Antonio Manuel Sirvent Juan
    • El cost d'inserir, cercar i esborrar és lineal amb el nombre d'entrades de la cubeta, en el pitjor cas cal recórrer tota la llista, i en un cas mitjana, si cada valor tinguera la mateixa probablitat, el cost es el factor de carrega.
  • Què caracteritza a una taula de dispersió (hash)? María Alabau Bosque
    • 1. L'ús d’un vector per a accedir a les dades.
    • 2. Una funció de dispersió per a obtenir un índex del vector a partir de la clau a cercar o a inserir.
    • 3. Un mecanisme per a resoldre les col·lisions.
  • Existeix una taula Hash universal de cost òptim? Per què? Guillermo Montilla Tomás
    • Existeix una taula Hash ideal però es ínutil buscar-la ja que no sabem el nombre d’elements a emmagatzemar.
  • ¿Que es una tabla hash? Miguel Ángel Mateo Casali
    • Una tabla Hash es un contenedor asociativo (Diccionario) que permite un almacenamiento y posterior recuperación eficientes de elementos (Valores) a partir de otros objetos (Claves).
  • Quines són les característiques principals de les taules de dispersió amb adreçament obert? Juan Carlos Asensi Cavero
    • -Els valors es guarden en el propi vector.
    • -Cada cubeta conté com a màxim un parell (clau, valor).
    • Si en inserir un element la cubeta ja està ocupada, cal cercar una altra posició fins a trobar una posició lliure.
    • Existeixen diverses formes de cercar una altra posició (totes elles implementant circularitat):
    • -Exploració lineal: anem avançant l’índex en intervals constants (normalment d’1 en 1).
    • -Doble hashing: a partir de la clau obtenim tant l’índex inicial com el salt o increment.
    • -Exploració quadràtica: des del primer índex anem sumant 1^2, 2^2, 3^2, … , i^2, …
  • ¿Com es calcula el factor de càrrega? Laura Medina Chaveli
  • Nombre d’elements dividit entre el nombre de cubetes
  • ¿Cuál sería principal problema de que, para implementar una tabla hash, si utilizáramos un array? Su tipo de datos sería el tipo de datos de los objetos que queremos guardar y usaríamos las distintas posiciones del array como claves. Andrea Murcia Serrano
    • Que solo funcionaría en aquellos casos en los que la clave fuera un int.
  • Per a què s'utilitza un histograma d'ocupació? Mireia Vico Burruezo
    • És una manera gràfica de veure com de ben dispersats estan els elements d'una taula.
  • Que ens indica la mitjana o factor de càrrega? I la variància? Arnau Mompo Alepuz
    • El factor de càrrega ens indica quants elements hi han de mitjana per cubeta , mentre que la variància ens diu com de pròxima està la ocupació de totes les cubetes a la mitjana.
  • Respecte a la distribució de les claus a una Taula Hash, quina sería la distribució óptima? I quin el pitjor cas? Miguel Alejandro Muñoz Gil
    • -El cas ideal es aquell on totes les llistes son de longitud 1.
    • -Mentre que el pitjor cas és el que comprén una sola llista de la longitud del array de cubetes i la resta de cubetes están buides.
  • Quina característica ha de complir forçosament una taula hash ? Stella Esparza Torregrosa
    • S'ha de donar la mateixa posició per a la mateixa clau.
  • Respecte a les propietats d'una taula hash ¿Quins son els valors óptims per al factor de càrrega i la dispersió? Marc Gavilán Gil
    • -Factor de càrrega: 1
    • -Dispersió: 0
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License