double_hashing Namespace Reference

An implementation of hash table using double hashing algorithm. More...

Classes
struct	Entry

Typedefs
using	Entry = struct Entry

Functions
bool	putProber (const Entry &entry, int key)
bool	searchingProber (const Entry &entry, int key)
void	add (int key)
size_t	hashFxn (int key)
	Hash a key. Uses the STL library's std::hash() function.
size_t	otherHashFxn (int key)
	Used for second hash function.
int	doubleHash (int key, bool searching)
	Performs double hashing to resolve collisions.
void	display ()
void	rehash ()
void	remove (int key)
void	addInfo (int key)
void	removalInfo (int key)

Variables
int	notPresent
std::vector< Entry >	table
int	totalSize
int	tomb = -1
int	size
bool	rehashing

Detailed Description

An implementation of hash table using double hashing algorithm.

Typedef Documentation

Entry

using double_hashing::Entry = struct Entry

Definition at line 22 of file double_hash_hash_table.cpp.

Function Documentation

add()

void double_hashing::add

(

int

key

)

Checks for load factor here

Parameters

key	key value to add to the table

Definition at line 185 of file double_hash_hash_table.cpp.

                  {
    // auto* entry = new Entry();
    // entry->key = key;
    int index = doubleHash(key, false);
    table[index].key = key;
    // Load factor greater than 0.5 causes resizing
    if (++size / static_cast<double>(totalSize) >= 0.5) {
        rehash();
    }
}

addInfo()

void double_hashing::addInfo

(

int

key

)

Information about the adding process

Parameters

key	key value to add to table

Definition at line 212 of file double_hash_hash_table.cpp.

                      {
    std::cout << "Initial table: ";
    display();
    std::cout << std::endl;
    std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
              << totalSize << " == " << hashFxn(key) % totalSize;
    std::cout << std::endl;
    add(key);
    std::cout << "New table: ";
    display();
}

display()

void double_hashing::display

(

)

Displays the table

Returns

None

Definition at line 143 of file double_hash_hash_table.cpp.

               {
    for (int i = 0; i < totalSize; i++) {
        if (table[i].key == notPresent) {
            std::cout << " Empty ";
        } else if (table[i].key == tomb) {
            std::cout << " Tomb ";
        } else {
            std::cout << " ";
            std::cout << table[i].key;
            std::cout << " ";
        }
    }
    std::cout << std::endl;
}

doubleHash()

int double_hashing::doubleHash	(	int	key,
		bool	searching )

Performs double hashing to resolve collisions.

Parameters

key	key value to apply double-hash on
searching	true to check for conflicts

Returns

Index of key when found

new hash if no conflicts present

Definition at line 71 of file double_hash_hash_table.cpp.

                                        {
    int hash = static_cast<int>(hashFxn(key));
    int i = 0;
    Entry entry;
    do {
        int index =
            static_cast<int>(hash + (i * otherHashFxn(key))) % totalSize;
        entry = table[index];
        if (searching) {
            if (entry.key == notPresent) {
                return notPresent;
            }
            if (searchingProber(entry, key)) {
                std::cout << "Found key!" << std::endl;
                return index;
            }
            std::cout << "Found tombstone or equal hash, checking next"
                      << std::endl;
            i++;
        } else {
            if (putProber(entry, key)) {
                if (!rehashing) {
                    std::cout << "Spot found!" << std::endl;
                }
                return index;
            }
            if (!rehashing) {
                std::cout << "Spot taken, looking at next (next index:"
                          << " "
                          << static_cast<int>(hash + (i * otherHashFxn(key))) %
                                 totalSize
                          << ")" << std::endl;
            }
            i++;
        }
        if (i == totalSize * 100) {
            std::cout << "DoubleHash probe failed" << std::endl;
            return notPresent;
        }
    } while (entry.key != notPresent);
    return notPresent;
}

hashFxn()

size_t double_hashing::hashFxn

(

int

key

)

Hash a key. Uses the STL library's std::hash() function.

Parameters

key	value to hash

Returns

hash value of the key

Definition at line 47 of file double_hash_hash_table.cpp.

                        {
    std::hash<int> hash;
    return hash(key);
}

otherHashFxn()

size_t double_hashing::otherHashFxn

(

int

key

)

Used for second hash function.

Parameters

key	key value to hash

Returns

hash value of the key

Definition at line 58 of file double_hash_hash_table.cpp.

                             {
    std::hash<int> hash;
    return 1 + (7 - (hash(key) % 7));
}

putProber()

bool double_hashing::putProber	(	const Entry &	entry,
		int	key )

Finds empty spot in a vector

Parameters

entry	vector to search in
key	key to search for

Returns

true if key is not present or is a toumb

false is already occupied

Definition at line 120 of file double_hash_hash_table.cpp.

                                            {
    if (entry.key == notPresent || entry.key == tomb) {
        return true;
    }
    return false;
}

rehash()

void double_hashing::rehash

(

)

Rehashes the table into a bigger table

Returns

None

Definition at line 161 of file double_hash_hash_table.cpp.

              {
    // Necessary so wall of add info isn't printed all at once
    rehashing = true;
    int oldSize = totalSize;
    std::vector<Entry> oldTable(table);
    // Really this should use the next prime number greater than totalSize * 2
    table = std::vector<Entry>(totalSize * 2);
    totalSize *= 2;
    for (int i = 0; i < oldSize; i++) {
        if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
            size--;  // Size stays the same (add increments size)
            add(oldTable[i].key);
        }
    }
    // delete[] oldTable;
    // oldTable.reset();
 
    rehashing = false;
    std::cout << "Table was rehashed, new size is: " << totalSize << std::endl;
}

removalInfo()

void double_hashing::removalInfo

(

int

key

)

Information about removal process

Parameters

key	key value to remove from table

Definition at line 227 of file double_hash_hash_table.cpp.

                          {
    std::cout << "Initial table: ";
    display();
    std::cout << std::endl;
    std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
              << totalSize << " == " << hashFxn(key) % totalSize;
    std::cout << std::endl;
    remove(key);
    std::cout << "New table: ";
    display();
}

remove()

void double_hashing::remove

(

int

key

)

Removes key. Leaves tombstone upon removal.

Parameters

key	key value to remove

Definition at line 199 of file double_hash_hash_table.cpp.

                     {
    int index = doubleHash(key, true);
    if (index == notPresent) {
        std::cout << "key not found" << std::endl;
    }
    table[index].key = tomb;
    std::cout << "Removal successful, leaving tombstone" << std::endl;
    size--;
}

searchingProber()

bool double_hashing::searchingProber	(	const Entry &	entry,
		int	key )

Looks for a matching key

Parameters

entry	vector to search in
key	key value to search

Returns

true if found

false if not found

Definition at line 133 of file double_hash_hash_table.cpp.

                                                  {
    if (entry.key == key) {
        return true;
    }
    return false;
}

Variable Documentation

notPresent

int double_hashing::notPresent

Definition at line 28 of file double_hash_hash_table.cpp.

rehashing

bool double_hashing::rehashing

Definition at line 33 of file double_hash_hash_table.cpp.

size

int double_hashing::size

Definition at line 32 of file double_hash_hash_table.cpp.

table

std::vector<Entry> double_hashing::table

Definition at line 29 of file double_hash_hash_table.cpp.

tomb

int double_hashing::tomb = -1

Definition at line 31 of file double_hash_hash_table.cpp.

totalSize

int double_hashing::totalSize

Definition at line 30 of file double_hash_hash_table.cpp.