3. (60)Hashtable with Quadratic Probing. Implement a simple hashtable using quad

Question

3. (60)Hashtable with Quadratic Probing. Implement a simple hashtable using quadratic probing for collision resolution. Both the keys and values are integers, assuming greater than 0. The initial table size rn should be 11 (it is too small for a real hashtable, we just use it for the purpose of this homework). Let n be the number of items in the table. When nm/2, use the technique of dynamic arrays to enlarge the table. You want to approximately double the table size but keep to the primes. The next table size m will be 23 You should use key%m as the hash function. Let b be the hash value modulo m. If bucket b is occupied, you probe (D+ 12) % m, (D+ 22) % m, (b+32) % m, . .. , (D+ (m/2)2) % m, and stop as soon as you find an empty bucket As long as n is kept less than m/2, you will find an empty bucket by the end of the probing You should at least implement the following functions (a) void put (int key, int value): insert key-value pair to the hashtable. Insert key to the key array, value to the value array based on the hash function (b) int get (int key): get the value of the key (c) boolean contains(int key): return true if the hashtable contains the key (d) void remove(int key): remove the key-value pair

Explanation / Answer

public boolean contains(int key){

  
    for (int i = 0; i<n; i++){
        if (keys[i] == key)
           return true;
    }
    return false;
}

public void remove(int key){

    int found = 0;
    for (int i = 0; i<n; i++){
        if (keys[i] == key){
           found = 1;
           keys[i] = 0;
        }
    }
    if (found == 0) {
       System.out.println("Not found");
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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