Question

: (6 points) Typical hash function for a string key. Fill the missing line of code. Th hash function should compute a polynomial of the form: s[0] + s[1] * 37 + s[2] * 372 + s[3] * 373 + + s[n-l] * 37, where s[i] is the it character of string s, for i = 0, . . ., n-1. The length of string s is n. si size_t hash(const string &s) 1f const int n- s.length); for (int i = n-1; ǐ >= 0; --ǐ) { // Insert missing code below. hash value-... return hash value
0 0
Add a comment Improve this question Transcribed image text
Answer #1

The missing code:-

hash_value = hash_value + s[i] * pow(37, i);

The Complete hash function after adding missing line of code:-

#include <cmath>   // used for pow() function

size_t hash(const string &s) {

                size_t hash_value = 0;

                const int n = s.length();

                for(int i = n-1; i >= 0; --i) {

                                hash_value = hash_value + s[i] * pow(37,i);

                }

                return hash_value

}

Explaination of code:-

The above code will start with the value of i=n-1, so the polynomial will be computed as

s[n-1]*37n-1 + s[n-2]*37n-2 + ....................+ s[3]*373 + s[2]*372 + s[1]*37 + s[0]

Add a comment
Know the answer?
Add Answer to:
: (6 points) Typical hash function for a string key. Fill the missing line of code....
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • (20 pts) Fill in the missing code: This recursive method returns “even” if the length of...

    (20 pts) Fill in the missing code: This recursive method returns “even” if the length of a give String is even, and “odd” if the length of the String is odd. public static String foo(String s) { if (s.length() ==0)    return “even”; else if (s.length() = = 1)    return “odd”; else     //your code goes here } (40 pts) You coded the following in the file Test.java : System.out.println( foo(5)); //more code here public static int foo(int n)...

  • How do I do this? -> string print() const; Function to output the data, return the...

    How do I do this? -> string print() const; Function to output the data, return the output in the form of string, with all elements in the hash table included and each seperated by a space this is my code: template <class elemType> string hashT<elemType>::print() const { for (int i = 0; i < HTSize; i++){        if (indexStatusList[i] == 1){        cout <<HTable[i]<< " " << endl;        }   }    } **********Rest of the code...

  • #include using namespace std; vector split_string(string); // Complete the findMedian function below. int findMedian(vector arr) {...

    #include using namespace std; vector split_string(string); // Complete the findMedian function below. int findMedian(vector arr) { } int main() { ofstream fout(getenv("OUTPUT_PATH")); int n; cin >> n; cin.ignore(numeric_limits::max(), '\n'); string arr_temp_temp; getline(cin, arr_temp_temp); vector arr_temp = split_string(arr_temp_temp); vector arr(n); for (int i = 0; i < n; i++) { int arr_item = stoi(arr_temp[i]); arr[i] = arr_item; } int result = findMedian(arr); fout << result << "\n"; fout.close(); return 0; } vector split_string(string input_string) { string::iterator new_end = unique(input_string.begin(), input_string.end(), []...

  • In C++ please! *Do not use any other library functions(like strlen) than the one posted(<cstddef>) in the code below!* /** CS 150 C-Strings Follow the instructions on your handout to complete t...

    In C++ please! *Do not use any other library functions(like strlen) than the one posted(<cstddef>) in the code below!* /** CS 150 C-Strings Follow the instructions on your handout to complete the requested function. You may not use ANY library functions or include any headers, except for <cstddef> for size_t. */ #include <cstddef> // size_t for sizes and indexes ///////////////// WRITE YOUR FUNCTION BELOW THIS LINE /////////////////////// ///////////////// WRITE YOUR FUNCTION ABOVE THIS LINE /////////////////////// // These are OK after...

  • PROGRAMMING PROJECTS Implement the class umapHash Key, which creates a hash function for miniPair...

    Data Structure in C++ please type the code and the output. thanks PROGRAMMING PROJECTS Implement the class umapHash Key, which creates a hash function for miniPair ob- iects that uses only the key of the pair (first). The third template argument is a func- tion object type that takes a Key argument. Place the class in the header file "umaphash.h" 37. (a) // a hash function object type that applies KeyHashFunc // to the key in a miniPair object template...

  • Java class quiz need help~ This is the Backwards.java code. public class Backwards { /** *...

    Java class quiz need help~ This is the Backwards.java code. public class Backwards { /** * Program starts with this method. * * @param args A String to be printed backwards */ public static void main(String[] args) { if (args.length == 0) { System.out.println("ERROR: Enter a String on commandline."); } else { String word = args[0]; String backwards = iterativeBack(word); // A (return address) System.out.println("Iterative solution: " + backwards); backwards = recursiveBack(word); // B (return address) System.out.println("\n\nRecursive solution: " +...

  • Follow the TODOs and complete the insertItem(), searchItem() and printTable() functions in hash.cpp. The hash function...

    Follow the TODOs and complete the insertItem(), searchItem() and printTable() functions in hash.cpp. The hash function has already been implemented for you. // hash.CPP program to implement hashing with chaining #include<iostream> #include "hash.hpp" using namespace std; node* HashTable::createNode(int key, node* next) { node* nw = new node; nw->key = key; nw->next = next; return nw; } HashTable::HashTable(int bsize) { this->tableSize= bsize; table = new node*[tableSize]; for(int i=0;i<bsize;i++) table[i] = nullptr; } //function to calculate hash function unsigned int HashTable::hashFunction(int key)...

  • Identify the letters and anything associated with it. It is a hash map so please feel...

    Identify the letters and anything associated with it. It is a hash map so please feel free to point out the other important parts beside the arrows. I apologize for the order of the pictures class HashMap private: HashEntry table ; public: HashMap() table-new HashEntry * [TABLE_SIZE]; for (int 1-0; 1< TABLE SIZE: i++) table [i] = NULL; Hash Function int HashFunc(int key) return key % TABLE-SIZE; Insert Element at a key void Insert(int key, int value) int hashHashFunc(key); while...

  • C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can...

    C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can be used to implement a Set ADT. Let's try to use the template below to implement a Set with double hashing. Here we assume the Set contains names with 3 characters long. Since it is a Set, we do not need to have an explicit value for each key. We will use a token value of 1 if a name belongs to the Set....

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT