hash_search.cpp File Reference

Hash Search Algorithm - Best Time Complexity Ω(1) More...

#include <cstdlib>
#include <iostream>

Include dependency graph for hash_search.cpp:

Classes
struct	list

Macros
#define	MAX   6
	Determines how much data.
#define	HASHMAX   5
	Determines the length of the hash table.

Typedefs
typedef struct list	node
typedef struct list *	link
	pointer to nodes

Functions
int	h (int key)
void	create_list (int key)
int	hash_search (int key, int *counter)
int	main ()

Variables
int	data [MAX] = {1, 10, 15, 5, 8, 7}
	test data
node	hashtab [HASHMAX]
	array of nodes

Detailed Description

Hash Search Algorithm - Best Time Complexity Ω(1)

Copyright

2020 Arctic2333

In this algorithm, we use the method of division and reservation remainder to construct the hash function, and use the method of chain address to solve the conflict, that is, we link a chain list after the data, and store all the records whose keywords are synonyms in the same linear chain list.

Warning

This program is only for educational purposes. It has serious flaws in implementation with regards to memory management resulting in large amounts of memory leaks.

Todo

fix the program for memory leaks and better structure in C++ and not C fashion

Typedef Documentation

node

typedef struct list node

a one-way linked list define node as one item list

Function Documentation

create_list()

void create_list

(

int

key

)

The same after the remainder will be added after the same hash header To avoid conflict, zipper method is used Insert elements into the linked list in the header

Parameters

[in]

key

key to add to list

Warning

dynamic memory allocated to n never gets freed.

Todo

fix memory leak

                          {  // Construct hash table
    link p, n;
    int index;
    n = (link)malloc(sizeof(node));
    n->key = key;
    n->next = NULL;
    index = h(key);
    p = hashtab[index].next;
    if (p != NULL) {
        n->next = p;
        hashtab[index].next = n;
    } else {
        hashtab[index].next = n;
    }
}

Here is the call graph for this function:

h()

int h

(

int

key

)

Mode of hash detection : Division method

Parameters

[in]

key

to hash

Returns

hash value for key

Examples

/Users/runner/work/C-Plus-Plus/C-Plus-Plus/numerical_methods/rungekutta.cpp.

{ return key % HASHMAX; }

hash_search()

int hash_search	(	int	key,
		int *	counter )

Input the key to be searched, and get the hash header position through the H (int key) function, then one-dimensional linear search. If found

Returns

element depth and number of searches If not found

-1

                                       {  // Hash lookup function
    link pointer;
    int index;
 
    *counter = 0;
    index = h(key);
    pointer = hashtab[index].next;
 
    std::cout << "data[" << index << "]:";
 
    while (pointer != NULL) {
        counter[0]++;
        std::cout << "data[" << pointer->key << "]:";
        if (pointer->key == key)
            return 1;
        else
            pointer = pointer->next;
    }
 
    return 0;
}

Here is the call graph for this function:

main()

int main

(

void

)

main function

           {
    link p;
    int key, index, i, counter;  // Key is the value to be found
    index = 0;
 
    // You can write the input mode here
    while (index < MAX) {  // Construct hash table
        create_list(data[index]);
        index++;
    }
 
    for (i = 0; i < HASHMAX; i++) {  // Output hash table
        std::cout << "hashtab [" << i << "]\n";
 
        p = hashtab[i].next;
 
        while (p != NULL) {
            std::cout << "please int key:";
            if (p->key > 0)
                std::cout << "[" << p->key << "]";
            p = p->next;
        }
        std::cout << std::endl;
    }
 
    while (key != -1) {
        // You can write the input mode here
        // test key = 10
        key = 10;
        if (hash_search(key, &counter))
            std::cout << "search time = " << counter << std::endl;
        else
            std::cout << "no found!\n";
        key = -1;  // Exit test
        /* The test sample is returned as:
         * data[0]:data[5]:data[15]:data[10]:search time = 3 The search is
         * successful. There are 10 in this set of data */
    }
 
    return 0;
}

Here is the call graph for this function:

Variable Documentation

data

int data[MAX] = {1, 10, 15, 5, 8, 7}

test data

{1, 10, 15, 5, 8, 7};  //!< test data