hash_chain Class Reference

Chain class with a given modulus. More...

Collaboration diagram for hash_chain:

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

Private Types
using	Node
	Define a linked node.

Private Attributes
std::vector< std::shared_ptr< Node > >	head
	array of nodes
int	_mod
	modulus of the class

Detailed Description

Chain class with a given modulus.

Member Typedef Documentation

Node

using hash_chain::Node

private

Initial value:

 struct Node {
        int data{};                         
        std::shared_ptr<struct Node> next;  
    }

Define a linked node.

                             {
        int data{};                         ///< data stored in the node
        std::shared_ptr<struct Node> next;  ///< pointer to the next node
    };

Constructor & Destructor Documentation

hash_chain()

hash_chain::hash_chain ( int mod )

inlineexplicit

Construct a new chain object.

Parameters

mod	modulus of the chain

                                 : _mod(mod) {
        while (mod--) head.push_back(nullptr);
    }

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

x	value at the new node
h	height of the node

                           {
        std::shared_ptr<Node> curr;
        std::shared_ptr<Node> temp(new Node);
        temp->data = x;
        temp->next = nullptr;
        if (!head[h]) {
            head[h] = temp;
            curr = head[h];
        } else {
            curr = head[h];
            while (curr->next) curr = curr->next;
            curr->next = temp;
        }
    }

Here is the call graph for this function:

display()

void hash_chain::display ( )

inline

Display the chain.

                   {
        std::shared_ptr<Node> temp = nullptr;
        int i = 0;
        for (i = 0; i < _mod; i++) {
            if (!head[i]) {
                std::cout << "Key " << i << " is empty" << std::endl;
            } else {
                std::cout << "Key " << i << " has values = " << std::endl;
                temp = head[i];
                while (temp->next) {
                    std::cout << temp->data << " " << std::endl;
                    temp = temp->next;
                }
                std::cout << temp->data;
                std::cout << std::endl;
            }
        }
    }

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

x	value to search for
h	corresponding hash key

Returns

true if element found

false if element not found

                                  {
        std::shared_ptr<Node> temp = head[h];
        if (!head[h]) {
            // index does not exist!
            std::cout << "Element not found" << std::endl;
            return false;
        }
 
        // scan for data value
        while (temp->data != x && temp->next) temp = temp->next;
 
        if (temp->next) {
            std::cout << "Element found" << std::endl;
            return true;
        }
 
        // implicit else condition
        // i.e., temp->next == nullptr
        if (temp->data == x) {
            std::cout << "Element found" << std::endl;
            return true;
        }
 
        // further implicit else condition
        std::cout << "Element not found" << std::endl;
        return false;
    }

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

x	value 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.

{ return x % _mod; }

---

The documentation for this class was generated from the following file:

• hashing/chaining.cpp