490 views
3 votes
3 votes

Which of the below options is TRUE for this statement :
Suppose we wish to repeatedly search a linked list of length N elements, each of which contains a very long string key. How might we take advantage of the hash value when searching the list for an element with a given key?

  1. by calculating hash function for the table
  2. precompute the hash value of each string in the list
  3. calculate hash value of the single string only
  4. none of the above

2 Answers

2 votes
2 votes

Each node of the Linked List has a very long string. And we repeatedly need to search this Linked List. Hence, at each node, there's possibly a very long comparison to make.

If there are n nodes, and length of each string is p, searching complexity would be $O(np)$ for a single search. For multiple searches, this would take a lot of time.

What we can do is calculate hash value of the input string, and all the strings in the nodes. By this method, only when the hash value matches, should we proceed and check string all the way.

With a wisely selected hash function, we can uniformly distribute hash values, and effectively reduce the search time from $O(np)$ to $O(n)$ for a single search.

Option B


To make things simple, assume number of nodes = size of string = number of searches to make = n. So, complexity = $O(n^3)$ for n searches

Precomputing hash values of all the nodes would reduce this problem to $O(1)$ comparison per node. So, complexity = $O(n^2)$ for n searches — a huge improvement.

1 votes
1 votes
So, here our linked list is a list of "strings" and each of this is a key. Now, while searching we are actually searching for a key value. i.e., for each node in the linked list we do

hash(node->value) == value;

So, by precomputing the hashvalue of all nodes, we can avoid the hash() function execution while traversing and checking the list.
Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked Oct 4, 2016
346 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___