-1

What is the time complexity of the method String.GetHashCode()? For example, if hashed string of length n, by mod 2 using Horner's scheme it's O(n). What is Big O for GetHashCode?

Florian Greinacher
  • 14,478
  • 1
  • 35
  • 53
Dmytro
  • 63
  • 8
  • 1
    I don't think it's specified, which means "you should not make any assumptions". If you want this information to do something then you are going down the wrong path. If you ask out of curiosity, why not just use a decompiler and find out? – Jon Sep 19 '14 at 17:36
  • If to clarify question, I would like to know how working this method, if it provides an advantage in performance over a method with Horner's scheme. – Dmytro Sep 19 '14 at 17:47
  • 1
    Well, technically is O(n/4), but I believe that is considered O(n). String.GetHashCode generates a hash of the memory used by the string based on the words (two at a time), not the characters (hence n/4) – Peter Ritchie Sep 19 '14 at 17:48
  • If you want to change the way String.GetHashCode works (and potentially reduce hash collisions, see http://msdn.microsoft.com/en-us/library/jj152924(v=vs.110).aspx I don't know the Big-O of the randomized algorithm. – Peter Ritchie Sep 19 '14 at 17:52
  • Should be duplicate of https://stackoverflow.com/questions/3053726/why-might-a-system-string-object-not-cache-its-hash-code – Alexei Levenkov Dec 26 '19 at 22:54

1 Answers1

2

According to the reference source the time complexity is O(n). It basically just takes each character of the string and adds its value to the hash.

As mentioned in Peter Ritchie's comment the algorithm can be changed by using the <UseRandomizedStringHashAlgorithm> element.

Wai Ha Lee
  • 8,598
  • 83
  • 57
  • 92
Florian Greinacher
  • 14,478
  • 1
  • 35
  • 53