quadratic_probing Namespace Reference

An implementation of hash table using quadratic probing 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)
int	quadraticProbe (int key, bool searching)
Entry	find (int key)
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 quadratic probing algorithm.

Typedef Documentation

Entry

using quadratic_probing::Entry = struct Entry

Definition at line 22 of file quadratic_probing_hash_table.cpp.

Function Documentation

add()

void quadratic_probing::add

(

int

key

)

Checks for load factor here

Parameters

key	key value to hash and add to table

Definition at line 182 of file quadratic_probing_hash_table.cpp.

                  {
    int index = quadraticProbe(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 quadratic_probing::addInfo

(

int

key

)

Information about the adding process

Parameters

key	key value to hash and add to table

Definition at line 207 of file quadratic_probing_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 quadratic_probing::display

(

)

Displays the table

Returns

None

Definition at line 142 of file quadratic_probing_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;
}

find()

Entry quadratic_probing::find

(

int

key

)

Get the entry instance corresponding to a key

Parameters

key	key value to search/probe

Returns

if present, the entry instance

if not present, a new instance

Definition at line 131 of file quadratic_probing_hash_table.cpp.

                    {
    int index = quadraticProbe(key, true);
    if (index == notPresent) {
        return Entry();
    }
    return table[index];
}

hashFxn()

size_t quadratic_probing::hashFxn

(

int

key

)

Hash a key

Parameters

key	key value to hash

Returns

hash of the key

Definition at line 46 of file quadratic_probing_hash_table.cpp.

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

putProber()

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

Finds empty spot

Parameters

entry	Instance of table entry
key	key value to search/probe

Returns

true if key is present

false if key is absent

Definition at line 106 of file quadratic_probing_hash_table.cpp.

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

quadraticProbe()

int quadratic_probing::quadraticProbe	(	int	key,
		bool	searching )

Performs quadratic probing to resolve collisions

Parameters

key	key value to search/probe
searching	true if only searching, false1 if assigning @returns value of notPresent`.

Definition at line 56 of file quadratic_probing_hash_table.cpp.

                                            {
    int hash = static_cast<int>(hashFxn(key));
    int i = 0;
    Entry entry;
    do {
        size_t index =
            (hash + static_cast<size_t>(std::round(std::pow(i, 2)))) %
            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 = "
                          << (hash + static_cast<size_t>(
                                         std::round(std::pow(i + 1, 2)))) %
                                 totalSize
                          << std::endl;
            }
            i++;
        }
        if (i == totalSize * 100) {
            std::cout << "Quadratic probe failed (infinite loop)" << std::endl;
            return notPresent;
        }
    } while (entry.key != notPresent);
    return notPresent;
}

rehash()

void quadratic_probing::rehash

(

)

Rehashes the table into a bigger table

Returns

none

Definition at line 160 of file quadratic_probing_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
    totalSize *= 2;
    table = std::vector<Entry>(totalSize);
    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;
    rehashing = false;
    std::cout << "Table was rehashed, new size is: " << totalSize << std::endl;
}

removalInfo()

void quadratic_probing::removalInfo

(

int

key

)

Information about removal process

Parameters

key	key value to hash and remove from table

Definition at line 222 of file quadratic_probing_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 quadratic_probing::remove

(

int

key

)

Removes key. Leaves tombstone upon removal.

Parameters

key	key value to hash and remove from table

Definition at line 194 of file quadratic_probing_hash_table.cpp.

                     {
    int index = quadraticProbe(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 quadratic_probing::searchingProber	(	const Entry &	entry,
		int	key )

Looks for a matching key

Parameters

entry	Instance of table entry
key	key value to search/probe

Returns

true if key matches the entry

false if key does not match the entry

Definition at line 119 of file quadratic_probing_hash_table.cpp.

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

Variable Documentation

notPresent

int quadratic_probing::notPresent

Definition at line 28 of file quadratic_probing_hash_table.cpp.

rehashing

bool quadratic_probing::rehashing

Definition at line 33 of file quadratic_probing_hash_table.cpp.

size

int quadratic_probing::size

Definition at line 32 of file quadratic_probing_hash_table.cpp.

table

std::vector<Entry> quadratic_probing::table

Definition at line 29 of file quadratic_probing_hash_table.cpp.

tomb

int quadratic_probing::tomb = -1

Definition at line 31 of file quadratic_probing_hash_table.cpp.

totalSize

int quadratic_probing::totalSize

Definition at line 30 of file quadratic_probing_hash_table.cpp.