Do in either C++ or Java. Only need to implement type D. Thank you. Write a clas

Question

Do in either C++ or Java. Only need to implement type D. Thank you.

Write a class, MyHashTable to implement a hash table that uses Open Hashing, and insert it in a test program The hash table efficiently stores records and uses character strings as keys. The member functions will be: MyHashTable(int sz); boolean insert (String key, String record); // returns false if key is present, true otherwise // create an empty has table of fixed size sz // key is a string of lower case alphabetic chars w/o spaces String isPresent(String key);// returns the record if key is present, null otherwise boolean delete(String key); int membership); void listAll) // returns false if key is not present, true otherwise // returns the number of records in the data structure // list all members of the hash table in the order that // they are stored. Precede each one with an integer giving // the index in the table of that record The hash function MUST BE as follows: int hash(String ky, int tableSize) [ int m - ky.lengthO; int sum0 for(int i-m-1;i>-0;i--) // use unsigned ints in C/C++ sum - sum*31 + (int) (ky.charAt(i)); // automatically applies mod 2 132) sum sum & 0x7fffffff return sum % tables ize // remove the sign bit // % works fine with a positive dividend Your program will read a text file from System.in that contains text commands. In response to each command your program will output one or more lines of text to System.out Here are the commands: L SZ Q sz D sz R // create a hash table of size sz that uses linear probing // create a hash table of size sz that uses quadratic probing // create a hash table of size sz that uses double hashing with h_2(y) R (y mod R) // empty the hash table and reset the statistics A soap:Keeps you clean /7 Insert record "Keeps you clean" with "soap" as its key. // Print one of the lines "Key soap inserted at location #", "Key soap already exists". OR // "Table has overflowed". In the latter case, the record isn't inserted // Delete the record that has "sin" as its key // Print one of the lines "Key sin deleted" OR "Key sin not found" R sin S fortune // Search for the key "fortune" // Print one of the lines "Key fortune:" then the record corresponding to that key, // then the text " found at location #" , OR Key fortune not found" // Print the line "Membership is #" where # is the number of records stored in the table // Print a list of the elements in the Table in the order of their position in the table, // one record per line in the form "# key: Record, where # is the position in the table // Print the following three lines: // Total probes during inserts = # // Total probes during unsuccessful searches = #

Explanation / Answer

JAVA Call

--------------------------------------------------------------------

public class HashTable {
private static int INITIAL_SIZE = 16;
private HashEntry[] entries = new HashEntry[INITIAL_SIZE];
public void insert(String key, String value) {
int hash = getHash(key);
final HashEntry hashEntry = new HashEntry(key, value);
if(entries[hash] == null) {
entries[hash] = hashEntry;
}
// If there is already an entry at current hash
// position, add entry to the linked list.
else {
HashEntry temp = entries[hash];
while(temp.next != null) {
temp = temp.next;
}
temp.next = hashEntry;
}
}

/**
* Returns 'null' if the element is not found.
*/
public String get(String key) {
int hash = getHash(key);
if(entries[hash] != null) {
HashEntry temp = entries[hash];

// Check the entry linked list for march
// for the given 'key'
while( !temp.key.equals(key)
&& temp.next != null ) {
temp = temp.next;
}
return temp.value;
}

return null;
}

private int getHash(String key) {
// piggy backing on java string
// hashcode implementation.
return key.hashCode() % INITIAL_SIZE;
}

public static class HashEntry {
String key;
String value;
// Linked list of same hash entries.
HashEntry next;

public HashEntry(String key, String value) {
this.key = key;
this.value = value;
this.next = null;
}

@Override
public String toString() {
return "[" + key + ", " + value + "]";
}
}

@Override
public String toString() {
int bucket = 0;
StringBuilder hashTableStr = new StringBuilder();
for (HashEntry entry : entries) {
if(entry == null) {
continue;
}
hashTableStr.append(" bucket[")
.append(bucket)
.append("] = ")
.append(entry.toString());
bucket++;
HashEntry temp = entry.next;
while(temp != null) {
hashTableStr.append(" -> ");
hashTableStr.append(temp.toString());
temp = temp.next;
}
}
return hashTableStr.toString();
}

public static void main(String[] args) {
HashTable hashTable = new HashTable();
// Put some key values.
for(int i=0; i<30; i++) {
final String key = String.valueOf(i);
hashTable.insert(key, key);
}

// Print the HashTable structure
log("**** HashTable ***");
log(hashTable.toString());
log(" Value for key(20) : " + hashTable.get("20") );
}

private static void log(String msg) {
System.out.println(msg);
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.