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.

Definition at line 16 of file chaining.cpp.

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.

Definition at line 21 of file chaining.cpp.

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

Constructor & Destructor Documentation

hash_chain()

hash_chain::hash_chain ( int mod )

inlineexplicit

Construct a new chain object.

Parameters

mod	modulus of the chain

Definition at line 35 of file chaining.cpp.

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

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

Definition at line 45 of file chaining.cpp.

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

display()

void hash_chain::display ( )

inline

Display the chain.

Definition at line 63 of file chaining.cpp.

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

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

Definition at line 101 of file chaining.cpp.

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

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.

Definition at line 91 of file chaining.cpp.

{ return x % _mod; }

Member Data Documentation

_mod

int hash_chain::_mod

private

modulus of the class

Definition at line 27 of file chaining.cpp.

head

std::vector<std::shared_ptr<Node> > hash_chain::head

private

array of nodes

Definition at line 26 of file chaining.cpp.

---

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

• hashing/chaining.cpp