Computer scienceAlgorithms and Data StructuresAlgorithmsPrinciples and techniquesHashing

Hash function

Life is complicated

Report a typo

Consider a hash function hh that computes the hash value of a string in linear time. You are provided with the following description of the hash function:

  1. It takes a string as input.

  2. It iterates through the string from left to right.

  3. In step ii, it calculates the hash value of the iith prefix, i.e. the substring from the first character to the iith one. In other words, if the string is a1a2ana_1a_2\dots a_n, at the iith step it computes h(a1a2ai)h(a_1a_2\dots a_i).

  4. It returns the list of these hash values in the same order they appear concatenated as a string.

Is it a good hash function? If not, which property is missing here?

Tip: Think about how the runtime of the described hash function might be affected by the size of the input string. Does the runtime increase proportionally with the length of the input?

Select one option from the list
___

Create a free account to access the full topic