29

It's usually said that inserting and finding a string in a hash table is O(1). But how is hash key of a string made? Why it's not considered O(L), length of string?
It is clear to me that why for integers it is O(1), but not for strings.

I do understand why in general, inserting into a hash table is O(1), but I am confused about the step before inserting the hash into table: making the hash value.

Also is there any difference between how hash keys for strings are generated in java and unordered_map in C++?
Thanks.

6
  • 3
    Why do you concern yourself with the length of the string, but ignore the number of bits in the integer?
    – Matt
    Jul 21, 2015 at 21:19
  • 10
    Ah, the magic "O(1)" that has universal meaning even without any context.
    – Kerrek SB
    Jul 21, 2015 at 21:22
  • 2
    @Matt, Since when the number can be fit into 32 bits or 64 bits, most of the operations can be done in O(1) by CPU. Also, most of the time we have long strings, rather than big integers. (Especially, when it comes to programming competitions!)
    – MehrdadAP
    Jul 21, 2015 at 21:24
  • 3
    I don't think you quite grasp what O(1) means in this context. The time it takes to hash a key has nothing at all to do with the current size of the hash table.
    – azurefrog
    Jul 21, 2015 at 21:24
  • 7
    Java Strings cache their hash code after it's computed the first time, so you don't have to compute it again. Jul 21, 2015 at 21:30

4 Answers 4

21

Inserting etc. in a hashtable is O(1) in the sense that it is constant (or more precisely, bounded) in regard to the number of elements in the table.

The "O(1)" in this context makes no claim about how fast you can compute your hashes. If the effort for this grows in some way, that is the way it is. However, I find it unlikely that the complexity of a decent (i.e. "fit for this application") hash function will ever be worse than linear in the "size" (i.e. the length in our string-example) of the object being hashed.

0
16

It's usually said that inserting and finding a string in a hashtable is O(1). But how is hash key of a string made ? Why it's not O(L), length of string? It's clear for me that why for integers it's O(1), but not for strings.

The O(1) commonly quoted means the time doesn't grow with the number of elements in the container. As you say, the time to generate a hash value from a string might not itself be O(1) in the length of the string - though for some implementations it is: for example Microsoft's C++ std::hash<std::string> has:

            size_t _Val = 2166136261U;
            size_t _First = 0;
            size_t _Last = _Keyval.size();
            size_t _Stride = 1 + _Last / 10;

            if (_Stride < _Last)
                    _Last -= _Stride;
            for(; _First < _Last; _First += _Stride)
                    _Val = 16777619U * _Val ^ (size_t)_Keyval[_First];
            return (_Val);

The _Stride is a tenth of the string length, so a fixed number of characters that far apart will be incorporated in the hash value. Such a hash function is O(1) in the length of the string.

GCC's C++ Standard library takes a different approach: in v4.7.2 at least, it calls down through a _Hash_impl support class to the static non-member function _Hash_bytes, which does a Murmur hash incorporating every byte. GCC's hash<std::string> is therefore O(N) in the length of the string.

  • GCC's higher prioritorisation of collision minimisation is also evident in its use of prime numbers of buckets for std::unordered_set and std::unordered_map, which MS's implementation doesn't do - at least up until VS2013/VC12; summarily MS's approach will be lighter-weight/faster for keys that aren't collision prone, and at lower load factors, but degrades earlier and more dramatically otherwise.

And is there any difference between how hash keys for strings are produced between hashTable in java and unordered_map in C++?

How strings are hashed is not specified by the C++ Standard - it's left to the individual compiler implementations. Consequently, different compromises are struck by different compilers - even different versions of the same compiler.

The documentation David Pérez Cabrera's answer links to explains the hashCode function in Java:

Returns a hash code for this string. The hash code for a String object is computed as

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

That's clearly O(N) in the length of the string.

Returning quickly to...

It's usually said that inserting and finding a string in a hashtable is O(1).

...a "key" ;-P insight is that in many problem domains, the real-world lengths of the strings is known not to vary significantly, or hashing for the worst-case length is still plenty fast enough. Consider a person's or company's name, a street address, an identifier from some source code, a programming-language keyword, a product/book/CD etc name: you can expect a billion keys to take roughly a million times more memory to store than the first thousand. With a hash table, most operations on the entire data set can be expected to take a million times longer. And this will be as true in 100 years' time as it is today. Importantly, if some request comes in related to a single key, it shouldn't take much longer to perform than it used to with a thousand keys (assuming sufficient RAM, and ignoring CPU caching effects) - though sure, if it's a long key it may take longer than for a short key, and if you have ultra-low-latency or hard-realtime requirements, you may care. But, the average throughput for requests with random keys will be constant despite having a million times more data.

Only when you have a problem domain with massive variance in key size and the key-hashing time is significant given your performance needs, or where you expect the average key size to increase over time (e.g. if the keys are video streams, and every few years people are bumping up resolutions and frame rates creating an exponential growth in key size), will you need to pay close attention to the hashing (and key comparison) costs.

5
  • "The _Stride is a tenth of the string length, so a fixed number of characters that far apart will be incorporated in the hash value. Such a hash function is O(1) in the length of the string." I would say the correct time complexity, in this case, is O(log N), N is the length of the string. Isn't it?
    – Ali Salehi
    Mar 17, 2021 at 15:54
  • @AliSalehi: Sorry to say, but no it itn't. If N is the length of the string, and you just pick 10 positions along the string, then it doesn't matter if the string was 10 characters long or 10 million characters long - you can directly access those 10 characters without traversing the rest, due to memory being random access. There's is a fixed upper processing effort regardless of the length of the string, hence O(1). Mar 17, 2021 at 16:02
  • That is true, I thought in the for-loop that you copied from the function: for(; _First < _Last; _First += _Stride) it is going all the way up to _Last with the strides of 10, I didn't notice that _Stride = 1 + _Last / 10;
    – Ali Salehi
    Mar 17, 2021 at 16:14
  • 1
    @AliSalehi Yes - the stride is N/10. But, even if it was doing strides of 10 characters, that would be O(N) not O(log N). For example, to hash a 10 thousand character string, you'd still be doing a thousand times more work than for a 10 character string - it's increased in the same 10,000:10 = 1000:1 ratio as the string length increased, hence O(N). Mar 17, 2021 at 16:18
  • @AliSalehi If N is above the size storable in a processor register, you would get O(log N), but then probably your memory will run out very soon.
    – Sebastian
    Feb 22, 2022 at 23:15
4

Acording to implementation of Java, Hashtable use the hashCode method of key (String or Integer). Hashtable String.hashCode Integer.hashCode

And C++ use std::hash<std::string> or std::hash<int> according to http://en.cppreference.com/w/cpp/utility/hash and the implementation was in functional file (/path/to/c++... /include/c++/4.8/functional)

1
  • Interesting to see the Java implementation... thanks! Jul 22, 2015 at 6:19
1

The complexity of a hashing function is never O(1). If the length of the string is n then the complexity is surely O(n). However, if you compute all hashes in a given array, you won't have to calculate for the second time and you can always compare two strings in O(1) time by comparing the precalculated hashes.

2
  • 2
    "The complexity of a hashing function is never O(1)." - that's not true, not even for strings - see my answer where I show Microsoft's string hashing function, which only visits 10 characters along the string and is therefore O(1). "you can always compare two strings in O(1) time by comparing the precalculated hashes" - not always, it depends what comparison you need: h1 != h2 implies s1 != s2, but h1 == h2 does not imply s1 == s2, though it makes it very likely (so much so that with >= 128bit hashes you might trust it in practice, depending on how serious a mistake would be). Feb 23, 2022 at 4:00
  • To compare the hashes you will need to locate the string in the array which will amount to compute the hash of the string. Oct 9, 2022 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.