Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <ul> <li>Why doesn't String's hashCode() cache 0?</li> </ul> </blockquote> <p>The value zero is reserved as meaning "the hash code is not cached".</p> <blockquote> <ul> <li>What is the probability that a Java string hashes to 0?</li> </ul> </blockquote> <p>According to the Javadoc, the formula for a String's hashcode is:</p> <pre><code>s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] </code></pre> <p>using <code>int</code> arithmetic, where <code>s[i]</code> is the ith character of the string and <code>n</code> is the length of the string. (The hash of the empty String is defined to be zero as a special case.)</p> <p>My intuition is that the hashcode function as above gives a uniform spread of String hash values across the range of <code>int</code> values. A uniform spread that would mean that the probability of a randomly generated String hashing to zero was 1 in 2^32.</p> <blockquote> <ul> <li>What's the best way to avoid the performance penalty of recomputing the hash value every time for strings that hash to 0?</li> </ul> </blockquote> <p>The best strategy is to ignore the issue. If you are repeatedly hashing the same String value, there is something rather strange about your algorithm.</p> <blockquote> <ul> <li>Is this the best-practice way of caching values? (i.e. cache all except one?)</li> </ul> </blockquote> <p>This is a space versus time trade-off. AFAIK, the alternatives are:</p> <ul> <li><p>Add a <code>cached</code> flag to each String object, making every Java String take an extra word.</p></li> <li><p>Use the top bit of the <code>hash</code> member as the cached flag. That way you can cache all hash values, but you only have half as many possible String hash values.</p></li> <li><p>Don't cache hashcodes on Strings at all.</p></li> </ul> <p>I think that the Java designers have made the right call for Strings, and I'm sure that they have done extensive profiling that confirms the soundness of their decision. However, it <em>does not</em> follow that this would <em>always</em> be the best way to deal with caching.</p> <p>(Note that there are two "common" String values which hash to zero; the empty String, and the String consisting of just a NUL character. However, the cost of calculating the hashcodes for these values is small compared with the cost of calculating the hashcode for a typical String value.)</p>
    singulars
    1. This table or related slice is empty.
    1. POWhy doesn't String's hashCode() cache 0?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USStephen C
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COI do not believe 1 in 2^32 is correct: For shorter strings the hash code will be in the range: [0, Integer.MAX_VALUE] and for any strings long enough to cause overflow the hash code will be in the range: [Integer.MIN_VALUE, Integer.MAX_VALUE]. Hence for randomly generated strings (and assuming a uniformly distributed hashing algorithm) the distribution is not completely uniform; there is a higher chance of a positive *or zero* hash code than a negative one.
      singulars
      1. PO
      1. USAdamski
    2. COThe `hashCode` algorithm causes integer overflow pretty quickly, *Adamski*. Taking a few random examples, 6 word characters appears to be enough - but I think your reasoning is sound, this does result in a skew towards positive hash values (which degrades as your Strings get longer)
      singulars
      1. PO
      1. USoxbow_lakes
    3. CORandomly generated Strings have random lengths as well as random characters.
      singulars
      1. PO
      1. USStephen C
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload