Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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 listlink
 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)

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]keykey to add to list
Warning
dynamic memory allocated to n never gets freed.
Todo:
fix memory leak
55  { // Construct hash table
56  link p, n;
57  int index;
58  n = (link)malloc(sizeof(node));
59  n->key = key;
60  n->next = NULL;
61  index = h(key);
62  p = hashtab[index].next;
63  if (p != NULL) {
64  n->next = p;
65  hashtab[index].next = n;
66  } else {
67  hashtab[index].next = n;
68  }
69 }
Here is the call graph for this function:

◆ h()

int h ( int  key)

Mode of hash detection : Division method

Parameters
[in]keyto hash
Returns
hash value for key
45 { 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
76  { // Hash lookup function
77  link pointer;
78  int index;
79 
80  *counter = 0;
81  index = h(key);
82  pointer = hashtab[index].next;
83 
84  std::cout << "data[" << index << "]:";
85 
86  while (pointer != NULL) {
87  counter[0]++;
88  std::cout << "data[" << pointer->key << "]:";
89  if (pointer->key == key)
90  return 1;
91  else
92  pointer = pointer->next;
93  }
94 
95  return 0;
96 }
Here is the call graph for this function:

◆ main()

int main ( void  )

main function

99  {
100  link p;
101  int key, index, i, counter; // Key is the value to be found
102  index = 0;
103 
104  // You can write the input mode here
105  while (index < MAX) { // Construct hash table
106  create_list(data[index]);
107  index++;
108  }
109 
110  for (i = 0; i < HASHMAX; i++) { // Output hash table
111  std::cout << "hashtab [" << i << "]\n";
112 
113  p = hashtab[i].next;
114 
115  while (p != NULL) {
116  std::cout << "please int key:";
117  if (p->key > 0)
118  std::cout << "[" << p->key << "]";
119  p = p->next;
120  }
121  std::cout << std::endl;
122  }
123 
124  while (key != -1) {
125  // You can write the input mode here
126  // test key = 10
127  key = 10;
128  if (hash_search(key, &counter))
129  std::cout << "search time = " << counter << std::endl;
130  else
131  std::cout << "no found!\n";
132  key = -1; // Exit test
133  /* The test sample is returned as:
134  * data[0]:data[5]:data[15]:data[10]:search time = 3 The search is
135  * successful. There are 10 in this set of data */
136  }
137 
138  return 0;
139 }
Here is the call graph for this function:
hash_search
int hash_search(int key, int *counter)
Definition: hash_search.cpp:76
HASHMAX
#define HASHMAX
Determines the length of the hash table.
Definition: hash_search.cpp:22
node
Definition: avltree.cpp:13
MAX
#define MAX
Determines how much data.
Definition: hash_search.cpp:21
std::cout
h
int h(int key)
Definition: hash_search.cpp:45
link
struct list * link
pointer to nodes
list::key
int key
key value for node
Definition: hash_search.cpp:30
hashtab
node hashtab[HASHMAX]
array of nodes
Definition: hash_search.cpp:35
data
int data[MAX]
test data
Definition: hash_search.cpp:24
std::endl
T endl(T... args)
create_list
void create_list(int key)
Definition: hash_search.cpp:55
std::malloc
T malloc(T... args)
list::next
struct list * next
pointer to next link in the chain
Definition: hash_search.cpp:31
list
Definition: list_array.cpp:8