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)
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 )

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`. */ int quadraticProbe(int key, bool searching) { 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; }

/** 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;
}

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.