Requirements:

In this sub-project, you will implement one class:

1. Cuckoo hash table: Cuckoo_hash_table.

A hash table stores positive integers (≥ 0) in the bin corresponding to the hash or searches forward if that bin is filled.

The load factor of a hash table may increase array may be changed depending on the number of positive integers currently stored in the array, according to the following two rules:

• If a positive integer is being inserted into a hash table where the load factor after the insertion is 0.75, the size of the array is doubled.
• If, after removing a positive integer from a hash table where the load factor after the removal is 0.25, then the size of the array is halved. The size of the array may not be reduced below the initially specified size.

Runtime:

The run time of each member function is specified in parentheses at the end of the description.

Class Specifications:

Dynamic_linear_hash_table

Description

Create a hash table which uses linear probing where the array size may double or halve, depending on the load factor.

Member Variables

The class at least six members:

• A pointer to an int, int *array, to be used as an array of bins,
• An initial capacity int initial_capacity,
• A current capacity int current_capacity, and
• A counter int count.

Hash Function

The hash value of any positive integer will be:

• multply the number by 53267,
• if this result is negative, add 2³¹,
• ignore the five least-significant bits and use an appropriate modulo of the balance to get the number.

For example, to get either a 4-bit or a 7-bit hash value of 1, 53, 93, and 100, we have 0 and 0; 15 and 31; 7 and 55; and 11 and 59. For example, if the hash table is empty and of capacity 2⁴, then 100 would be stored in bin 11, and if the hash table is empty and of capacity 2⁷, then 100 would be stored in bin 59.

Member Functions

Constructors

Dynamic_linear_hash_table( int n = 3 )

The constructor takes as an argument the initial size of the array and allocates memory for that array. The default number of entries is 2ⁿ. You may assume that n ≥ 2 (that is, there will be at least 4 bins). Other class members are assigned as appropriate. (O(2ⁿ))

Destructor

~Dynamic_linear_hash_table()

The destructor deletes the memory allocated for the array.

Accessors

This class has six accessors:

int size() const

Returns the number of positive integers currently stored in the hash table. (O(1))

bool empty() const

Returns true if the hash table is empty, false otherwise. (O(1))

int capacity() const

Returns the current size of the array. (O(1))

bool member( int ) const

Returns true if the argument is in the hash table, and false otherwise. (O(1) on average)

double load_factor() const

Returns the load factor as a double-precision floating-point number. (O(1))

int bin( int ) const

Returns whatever is stored in the bin number corresponding to the argument (this will only be called on bins which I expect to be filled). (O(1))

Mutators

This class has three mutators:

void insert( int )

Insert the new integer into the hash table. Linear probing should be used if any of the bins are full. If the addition causes the load factor to reach 0.75, then a new hash table twice the size should be allocated and reinsert all the positive integers. The argument will always be positive. (O(1) on average)

bool remove( int )

Remove the integer from the hash table. If, after the deletion, the load factor drops to 0.25 or less, then a new hash table half the size should be allocated and reinsert all the positive integers (except, of course, the removed one). The size of array must never go below the initial size. Be sure to make sure that all entries can still be found. If the integer is not found, return false. (O(1) on average)

Note: the algorithm for remove is given in lecture slides for "Linear probing", 15-25.

void clear()

Removes all the positive integers in the hash table. If the array is not the initial size, it, too, should be resized to the initial capacity. (O(2ⁿ) where n is the initial argument to the constructor)

Friends

The class has no friends.

Hints

Review the appropriate bitwise functions (<<, >>, &, etc.). Second, use a simple hash function initially, such as simply taking the number modulo the array size. Third, get the hash table working without doubling or halving the size of the array. Test it thoroughly for different initial sizes. Use the examples above to make sure you put numbers in the correct bin. Use one of the properties of what is being stated in insert to mark empty bins. Then, once it is working, when you have to halve or double the size of the table, store the current table elsewhere, create a new table of half or double this size, make it as if it were empty, and then call insert on all entries in the stored array.