Skip to content

Dynamic hash table implementation that uses chaining method. Supporting insertion, delete and equality search.

License

Notifications You must be signed in to change notification settings

ByJuanDiego/hash-table

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

32 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Hash table C++ implementation

Requirements

Before running the project, install the following libraries:

sudo yum install openssl
sudo yum install openssl-devel
sudo yum install boost-devel
sudo yum install boost

To link the libraries with the project, add the following lines to CMakeList.txt

find_package(OpenSSL REQUIRED)
find_package(Boost REQUIRED)

target_link_libraries(
        ${PROJECT_NAME}
        OpenSSL::SSL
        Boost::boost
)

Run the project

git clone https://github.com/ByJuanDiego/hash-table.git
cd hash-table
chmod +x run.zsh
./run.zsh

Member functions

$n :=$ total number of records in the hash table

$e_{avg} :=$ average number of entries in a bucket

$v_{avg} :=$ average number of values on an entry

Member Function Big $\mathcal{O}$ performance Big $\Theta$ performance Notes
bucket_count() $\mathcal{O}(1)$ Same as $\mathcal{O}$ -
bucket_size(int i) $\mathcal{O}(1)$ Same as $\mathcal{O}$ -
key_count() $\mathcal{O}(1)$ Same as $\mathcal{O}$ -
size() $\mathcal{O}(1)$ Same as $\mathcal{O}$ -
empty() $\mathcal{O}(1)$ Same as $\mathcal{O}$ -
clear() $\mathcal{O}(n)$ Same as $\mathcal{O}$ if V is a pointer, records will not be freed
find(K key) $\mathcal{O}(n)$ $\Theta(e_{avg})$ keeps the array length
insert(V value) $\mathcal{O}(n)$ $\Theta(e_{avg})$ -
remove(K key) $\mathcal{O}(n)$ $\Theta(e_{avg} + v_{avg})$ -
search(K key) $\mathcal{O}(n)$ $\Theta(e_{avg} + v_{avg})$ -
print(std::ostream &os, Print<V> print_value, Print<K> print_key) $\mathcal{O}(n)$ Same as $\mathcal{O}$ print_value and print_key has default functions for fundamental types

Usage cases

Initialization

using std::string;
using sha = sha2::sha256<string>;
using index_t = std::function<string(transaction *)>;
using equal_t = std::function<bool(string, string)>;

sha hash;
index_t index = [&](const transaction *tx) -> string {
    return tx->emisor;
};
equal_t equal = [&](const string &a, const string &b) -> bool {
    return (a == b);
};
hash_table<string, transaction *, sha, index_t, equal_t> hashTable(index, hash, equal);

Instantiates a hashTable that contains transaction * indexed by emisor

  • equal is an optional parameter. By default, it receives an instance of std::equal_to, which works properly for built-in types. Using a non-built-in type as key makes necessary equal parameter or an std::equal_to specialization
  • hash is an instance of sha2::sha256, which is well-defined for std::to_string convertable key-types and specialized for std::string usage. To use other key-types a sha2::sha256 specialization is required
  • usage of other hash functions such as std::hash is allowed by passing the desire hash function as template type parameter

Querying

std::string key = "juan-diego";
for (const transaction *t: hashTable.search(key)) {
    std::cout << t->to_string() << std::endl;
}

This query returns all the transactions made by juan-diego

Freeing memory

If the value-type is a pointer, the pointed values will not be freed when hash_table::~hash_table is called. This is manual process.

for (transaction *tx: destructor) {
    delete tx;
}

To be implemented

  • iterator class for the hash table
  • shrink_to_fit private member function to be used to resize the hash table when deleting a certain number of keys

About

Dynamic hash table implementation that uses chaining method. Supporting insertion, delete and equality search.

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published