11. Métodos de búsqueda

Última modificación por Mario Gorga López el 2021/12/06 09:20
  • Manage
  • Administer Parent
  • Copiar
  • Renombrar
  • Eliminar
  • Actions
  • Exportar
  • Vista previa de la impresión
  • Ver fuente
  • Compartir por correo
  • Viewers
  • Siblings
  • Comentarios
  • Adjuntos (4)
  • Historial
  • Información
Contenidos

Objetivos

Los objetivos de este módulo son los siguientes:

  • Consolidar los algoritmos de búsqueda estudiados en Fundamentos de Programación
  • Entender cómo se puede usar la recursividad en los algoritmos de búsqueda
  • Entender qué es el hashing y cómo se puede utilizar para hacer búsquedas

Introducción

La búsqueda de información, ya sea en tablas, TAD o árboles binarios es una funcionalidad básica en el mundo de la programación ya que en la mayoría de aplicaciones informáticas lo que se hace es gestionar información. Es a decir, se guarda información para posteriormente tratarla de diferentes maneras.

De hecho, todos los buscadores de Internet, por ejemplo, solicitan unos criterios de búsqueda y retornan los elementos encontrados:

  • Búsquedas de trabajo.
  • Búsquedas de tiendas.
  • Búsquedas de cualquier otro tipo.

Los algoritmos de búsqueda son, por lo tanto, un elemento importante dentro de la informática y algunos pueden llegar a ser muy complejos para poder conseguir obtener la información deseada en el mínimo tiempo posible.

En Fundamentos de Programación ya se introdujeron dos algoritmos de búsqueda sobre tablas:

  • Búsqueda secuencial.
  • Búsqueda dicotómica (sobre tablas ordenadas).

En este módulo se presentan los mismos algoritmos pero utilizando memoria dinámica (lista encadenadas) y recursividad. También se introduce el concepto de hashing , método muy rápido utilizado para insertar y buscar elementos en una tabla cuando se dan unas condiciones especiales

Ejemplos

En Fundamentos de Programación se vio cómo hacer una búsqueda secuencial sobre una tabla utilizando métodos iterativos. A continuación se presentan dos ejemplos secuenciales pero recursivos: uno usando tablas y otro usando listas encadenadas y luego un tercer ejemplo usando la búsqueda dicotómica pero de forma recursiva.

Ejemplo I: algoritmo recursivo de búsqueda secuencial sobre una tabla

Supongamos que tenemos una tabla para guardar libros y queremos escribir un algoritmo recursivo para encontrarlos. Recordemos que la recursividad implicaba definir:

Caso base: en este algoritmo debemos tratar dos casos base: si el libro no está presente o si ya lo hemos encontrado.

Caso recursivo: si el libro no está en la primera posición de la tabla, hacemos una llamada recursiva pasando la misma tabla a la que le hemos extraído el primer elemento.

La cabecera de la función deberá tener en cuenta los siguientes parámetros:

  1. La tabla.
  2. El punto de la tabla donde estamos mirando si está el libro.
  3. El valor que estamos buscando.

Si el libro se encuentra en la tabla, la función retornará la posición donde se encuentra el libro, en caso contrario retornará -1.

Veamos cómo queda el algoritmo completo. Hemos primero insertado libros en la tabla para poder probar el algoritmo de búsqueda.

[Ejemplo 11_01]

const
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: string;
     end record

    tTableBooks = record
        books: vector[MAX_BOOKS] of tBook;
        numBooks: integer;
    end record;
end type

algorithm linearRecursiveSearch

    var
        listBooks: tTableBooks;
        i: integer;
        index: integer;
    end var

    { insert info to the table }
    listBooks.numBooks:= MAX_BOOKS;
    for i:=1 to listBooks.numBooks do
        listBooks.books[i].id : = i;
        listBooks.books[i].title:= "BOOK" + i;
    end for

    { search info on the table}
    i := readInteger();
    while i > 0 and i <= MAX_BOOKS do
        index = findBook(listBooks, 1, i);
        writeInteger(index);
        if index ≠ -1 then
            writeString(listBooks.books[index].title);
        else
            writeString("Book Not Found");
        end if
        i := readInteger();
    end while

end algorithm

function findBook(table: tTableBooks, ini: integer, value: integer): integer

    { base case. The first position is 1 and the last is MAX_BOOKS }
    if ini = MAX_BOOKS+1 then
        return -1;
    { recursive case }
    else
        if table.books[ini].id = value then
            return ini;
        else
            return findBook(table, ini+1, value);
        end if
    end if

end function


#include <stdio.h>
#include <string.h>

#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct {
    tBook books[MAX_BOOKS];
   int numBooks;
} tTableBooks;

int findBook(tTableBooks table, int ini, int value);

int main(int argc, char **argv) {

    tTableBooks listBooks;
   int i;
   int index;

   // insert info to the table
    listBooks.numBooks = MAX_BOOKS;
   for (i=0; i<listBooks.numBooks; i++) {
        listBooks.books[i].id = i_1;
        sprintf(listBooks.books[i].title, "BOOK %d\0", i_1);
    }

   // search info on the table
    printf("Next Book: ");
    scanf("%d", &i);
   while (i>=0 && i<MAX_BOOKS) {
        index = findBook(listBooks, 0, i);
       if (index >= 0) {
            printf("The book is : %s\n ", listBooks.books[index].title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}

int findBook(tTableBooks table, int ini, int value) {
   // base case. The first position is 0 and the last is MAX_BOOKS-1
    if (ini == MAX_BOOKS) {
       return -1;
    } else {
       // recursive case
        if (table.books[ini].id == value) {
           return ini;
        } else {
           return findBook(table, ini_1, value);
        }
    }
}

Nota: se ha utilizado el operador "+" para indicar una concatenación de la cadena "BOOK" y el número entero i, para formar nombres de libros que se pudieran distinguir.

Ejemplo II: algoritmo de búsqueda secuencial sobre una lista encadenada

A continuación vamos a ver coóo se hace una búsqueda secuencial sobre una lista encadenada.

En este caso, los parámetros que debe recibir la función son la lista y la clave del elemento a buscar. La función devolverá un puntero al elemento de la lista que contiene el libro, si éste se encuentra en la lista o null en caso contrario. La función sería:

[Ejemplo 11_02]

const
    MAX_LETTERS: integer = 50;
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: vector[MAX_LETTERS] of char;
    end record

    tListBooks = record
        book tBook;
        nextBook pointer to tListBooks;
    end record
end type

function findBook(first: pointer to tListBooks, id: integer): pointer to tListBooks
    var
        found: boolean;
        temp: pointer to tListBooks;
    end var

    temp := first;
    found := false;

    while temp≠NULL and not found do
        if temp->book.id = id then
            found := true;
        else
            temp := temp->nextBook;
        end if
    end while

     return temp;
end function

/* program presentació */
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct tListBooks {
    tBook book;
   struct tListBooks *nextBook;
} tListBooks;

typedef enum {FALSE, TRUE} boolean;

tListBooks *insertBook(tListBooks *first, tBook book);
tListBooks *findBook(tListBooks *first, int id);

int main(int argc, char **argv) {

    tListBooks *listBooks;
    tListBooks *temp;
    tBook book;
   int i;
    tListBooks *index;

   /* although now we can insert any number of books at the list, we insert MAX_BOOKS as in the previous example*/

    listBooks = NULL;
   for (i=1; i<=MAX_BOOKS; i++){
        book.id = i;
        sprintf(book.title, "BOOK %d\0", i);
        listBooks = insertBook(listBooks, book);
    }
    temp = listBooks;

    printf("Next Book: ");
    scanf("%d", &i);
   while (i > 0) {
        index = findBook(listBooks, i);
       if (index != NULL) {
            printf("The book is : %s\n ", index->book.title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}

tListBooks *insertBook(tListBooks *first, tBook book) {

    tListBooks *temp;

    temp = malloc(sizeof(tListBooks));
    temp->nextBook = first;
    temp->book.id = book.id;
    strcpy(temp->book.title, book.title);
   return temp;
}

tListBooks *findBook(tListBooks *first, int id){
    boolean found;
    ListBooks *temp;

    temp = first;
    found = FALSE;
   while (temp!=NULL && !found) {
       if (temp->book.id == id) {
            found = TRUE;
        } else {
            temp = temp->nextBook;
        }
    }
   return temp;
}

Nota: en el apartado de programación en C se ha añadido un pequeño programa para probar la función.

Ejemplo III: algoritmo recursivo de búsqueda dicotómica sobre una tabla ordenada

Los algoritmos vistos en los dos ejemplos anteriores tienen un tiempo de ejecución igual al visto en el módulo Introducción a la complejidad. Son algoritmos lineales y su complejidad es de orden O( n ) siendo n el número de elementos en la tabla.

Cómo ya se vio en Fundamentos de Programación, cuando una tabla está ordenada por una clave se pueden utilizar otro tipo de algoritmos más eficientes.

La idea de la búsqueda binaria ó dicotómica es la siguiente: si tenemos la tabla ordenada, no empezamos a buscar desde el inicio de la tabla sino que empezamos por en medio. El proceso es el siguiente:

  1. Calculamos la posición del medio de la tabla.
  2. Comparamos su contenido con el valor buscado.
  3. Si el contenido es el valor buscado se acaba la búsqueda. En caso contrario, hacemos lo siguiente:
    1. Si el elemento del medio es mayor que el buscado, podemos descartar la segunda mitad de la tabla. El elemento buscado, si existe debe estar en la primera mitad (parte izquierda).
    2. En caso contrario descartamos la primera mitad. El elemento buscado, si existe debe estar en la segunda mitad (parte de la derecha).
  4. Aplicamos el mismo procedimiento a la parte de la tabla que no se ha descartado.

En los apuntes de Fundamentos de Programación, en el módulo de tablas, podéis encontrar un ejemplo de cómo funciona el algoritmo.

Vamos a ver ahora la versión recursiva de este algoritmo. Como podemos ver, la propia definición anterior es una definición recursiva.

Utilizando los mismos tipos de datos que en el ejemplo I:

[Ejemplo 11_03]

const
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: string;
    end record

    tTableBooks = record
        books: vector [MAX_BOOKS] of tBook;
        numBooks: integer;
    end record
end type

/* program presentació */
#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct {
    tBook books[MAX_BOOKS];
   int numBooks;
} tTableBooks;

Analicemos cual debe ser la cabecera de la función. Hay diferentes maneras de definirla, pero en este caso optamos por pasar la tabla entera y dos enteros que indican el principio y final de la sub tabla sobre la que hay que buscar la clave.

La cabecera será:

[Ejemplo 11_04]

function findBookBin(table: tTableBooks, first: integer, last: integer, value: integer): integer

int findBookBin(tTableBooks table, int first, int last, int value)

Caso base: el algoritmo se basa en que en cada llamada de la función se descarta la mitad de la tabla ya que al estar ordenada, comparando el valor buscado con el que hay en la posición del medio podemos saber si se puede encontrar en la mitad derecha o izquierda. Por lo tanto llega un momento en que la mitad sobre la que debemos buscar está vacía. En este caso acaba la recursividad y el elemento no está en la tabla. Esto ocurre cuando first > last.

Caso recursivo: si el valor buscado es menor que el valor en la posición del medio de la tabla, llamamos recursivamente a la función con la mitad izquierda de la tabla, sino con la mitad derecha.

La función queda:

[Ejemplo 11_05]

function findBookBin(table: tTableBooks, first: integer, last: integer, value: integer): integer

    var
        middle: integer;
    end var

    if first ≤ last then
        middle := (first + last) div 2;
        if (table.books[middle].id = value) then
            return middle;
        else
            if (table.books[middle].id < value)
                return findBookBin(table, middle+1, last, value); { recursivo con la parte derecha }
            else
                return findBookBin(table, first, middle-1, value); { recursivo con la parte izquierda }
            end if
        end if
    end if

    { cas base }
    return -1;

end function

int main(int argc, char **argv) {

    tTableBooks listBooks;
   int i;
   int index;

   for (i=0; i<MAX_BOOKS; i++) {
        listBooks.books[i].id = i+1;
        sprintf(listBooks.books[i].title, "BOOK %d\0", i+1);
        listBooks.numBooks = MAX_BOOKS;
    }

    printf("Next Book: ");
    scanf("%d", &i);
   while (i > 0) {
        index = findBookBin(listBooks, 0, listBooks.numBooks, i);
       if (index >= 0) {
            printf("The book is : %s\n ", listBooks.books[index].title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}


int findBookBin(tTableBooks table, int first, int last, int value) {

   int middle;

   if (first <= last) {
        middle = (first + last) / 2;
       if (table.books[middle].id == value) {
           return middle;
        } else {
           if (table.books[middle].id < value) {
               return findBookBin(table, middle+1, last, value);
            } else {
               return findBookBin(table, first, middle-1, value);
            }
        }
    }

    { cas base }
   return -1;
}

Nota: igual que en el caso anterior, en C se ha incluído un pequeño programa para probar la función.

En este caso, la complejidad del algoritmo es O(log( n )) ya que en cada llamada recursiva la medida de la tabla se divide por dos.

En los ejemplos anteriores se han visto algoritmos ya conocidos pero diseñados con resursividad. En el siguiente apartado vamos a ver un concepto nuevo que se puede utilizar en algunas situaciones y que permite insertar y buscar en un tiempo constante de O(1).

Tablas hash

En los métodos vistos en los ejemplos anteriores hemos buscado una clave a base de recorrer la tabla o descartando la mitad en cada iteración, con una complejidad de O( n ) y O(log( n )) respectivamente.

Sería interesante si, dada una clave, en lugar de tener que buscarla, fuese posible saber directamente donde sse encuentra en función de la propia clave. De esta manera podríamos encontrar el elemento buscado sin necesidad de compararlo con muchas otras claves de la tabla.

Ejemplo IV

Imaginemos que tenemos el siguiente tipo de datos, que identifica un producto en una tienda de plantas.

[Ejemplo 11_06]

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
    end record
end type


typedef struct {
   int id;
   char *description;
   int stock;
} tProduct;

Queremos definir una tabla en la que guardar los productos de la tienda sabiendo que habrá un máximo de 100 productos distintos.

Como nos dejan escoger el identificador de cada tipo de planta, decidimos usar los identificadores del 1 al 100. En este caso, el identificador de la planta se puede utilizar para acceder directamente a la tabla ya que podemos mapear directamente el conjunto de identificadores con las posiciones de la tabla. En lenguaje C usaremos idenficadores del 0 al 99 porque la primera posición es el 0. Para usar ids del 1 al 100 habría que restar 1 al id, pero en los ejemplos se parte de la premisa que el id se corresponde con la posición de la tabla. La definición de los tipos de datos sería la siguiente:

[Ejemplo 11_07]

const
    MAX_PRODUCTS: integer = 100;
end const

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
    end record

    tListProducts = record
        products: vector[MAX_PRODUCTS] of tProduct;
        numProducts: integer;
    end record
end type

#define MAX_PRODUCTS 100

typedef struct {
   int id;
   char *description;
   int stock;
} tProduct;

typedef struct {
    tProduct products[MAX_PRODUCTS];
   int numProducts;
} tListProducts;

Para añadir un producto a la tabla podemos utilizar una inserción directa, es decir, utilizar la i-ésima posición del vector para guardar el producto con el identificador i.

Es decir, quedaría tan simple como:

[Ejemplo 11_08]

action insertProduct(inout list: tListProducts, in p: tProduct)
    list.products[p.id] := p;
    list.numProducts := list.numProducts + 1;
end action

void insertProduct(tListProducts *list, tProduct p) {
    list->products[p.id] = p;
    list->numProducts++;
}

Para buscar si hay stock de un producto concreto la función se reduce a:

[Exemple 11_09]

function search(list: tListProduct, id: integer): boolean

    if (list.products[id].stock > 0) then
        return true;
    else
        return false;
    end if

end function

typedef enum {FALSE, TRUE} boolean;

boolean search(tListProduct list, int id) {

   if (list.products[id].stock > 0) {
       return TRUE;
    } else {
       return FALSE;
    }
}

Como podemos ver, no ha hecho falta hacer un recorrido para encontrar el producto ni tampoco una búsqueda binaria ya que se dispone de un método para saber, dada una clave, dónde encontrarla directamente en la tabla.

Ahora bien, la situación presentada en este ejemplo es muy simple y normalmente las situaciones reales son más complejas y no es tan fácil mapear el conjunto de posibles claves con las posiciones de la tabla.

Ejemplo V

Continuemos con el mismo ejemplo de antes pero con las siguientes especificaciones:

  • sabemos que como mucho tendremos 100 productos.
  • id de los productos ahora nos vienen dados y serán números entre el 1000 y el 9999.

La estrategia anterior ya no sirve ya que por un lado no sabemos cuáles serán los ids de los productos que tendrá la tienda, y aunque los supiésemos no podríamos mapear directamente los id con las posiciones de la tabla.

Necesitamos buscar una función que mapee los números del 1000 al 9999 a valores entre el 0 y el 99. Es decir, una función que calcule, en función del id del producto, una posición única en la tabla, de forma que permita saber dónde insertarlo y dónde ir a buscarlo.

Una forma fácil de hacerlo es utilizar el operador módulo. La tabla siguiente muestra el resultado que se obtendría a al aplicar el operador módulo 100 a algunos identificadores de productos:

id f(id)
3876 76
8765 65
2345 45
9999 99
5688 88
1111 11

Con esta función podemos utilizar el mismo código de antes pero aplicando una pequeña modificación. Antes de insertar o buscar un identificador hay que calcular la posición de la tabla que le corresponde al identificador tratado. Quedaría como sigue:

[Ejemplo 11_10]

action insertProduct(inout list: tListProducts, in p: tProduct)
    list.products[f(p.id)+1] := product; { en C no hará falta sumar 1 }
    list.numProducts := list.numProducts + 1;
end action

function f(id: integer): integer

    return (id mod 100);
end function

function search(list: tListProduct, id: integer): boolean
 var
     pos: integer;
 end var
     pos := f(id)+1;
    if (list.products[pos] ≠ NULL and list.products[pos].stock > 0) then
        return true;
    else
        return false;
end function

typedef enum {FALSE, TRUE} boolean;

void insertProduct(tListProducts *list, tProduct p) {

    list->products[f(p.id)] = product;  /* en C no hace falta sumar 1 */
    list->numProducts++;
}

int f(int id) {
   return (id mod 100);
}

boolean search(tListProduct list, int id) {
   int pos;
    pos = f(id);
   if (list.products[pos] != NULL && list.products[pos].stock > 0) {
       return TRUE;
    } else {
       return FALSE;
    }
}

Con el cambio introducido, se ha creado una función que permite insertar y buscar elementos de forma directa en la tabla.

Ahora bien, la solución que dada tiene un problema y es que la función no es inyectiva, es decir dos identificadores diferentes pueden ser asignados a la misma posición de la tabla. Este hecho recibe el nombre de colisiones. De hecho, la mayoría de funciones hash tiene problemas de colisiones, por lo que hay que buscar algún método para solventarlas.

Definiciones

Las tablas hash son tablas que permiten insertar y buscar elementos de forma muy rápida dentro de una tabla. Para hacerlo se utiliza una función matemática que calcula la posición única de cada elemento en la tabla. Esta función de denomina función hash. Tanto la operación de inserción como la de búsqueda son de O(1).

Las tablas hash tienen algunos inconvenientes:

  • Como es una tabla, su medida debe estar prefijada, para saber cómo calcular la posición.
  • La tabla no se puede ordenar (no se puede sacar información ordenada sin hacer previamente una operación de ordenación).
  • Se pueden generar colisiones, como hemos visto en el ejemplo anterior.

Cómo tratar las colisiones

Vamos a ver un par de maneras de tratar las colisiones

Hashing abierto: uso de memoria dinámica

En el hashing abierto lo que se hace es crear una tabla que en lugar de guardar directamente los elementos, se crea una tabla de apuntadores (poinetrs) a elementos.

Para cada inserción se crea un elemento nuevo y se inserta en la lista que cuelga de la posición de la posición de la tabla que le corresponde. Para buscar el elemento se recorre la lista que cuelga de la posición de la tabla que le corresponde al elemento. Siguiendo el mismo ejemplo que antes definiremos:

[Ejemplo 11_11]

const
    MAX_PRODUCTS: integer = 100;
end const

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
        next: pointer to tProduct;
    end record

    listProducts = record 
         products: vector[MAX_PRODUCTS] of pointer to tProduct;
         numProducts: integer;
    end record
end type

#define MAX_PRODUCTS 100

typedef struct tProduct {
   int id;
   char *description;
   int stock;
   struct tProduct *next;
} tProduct;

typedef struct {
    tProduct *products[MAX_PRODUCTS];
   int numProducts;
} tListProducts;

El siguiente dibujo muestra cómo quedaría la tabla. Podemos ver que cuando hay una colisión se forma una lista encadenada con origen en la posición de la tabla correspondiente.

11_01.svg

Hashing cerrado

En el hashing cerrado, las colisiones se resuelven buscando una posición libre dentro de la propia tabla.

La inserción se realiza de la siguiente manera: si la posición que le corresponde está vacía, se inserta directamente; si está ocupada se busca en la tabla una posición vacía. La manera de buscar posiciones vacías puede hacerse de diversas maneras. Por ejemplo sumando uno a la posición hasta encontrar una vacía. Si se llega a la última posición de la tabla se continúa a partir de la posición 1. La siguiente imagen muestra como quedaría.

11_02.svg

A continuación se presenta un ejemplo sencillo de cómo se implementaría un hashing cerrado.

Ejemplo VI

Vamos a ver un ejemplo que utiliza la técnica de hashing cerrado para tratar las colisiones. Para calcular la posición hash utilizaremos el método de división (uso del operador módulo).

En el ejemplo hemos supuesto que para un evento cultural a la que asistirán entre unas 2500 y 2800 personas se quiere crear una lista de preinscritos (se apuntarán por internet) que posteriormente se podrá consultar para confirmar la asistencia de las personas.

Supondremos que las personas se identifican con su DNI (sin la letra). Para simplificar el ejemplo, la única información que se dará de cada persona, a parte de su DNI, que será la clave de acceso, será su nombre.

Veamos primero cómo definimos los tipos de datos, teniendo en cuenta que la tabla la definiremos de 3041 elementos. El valor escogido es un número primo ya que el uso de los primos hace que las colisiones sean menores.

[Ejemplo 11_11]

const
    MAX_SIZE: integer = 3041;
end const

type
    tElem = record
        key: integer;
        name: string;
        next: integer;
    end record

    tHasTable = record
        size: integer;
        numElem: integer;
        list: vector[MAX_SIZE] of tElem
    end record
end type

define MAX_SIZE 3041

typedef enum {FALSE, TRUE} boolean;

typedef struct {
   int key;   /* clave */
   char *name;   /* datos a guardar */
   int next;   /* si hay colisión, siguiente elemento */
} tElem;

typedef struct {
   int size;
   int numElem;
    tElem list[MAX_SIZE];
} tHashTable;

Es decir, hemos definido un tipo estructurado, tElem, para definir la información de la persona (key, name) y donde es encuentra el siguiente elemento (next), en caso de colisión También hemos definido una tabla donde guardar los elementos.

A continuación escribimos la función para calcular el valor hash que le corresponde a una clave dada. Como hemos dicho, utilizamos el modulo para calcularla. Concretamente usamos el número 3041, por ser un número primo superior a la afluencia esperada.

La función será:

[Ejemplo 11_12]

function hashFunction(key: integer): integer
    return (key mod MAX_SIZE) + 1;
end function

int hashFunction(int key) {
   return(key % MAX_SIZE);
}

Como podemos ver, la función que hemos escogido es simple.

Para poder implementar la inserción de los elementos en la tabla, primero es necesario inicializarla, por lo que hay que escribir una función o acción de inicialización. Hay que fijarse que el campo next se inicializa a -1 para indicar que no apunta a ningún elemento de la tabla.

[Ejemplo 11_13]

action initHashTable(inout t: tHashTable)

    var
        i: integer;
    end var

    t.size := MAX_SIZE;
    t.numElem:= 0;

    for i:=1  to MAX_SIZE do
        t.list[i].key = -1;
        t.list[i].next = -1;
    end for

end action

void initHashTable(tHashTable *t) {
   int i;
    t->size = MAX_SIZE;
    t->numElem = 0;

   for (i=0; i<MAX_SIZE; i++) {
        t->list[i].key = -1;
        t->list[i].next = -1;
    }
}

Ahora hay que diseñar la función de inserción:

[Ejemplo 11_14]

action insertElem(inout t: tHashTable, in key: integer, in name: string)

    var
        h: integer;
        next, previous: integer;
        found: boolean;
    end var

   if (t.numElem = MAX_SIZE) then
        writeString("Sorry but the registration is full");
   else
        h := hashFunction(key);
        found := false;
        next := h;
        previous := h;

        while not found do
            if t.list[next].key = -1 then
                found := true;
                t.list[next].key := key;
                t.list[next].name := name;
                if (next ≠ previous) then
                    t.list[previous].next := next;
                end if
            else
                writeString("Collision at ");
                writeInteger(next);
                previous := next;
                next := (next + 1) mod MAX_SIZE;
            end if
        end while
    end if
end action

typedef enum {FALSE, TRUE} boolean;

void insertElem(tHashTable *t, int key, char *name) {
   int h;
   int next, previous;
    boolean found;
   if (t->numElem == MAX_SIZE) {
        printf("Sorry but the registration is full");
    } else {
        h = hashFunction(key);
        found = FALSE;
        next = h;
        previous = h;

       while (!found) {
           if (t->list[next].key == -1) {
                found = TRUE;
                t->list[next].key = key;
                t->list[next].name = malloc(sizeof(*name));
                strcpy(t->list[next].name, name);
               if (next != previous) {
                    t->list[previous].next = next;
                }
            } else {
                printf("Collision at %d\n", next);
                previous = next;
                next = (next + 1) mod MAX_SIZE;
            }
        }
    }
}

Por último falta la función de búsqueda:

[Ejemplo 11_15]

function findElem(t: tHashTable, key:integer): integer

    var
        h: integer;
        found: boolean;
    end var

    h := hashFunction(key);
    found := false;

    while not found and t.list[h].key ≠ -1 do
        if t.list[h].key = key then
            found := true;
        else
            h: = t.list[h].next;
        end if*
    end while

    if found then
        return h;
    else
        return -1;
    end if

end function

typedef enum {FALSE, TRUE} boolean;

int findElem(tHashTable t, int key) {

   int h;
    boolean found;

    h = hashFunction(key);
    found = FALSE;

   while (!found && t.list[h].key != -1) {
       if (t.list[h].key == key) {
            found = TRUE;
        } else {
            h = t.list[h].next;
        }
    }

   if (found) {
       return h;
    } else {
       return -1;
    }
}

A continuación presentamos el algoritmo completo con un pequeño programa para probarlo:

[Ejemplo 11_16]

const
    MAX_SIZE: integer = 3041;
end const

type
    tElem = record
        key: integer;
        name: string;
        next: integer;
    end record

    tHasTable = record
        size: integer;
        numElem: integer;
        list: vector[MAX_SIZE] of tElem
    end record
end type

algorithm hash

    var
        list: tHashTable;
        i: integer;
        cell: integer;
        key: integer;
        name: string;
    end var

    initHashTable(list);
    key := 12345678;
    name := "NAME12345678";
    insertElem(list, key,name);

    key := 98563211;
    name := "NAME98563211";
    insertElem(list, key,name);

    key := 33330001;
    name := "NAME33330001";
    insertElem(list, key,name);

    key := 30410641;
    name := "NAME30410641";
    insertElem(list, key,name);

    cell := findElem(list, 30410641 );
    if cell != -1 then
        writeString("Key 30410641 has been found at cell");
        writeInteger(cell);
    else 
        printf("Value not found\n");
    end if

    cell := findElem(list, 33330001 );

    if cell != -1 then
        writeString("Key 33330001has been found at cell");
        writeInteger(cell);
    else
        writeString("Value not found\n");
    end if

    cell := findElem(list, 55558888 );

    if cell != -1 then
        writeString("Key 55558888 has been found at cell");
        writeInteger(cell);
    else 
        writeString("Value not found\n");
    end if

end algorithm

function hashFunction(key: integer): integer
    return (key mod MAX_SIZE) + 1;
end function

action insertElem(inout t: tHashTable, in key: integer, in name: string)

    var
        h: integer;
        next, previous: integer;
        found: boolean;
    end var

    if t.numElem = MAX_SIZE then
        writeString("Sorry but the registration is full");
    else
        h := hashFunction(key);
        found := false;
        next := h;
        previous := h;

        while not found do
            if t.list[next].key = -1 then
                found := true;
                t.list[next].key := key;
                t.list[next].name := name;
                if next ≠ previous then
                    t.list[previous].next := next;
                end if
            else
                writeString("Collision at ");
                writeInteger(next);
                previous := next;
                next := (next + 1) mod MAX_SIZE;
            end if
        end while
    end if

end action

function findElem(t: tHashTable, key:integer): integer

    var
        h: integer;
        found: boolean;
    end var

    h := hashFunction(key);
    found := false;
    while not found and t.list[h].key ≠ -1 do
        if t.list[h].key = key then
            found := true;
        else 
            h: = t.list[h].next;
        end if*
    end while

    if found then
        return h;
    else
        return -1;
    end if
end function

action initHashTable(inout t: tHashTable)

    var
        i: integer;
    end var

    t.size := MAX_SIZE;
    t.numElem:= 0;
    for i:=1 to MAX_SIZE do
        t.list[i].key = -1;
        t.list[i].next = -1;
    end for

end action

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MAX_SIZE 3041

typedef enum {FALSE, TRUE} boolean;

typedef struct {
   int key;
   char *name;
   int next;
} tElem;

typedef struct {
   int size;
   int numElem;
    tElem list[MAX_SIZE];
} tHashTable;

void initHashTable(tHashTable *t) {
   int i;
    t->size = MAX_SIZE;
    t->numElem = 0;

   for (i=0; i<MAX_SIZE; i++) {
        t->list[i].key = -1;
        t->list[i].next = -1;
    }
}

int hashFunction(int key) {
   return (key % MAX_SIZE);
}

int insertElem(tHashTable *t, int key, char *name) {

   int h;
   int next, previous;
    boolean found;

   if (t->numElem == MAX_SIZE) {
       return -1;
    }

    h = hashFunction(key);
    found = FALSE;
    next = h;
    previous = h;

   while (!found) {
       if (t->list[next].key == -1) {
            found = TRUE;
            t->list[next].key = key;
            t->list[next].name = malloc(sizeof(*name));
            strcpy(t->list[next].name, name);
           if (next != previous) {
                t->list[previous].next = next;
            }
        } else {
            printf("Collision at %d\n", next);
            previous = next;
            next = (next + 1) % MAX_SIZE;
        }
    }

   return next;
}

int findElem(tHashTable t, int key) {

   int h;
    boolean found;

    h = hashFunction(key);
    found = FALSE;

   while (!found && t.list[h].key != -1) {
       if (t.list[h].key == key) {
            found = TRUE;
        } else {
            h = t.list[h].next;
        }
    }

   if (found) {
       return h;
    } else {
       return -1;
    }
}

int main(int argc, char **argv) {

    tHashTable list;
   int cell;
   int key;
   char *name;

    initHashTable(&list);

    key = 12345678;
    name = "NAME12345678";
    cell = insertElem(&list, key,name);

    key = 98563211;
    name = "NAME98563211";
    cell = insertElem(&list, key,name);

    key = 33330001;
    name = "NAME33330001";
    cell = insertElem(&list, key,name);

    key = 30410641;
    name = "NAME30410641";
    cell = insertElem(&list, key,name);

    cell = findElem(list, 30410641 );
    printf("Key 30410641 has been found at cell %d\n", cell);

    cell = findElem(list, 33330001 );
    printf("Key 33330001 has been found at cell %d\n", cell);

    cell = findElem(list, 55558888 );
    printf("Key 55558888 has been found at cell %d\n", cell);

   return 0;
}

Resumen

En este módulo hemos revisado

  1. Métodos de búsqueda utilizando recursividad.
    1. Sobre tablas.
    2. Sobre listas encadenadas.
  2. Se ha introducido el concepto de hashing.
    1. Definición.
    2. Métodos para resolver colisiones.
Etiquetas:
[_]
Creado por editor1 el 2018/09/17 11:41