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?
-
1I 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– Jon2014-09-19 17:36:40 +00:00Commented Sep 19, 2014 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– Dmytro2014-09-19 17:47:44 +00:00Commented Sep 19, 2014 at 17:47
-
1Well, 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– Peter Ritchie2014-09-19 17:48:25 +00:00Commented Sep 19, 2014 at 17:48
-
If you want to change the way String.GetHashCode works (and potentially reduce hash collisions, see msdn.microsoft.com/en-us/library/jj152924(v=vs.110).aspx I don't know the Big-O of the randomized algorithm.Peter Ritchie– Peter Ritchie2014-09-19 17:52:26 +00:00Commented Sep 19, 2014 at 17:52
-
Should be duplicate of stackoverflow.com/questions/3053726/…Alexei Levenkov– Alexei Levenkov2019-12-26 22:54:32 +00:00Commented Dec 26, 2019 at 22:54
Add a comment
|
1 Answer
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.
