Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
hash_chain Class Reference

Chain class with a given modulus. More...

Collaboration diagram for hash_chain:
[legend]

Public Member Functions

 hash_chain (int mod)
 Construct a new chain object. More...
 
void add (int x, int h)
 create and add a new node with a give value and at a given height More...
 
void display ()
 Display the chain.
 
virtual int hash (int x) const
 Compute the hash of a value for current chain. More...
 
bool find (int x, int h) const
 Find if a value and corresponding hash exist. More...
 

Private Types

using Node = struct Node { int data{}
 data stored in the node
 

Private Attributes

std::shared_ptr< struct Nodenext
 pointer to the next node
 
std::vector< std::shared_ptr< Node > > head
 array of nodes
 
int _mod
 modulus of the class
 

Detailed Description

Chain class with a given modulus.

Constructor & Destructor Documentation

◆ hash_chain()

hash_chain::hash_chain ( int  mod)
inlineexplicit

Construct a new chain object.

Parameters
modmodulus of the chain
35  : _mod(mod) {
36  while (mod--) head.push_back(nullptr);
37  }
Here is the call graph for this function:

Member Function Documentation

◆ add()

void hash_chain::add ( int  x,
int  h 
)
inline

create and add a new node with a give value and at a given height

Parameters
xvalue at the new node
hheight of the node
45  {
47  std::shared_ptr<Node> temp(new Node);
48  temp->data = x;
49  temp->next = nullptr;
50  if (!head[h]) {
51  head[h] = temp;
52  curr = head[h];
53  } else {
54  curr = head[h];
55  while (curr->next) curr = curr->next;
56  curr->next = temp;
57  }
58  }
Here is the call graph for this function:

◆ find()

bool hash_chain::find ( int  x,
int  h 
) const
inline

Find if a value and corresponding hash exist.

Parameters
xvalue to search for
hcorresponding hash key
Returns
true if element found
false if element not found
101  {
102  std::shared_ptr<Node> temp = head[h];
103  if (!head[h]) {
104  // index does not exist!
105  std::cout << "Element not found";
106  return false;
107  }
108 
109  // scan for data value
110  while (temp->data != x && temp->next) temp = temp->next;
111 
112  if (temp->next) {
113  std::cout << "Element found";
114  return true;
115  }
116 
117  // implicit else condition
118  // i.e., temp->next == nullptr
119  if (temp->data == x) {
120  std::cout << "Element found";
121  return true;
122  }
123 
124  // further implicit else condition
125  std::cout << "Element not found";
126  return false;
127  }
Here is the call graph for this function:

◆ hash()

virtual int hash_chain::hash ( int  x) const
inlinevirtual

Compute the hash of a value for current chain.

Parameters
xvalue to compute modulus of
Returns
modulus of x
Note
declared as a virtual so that custom implementations of the class can modify the hash function.
91 { return x % _mod; }

The documentation for this class was generated from the following file:
std::shared_ptr< Node >
hash_chain::head
std::vector< std::shared_ptr< Node > > head
array of nodes
Definition: chaining.cpp:24
Node
Definition: linkedlist_implentation_usingarray.cpp:14
std::vector::push_back
T push_back(T... args)
hash_chain::_mod
int _mod
modulus of the class
Definition: chaining.cpp:27
std::cout
h
int h(int key)
Definition: hash_search.cpp:45