Design a hash table data structure using chaining strategy. Your hash table shou

Question

Design a hash table data structure using chaining strategy. Your hash table should use chaining strategy and it should convert the linked list to a tree if the size of linked list become 11 or more and it should convert it back to a linked list if its size is smaller or equal to 9. The other specification of your hash table is the capability to change the size of the table dynamically. You have to have a rehash function that changes the size of the hash table if the number of entries exceeds (n lg n) in which n is the size of table. However your rehash function should not copy the older table in a larger table; it should insert the elements of the older table one by one in the new table (Why?).

Use C++ language.

Submit three different files for header, cpp and a main file to test it.

Explanation / Answer

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package chegg.july;

/**
*
* @author Sam
*/
public class StringHash {
    private final int SIZE;
    private final String[] hashTable;
    private int count;
  
    public StringHash() {
        SIZE = 20;
        hashTable = new String[SIZE];
        count = 0;
    }

    public StringHash(int SIZE) {
        this.SIZE = SIZE;
        hashTable = new String[SIZE];
    }
  
    public int hash(String string){
        int hash = 0;
        for (int i = 0; i < string.length(); i++)
            hash = hash*31 + string.charAt(i);
      
        hash = hash % SIZE;
        return hash;
    }
  
    public void add(String newString) {
        int hash = hash(newString);
        while (hashTable[hash]!= null)
            hash = (hash+1)%SIZE;
        hashTable[hash] = newString;
        count++;
    }
  
    public boolean contains(String string) {
        int hash,hashStart;
        hash = hashStart= hash(string);
        if (hashTable[hash] == null)
            return false;
        while (!string.equals(hashTable[hash])) {
            hash = (hash + 1) % SIZE;
            if (hash == hashStart)
                return false;
            if (hashTable[hash] == null)
                return false;
        }
        return true;
    }
  
    public void remove(String string) {
        int hash,hashStart;
        hash = hashStart= hash(string);
        if (hashTable[hash] == null)
            return;
        while (!string.equals(hashTable[hash])) {
            hash = (hash + 1) % SIZE;
            if (hash == hashStart)
                return;
            if (hashTable[hash] == null)
                return;
        }
        hashTable[hash] = null;
        count--;
    }
  
    public int size() {
        return count;
    }
}

This code is in JAVA. Am uploading the C++ version within 2hours. Please be patient!

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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