Data Structures with C++ Using STL”, William Ford and William Topp, 2002, Prenti
ID: 3758812 • Letter: D
Question
Data Structures with C++ Using STL”, William Ford and William Topp, 2002, Prentice Hall, 0-13-085850-1
CH12
Question 21. page 720
Hash tables are suited to applications where the primary operations is retrieval:Insert a data value, and then "look it up" many
times. The linear probe hashing method is poorly suited tto an application that requires that data element be deleted from the hash table.
Consider the following has table of 101 entries with hash function hf(key)=key
a. Delete 304 by placing -1 (empty) in table location 1. What happens when we search for 707? Explain in general why just marking a
slot as empty is not a correct solution to the problem of deletions.
b. A solution to the problem involves placing a special value, deletedData, in the location of the deletion. when searching for a key, we skip table
locations marked with deleteData. Use the key value -2 in the table to indicate that a deletion occurred at the particular table location.
Show that this approach to deletin g 304 allows a correct search for 707.
The insertion and retrieval operations in the linear probe algorithm must be modified to accommodate deletions.
c. Describe an algorithm to delete a table element.
d. Describe an algorithm to locate an element in the table.
e. Describe an algorithm to insert an element in the table.
Explanation / Answer
b.
Inserting into an open-addressed hash table
Deleting from an open-addressed hash table
Retrieving from an open-addressed hash table
Quadratic probing implementation
c. Algorithm to delete a table element:
class HashEntry {
private:
int key;
int value;
public:
HashEntry(int key, int value) {
this->key = key;
this->value = value;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
void setValue(int value) {
this->value = value;
}
};
class DeletedEntry: public HashEntry {
private:
static DeletedEntry *entry;
DeletedEntry() :
HashEntry(-1, -1) {
}
public:
static DeletedEntry *getUniqueDeletedEntry() {
if (entry == NULL)
entry = new DeletedEntry();
return entry;
}
};
DeletedEntry *DeletedEntry::entry = NULL;
const int TABLE_SIZE = 128;
class HashMap {
private:
HashEntry **table;
public:
HashMap() {
table = new HashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
int get(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] == NULL || hash == initialHash)
return -1;
else
return table[hash]->getValue();
}
void put(int key, int value) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry::getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if ((table[hash] == NULL || hash == initialHash) && indexOfDeletedEntry
!= -1)
table[indexOfDeletedEntry] = new HashEntry(key, value);
else if (initialHash != hash)
if (table[hash] != DeletedEntry::getUniqueDeletedEntry()
&& table[hash] != NULL && table[hash]->getKey() == key)
table[hash]->setValue(value);
else
table[hash] = new HashEntry(key, value);
}
void remove(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (hash != initialHash && table[hash] != NULL) {
delete table[hash];
table[hash] = DeletedEntry::getUniqueDeletedEntry();
}
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL && table[i]
!= DeletedEntry::getUniqueDeletedEntry())
delete table[i];
delete[] table;
}
};
d. Algorithm to locate an element in the table:
Algorithm is quite simple. It can be done either recursively or iteratively:
Now we should define, when iterations should stop. First case is when searched element is found. Second one is when subarray has no elements. In this case, we can conclude, that searched value doesn't present in the array.
C++
/*
* searches for a value in sorted array
* arr is an array to search in
* value is searched value
* left is an index of left boundary
* right is an index of right boundary
* returns position of searched value, if it presents in the array
* or -1, if it is absent
*/
int binarySearch(int arr[], int value, int left, int right) {
while (left <= right) {
int middle = (left + right) / 2;
if (arr[middle] == value)
return middle;
else if (arr[middle] > value)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
e. Algorithm to insert an element in the table:
To make space for the new value means moving the rest of the array along. For example, consider that inserting 4 into the sequence 1 3 9 11 15; linear_pos() gives an index of 2 (because 9 is greater than 4). Everything above that position must be shifted up to make room; the top line shows the array subscripts:
0 1 2 3 4 5 subscripts
1 3| 9 11 15 before shifting up by one
1 3 xxx 9 11 15 after shifting up by one
We have to put 4 before index 2 (that is, the third position). So everything from the third position up (9 11 15) has got to move up one. That is, the shift involves A[5] = A[4], A[4] = A[3], and A[3] = A[2]. We can then set A[2] = 4. In general:
Once insert_at() is defined, then it is straightforward to put a new element into an array so that it remains in order. The special case when idx is -1 just involves putting the value at the end. But generally there will be a lot of shuffling, making insertion much slower than array access. Note that this routine breaks the first rule for dealing with arrays: It goes beyond the end of the array and writes to arr[n]. For this to work, the array needs to have a dimension of at least n+1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.