hash_search.cpp File Reference

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

#include <cstdlib>
#include <iostream>

Include dependency graph for hash_search.cpp:

Go to the source code of this file.

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

Definition in file hash_search.cpp.

Macro Definition Documentation

HASHMAX

#define HASHMAX   5

Determines the length of the hash table.

Definition at line 22 of file hash_search.cpp.

MAX

#define MAX   6

Determines how much data.

Definition at line 21 of file hash_search.cpp.

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

Definition at line 55 of file hash_search.cpp.

                          {  // 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;
    }
}

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.

Definition at line 45 of file hash_search.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

Definition at line 76 of file hash_search.cpp.

                                       {  // 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;
}

main()

int main

(

void

)

main function

Definition at line 99 of file hash_search.cpp.

           {
    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;
}

Variable Documentation

data

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

test data

Definition at line 24 of file hash_search.cpp.

{1, 10, 15, 5, 8, 7};  

hashtab

node hashtab[HASHMAX]

array of nodes

Definition at line 35 of file hash_search.cpp.