quadratic_probing Namespace Reference

An implementation of hash table using quadratic probing algorithm. More...

Classes
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.

Function Documentation

add()

void quadratic_probing::add

(

int

key

)

Checks for load factor here

Parameters

key	key value to hash and add to table

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

Here is the call graph for this function:

addInfo()

void quadratic_probing::addInfo

(

int

key

)

Information about the adding process

Parameters

key	key value to hash and add to table

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

Here is the call graph for this function:

display()

void quadratic_probing::display

(

)

Displays the table

Returns

None

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

Here is the call graph for this function:

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

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

Here is the call graph for this function:

hashFxn()

size_t quadratic_probing::hashFxn

(

int

key

)

Hash a key

Parameters

key	key value to hash

Returns

hash of the key

                        {
    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

                                            {
    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 ofnotPresent`.

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

Here is the call graph for this function:

rehash()

void quadratic_probing::rehash

(

)

Rehashes the table into a bigger table

Returns

none

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

Here is the call graph for this function:

removalInfo()

void quadratic_probing::removalInfo

(

int

key

)

Information about removal process

Parameters

key	key value to hash and remove from table

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

Here is the call graph for this function:

remove()

void quadratic_probing::remove

(

int

key

)

Removes key. Leaves tombstone upon removal.

Parameters

key	key value to hash and remove from table

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

Here is the call graph for this function:

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

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