The caption on figure 5.56 should read Dictionary skeleton for Exercise 5.21
CHAPTER 5
Hashing
5.1 (a) On the assumption that we add collisions to the end of the list (which is the easier way if a hash table is
being built by hand), the separate chaining hash table that results is shown here.
(c)
(d) 1989 cannot be inserted into the table because hash2(1989) = 6, and the alternative locations 5, 1, 7, and 3
5.2 When rehashing, we choose a table size that is roughly twice as large and prime. In our case, the appropriate
new table size is 19, with hash function h(x) = x(mod 19).
(a) Scanning down the separate chaining hash table, the new locations are 4371 in list 1, 1323 in list 12, 6173
(c) The new locations are 9679 in bucket 8, 4371 in bucket 1, 1989 in bucket 13, 1323 in bucket 12, 6173 in
5.3 For simplicity only integers will be hashed and the hash function h(x) = x %D where D is the user
input size of the table. The simulation continues until the quadratic hashing fails.
Typical results for table size 1001
Linear Collisions : 5983
int insertLinear(int x, vector<int> & linear);
int insertQuad(int x, vector<int> & quad);
int insertDuble(int x, int dubHash, vector<int> & duble);
int main()
srand(time(NULL));
cout<<“enter the size of the table “;
cin>>tableSize;
quadCollides += quadInc;
linCollides+=insertLinear(x,linear);
dubCollides+=insertDuble(x,doubleHash, duble);
}
count++;
}
int insertLinear(int x, vector<int> & linear)
{
int collides=0;
while(collides < linear.size() && linear[x] >=0)
{
}
int insertQuad(int x, vector<int> & quad)
{
int collides=0;
int probeDist= 1;
int probeDiff =1;
bool fail = false;
while(collides < quad.size() && quad[x] >=0 && !fail)
{
}
if (fail || collides>=quad.size())
return –1;
else
{
quad[x] = x;
return collides;
}
}
int insertDuble(int x, int dubHash, vector<int> & duble)
return collides;
}
5.4 We must be careful not to rehash too often. Let p be the threshold (fraction of table size) at which we rehash
to a smaller table. Then if the new table has size N, it contains 2pN elements. This table will require
5.5 This problem is in error, as the implementation in the text already uses a vector of lists.
5.8 Cubic probing encounters slightly fewer collisions than quadratic probing, as seen in the following
simulation.
// Let’s simulate linear, quadratic, and cubic probing.
// Is cubic probing any better than quadratic?
// We are going to generate random indices to occupy in the hash tables.
srand(0);
for (int i = 0; i < MAX; ++i)
{
}
srand(0);
for (int i = 0; i < MAX; ++i)
{
int hashCode = rand()% SIZE;
int offset = 0;
while (quadratic[hashCode] == 1)
{
++quadraticCollisions;
++offset;
hashCode += offset * offset;
if (hashCode >= SIZE)
hashCode %= SIZE;
5.10 Separate chaining hashing requires the use of links, which costs some memory, and the standard
method of implementing calls on memory allocation routines, which typically are expensive. Linear
5.11 In the case of a collision this method uses a pseudorandom number to make jumps away from the
home bucket. However the length of the jump the same for each home bucket. This would avoid
5.13 Sorting the MN records and eliminating duplicates would require O(MN log MN) time using a
standard sorting algorithm. If terms are merged by using a hash function, then the merging time is
constant per term for a total of O(MN). If the output polynomial is small and has only O(M + N)
terms, then it is easy to sort it in O((M + N) log(M + N)) time, which is less than O(MN). Thus
5.14 To each hash table slot, we can add an extra data member that we’ll call whereOnStack, and we can
keep an extra stack. When an insertion is first performed into a slot, we push the address (or
number)
5.16 The compiler could hash each string in the switch statement to a table which holds the starting memory
5.20
template <typename HashedObj, typename Object>
class Pair
{
{
public:
Dictionary( ) {}
void insert( const HashedObj & key, const Object & definition )
{items.insert(Pair<HashedObj,Object>(key, definition));}
};
5.22 Consider the function on the random variable X, Ia (X) to be 1 if X> a, and 0 otherwise. Ia() is called an
indicator random variable . If a > 0, then aIa(X) < X since if X < a, the left size is 0 and if X > a we have
a < X. Taking the expectation of both sides we have :
Thus aPr(X> a)< E(X) and dividing by a (since a was assumed greater than 0) we have
5.23 The probability of a rehash (failed insertion) at the point when the table is half full is low, on the order of
1% or less. The probability falls with increased table size. Below are the results of two trials with random
insertion data. The probabilities may be even lower if we modify the hopscotch table to continue linear
probing past the end of the table to wrap around to the beginning.
Table size
MAX_DIST
Load factor
Number of trials
Probability of rehash
5.24
template <typename AnyType>
class HopScotchHash
{
private :
{
int i = open – MAX_DIST;
int pos = (1<<MAX_DIST);
int D = table.size();
int tempHome;
AnyType temp;
if (i<MAX_DIST)
{
table[(home + i)% D].element = x;
table[(home + i)% D].isActive = true;
table[home].hop = table[home].hop | (pos>>i);
return true;
(1<<(home+open – tempHome));
return true;
}// end if
return false;
}//end else
}// end else
}// end shiftdown
bool insert1(AnyType & x)
991
while (diff < table.size() && table[(home + (diff))% D].isActive)
diff++;
if (diff >= table.size())
return false;
else if (diff<=MAX_DIST)
}
}// end of insert
public :
HopScotchHash(int size = 11)
{table.resize(size);}
bool insert(AnyType & x)
};
The amount of time to insert 10,000 elements for various sample implementations is given below. The
advantage of hopscotch hashing is not in the computational efficiency of the average case.
5.25
// To mimic the “classic” cuckoo hash table, as shown in the examples
// given in Figures 5.26-5.33 in the text,
Implementation
Time (ms)
Hopscotch
150
#include<iostream>
using namespace std;
const int LOGICAL_SIZE = 13;
void makeEmpty()
{
for (int i = 0; i < contents.size(); ++i)
for (int j = 0; j < contents[0].size(); ++j)
contents[i][j] = “”;
}
}
// For Cuckoo hashing, we need to be ready to compute the value
// of an n-th hash code. Multiply the string’s native hash code
}
void add(string value)
{
cout<<“Entering add() with value = “<< value<<endl;
{
contents[desiredRow][desiredCol] = value;
break;
}
}
}
}
5.26 To support d hash functions, the only modification necessary in the implementation given in 5.25 is to
5.27
5.28
/*
Extensible hashing
Assumes the number of bits is INT_BITS
const int BLOCKSIZE = 4;
const int INT_BITS = 32;
struct Node
{
}
int size() {return pointers.size();}
void resize(int size)
{
pointers.resize(size);
for (auto & p : pointers)
p = nullptr;
numSigBits = floor(log(size)/log(2)+.5);
}
};
}
void doubleDirect()
{
Directory temp(2*directory.size());
for (int i = 0; i < directory.size(); i++)
}
}
if (p->data.size() < BLOCKSIZE )
p->data.push_back(d);
else
{
for (int i = 0; i < directory.pointers.size(); i++)
if (i != key && directory.pointers[key] == directory.pointers[i])
}
void print()
{
for (int i = 0; i < directory.pointers.size(); i++)
int main()
{