String의 hashCode ()가 0을 캐시하지 않는 이유는 무엇입니까?

String의 hashCode ()가 0을 캐시하지 않는 이유는 무엇입니까?

---

Java 6 소스 코드에서 hashCode가 0 이외의 값만 캐시하는 것을 발견했습니다. 성능 차이는 다음 스 니펫에 의해 나타납니다.

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

ideone.com에서 실행 하면 다음과 같은 결과가 나타납니다.

Took 1470 ms.
Took 58 ms.

그래서 내 질문은 다음과 같습니다.

• String의 hashCode ()가 0을 캐시하지 않는 이유는 무엇입니까?
• Java 문자열이 0으로 해시 될 확률은 얼마입니까?
• 0으로 해시하는 문자열에 대해 매번 해시 값을 다시 계산하는 성능 저하를 피하는 가장 좋은 방법은 무엇입니까?
• 이것이 값을 캐싱하는 가장 좋은 방법입니까? (즉, 하나를 제외하고 모두 캐시 하시겠습니까?)

---

즐거움을 위해 여기에있는 각 줄은 0으로 해시되는 문자열입니다.

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

---

당신은 아무것도 걱정하지 않습니다. 이 문제에 대해 생각하는 방법이 있습니다.

일년 내내 문자열을 해싱하는 것 외에는 아무것도하지 않는 애플리케이션이 있다고 가정 해 보겠습니다. 메모리에있는 천 개의 문자열을 가져 와서 라운드 로빈 방식으로 반복해서 hashCode ()를 호출하고 백만 번을 거쳐 또 다른 천 개의 문자열을 가져 와서 다시 수행한다고 가정 해 봅시다.

그리고 문자열의 해시 코드가 0 일 가능성이 실제로 1 / 2 ^ 32보다 훨씬 컸다고 가정 해 보겠습니다. 나는 그것이 1 / 2 ^ 32보다 다소 크다고 확신 하지만, 1 / 2 ^ 16 (제곱근! 이제 훨씬 더 나쁘다!)처럼 그것보다 훨씬 더 나쁘다고 가정 해 봅시다.

이 상황에서 Oracle 엔지니어가 이러한 문자열의 해시 코드가 살아있는 다른 누구보다 캐시되는 방식을 개선하는 이점을 더 많이 얻을 수 있습니다. 그래서 당신은 그들에게 편지를 쓰고 고쳐달라고 요청합니다. 그리고 그들은 s.hashCode ()가 0이 될 때마다 즉시 (처음에도! 100 % 향상!) 반환되도록 마법을 사용합니다 . 그리고 다른 경우에 대해 성능을 전혀 저하시키지 않고이를 수행한다고 가정 해 보겠습니다.

만세! 이제 앱이 ... 보자 ... 0.0015 % 더 빨라졌습니다!

하루 종일 걸리던 작업이 이제 23 시간 57 분 48 초 밖에 걸리지 않습니다!

그리고 우리는 의심의 모든 가능한 이점을 종종 터무니없는 정도로 제공하도록 시나리오를 설정했습니다.

이것이 당신에게 그만한 가치가있는 것 같습니까?

편집 : 이 글을 몇 시간 전에 게시 한 이후로 내 프로세서 중 하나가 해시 코드가없는 두 단어 구문을 찾기 위해 거칠게 실행되도록했습니다. 지금까지는 bequirtle zorillo, chronogrammic schtoff, 타박상이있는 회랑, creashaks organzine, drumwood boulderhead, electroanalytic exercisable, favosely nonconstruable이 있습니다. 이것은 약 2 ^ 35 가능성에서 벗어난 것이므로 완벽한 분포를 사용하면 8 개만 볼 수있을 것으로 예상됩니다. 완료 될 때쯤에는 분명히 몇 배는 있지만 이상하게 더 많이는 아닙니다. 더 중요한 것은 제가 이제 몇 가지 흥미로운 밴드 이름 / 앨범 이름을 생각 해냈다는 것입니다! 공정한 절도 금지!

---

0을 사용하여 "아직 해시 코드를 작성하지 않았습니다"를 나타냅니다. 대안은 더 많은 메모리를 차지하는 별도의 부울 플래그를 사용하는 것입니다. (물론 해시 코드를 캐시하지 않으려는 경우도 있습니다.)

많은 문자열이 0으로 해시되는 것을 기대하지 않습니다 . 아마도 해싱 루틴이 의도적으로 0을 피하는 것이 합리적 일 것입니다 (예 : 해시를 0에서 1로 변환하고이를 캐시). 그러면 충돌이 증가하지만 재해 싱은 피할 수 있습니다. String hashCode 알고리즘이 명시 적으로 문서화되어 있기 때문에 지금은 너무 늦었습니다.

이것이 일반적으로 좋은 아이디어인지 여부에 관해서는 확실히 효율적인 캐싱 메커니즘이며, 해시 0으로 끝나는 값을 다시 해싱하지 않도록 변경하면 더 좋을 수도 있습니다 (편집 참조). 개인적으로보고 싶습니다. 썬은 이것이 처음부터 가치가 있다고 믿게 만든 데이터입니다. 생성 된 모든 문자열에 대해 추가 4 바이트를 차지하지만 자주 또는 드물게 해시되며 유일한 이점은 두 번 이상 해시 된 문자열에 대한 것 입니다.

편집 : KevinB가 다른 주석에서 지적했듯이 위의 "0 방지"제안 은 매우 드문 경우에 도움이 되지만 모든 해시 계산에 대해 추가 비교가 필요 하기 때문에 순 비용 이 발생할 수 있습니다 .

---

지금까지 다른 답변이 누락 된 중요한 것이 있다고 생각합니다. 0 값이 존재하므로 hashCode 캐싱 메커니즘이 다중 스레드 환경에서 강력하게 작동합니다.

cachedHashCode 자체 및 cachedHashCode가 계산되었는지 여부를 나타내는 isHashCodeCalculated 부울과 같은 두 개의 변수가있는 경우 다중 스레드 환경에서 작업하려면 스레드 동기화가 필요합니다. 특히 문자열은 여러 스레드에서 매우 일반적으로 재사용되기 때문에 동기화는 성능에 좋지 않습니다.

Java 메모리 모델에 대한 나의 이해는 약간 개략적이지만 대략적인 내용은 다음과 같습니다.

1. 여러 스레드가 변수 (예 : 캐시 된 hashCode)에 액세스 할 때 각 스레드가 최신 값을 볼 것이라는 보장은 없습니다. 변수가 0에서 시작하면 A가이를 업데이트하고 (0이 아닌 값으로 설정) 스레드 B는 곧바로이를 읽고 스레드 B는 여전히 0 값을 볼 수 있습니다.

2. There's another problem with accessing shared values from multiple threads (without synchronization) - you can end up trying to use an object that's only been partly initialized (constructing an object is not an atomic process). Multi-threaded reads and writes of 64-bit primitives like longs and doubles are not necessarily atomic either, so if two threads try to read and change the value of a long or a double, one thread can end up seeing something weird and partially set. Or something like that anyway. There are similar problems if you try to use two variables together, like cachedHashCode and isHashCodeCalculated - a thread can easily come along and see the latest version of one of those variables, but an older version of another.

3. 이러한 멀티 스레딩 문제를 해결하는 일반적인 방법은 동기화를 사용하는 것입니다. 예를 들어, 캐시 된 hashCode에 대한 모든 액세스를 동기화 된 블록 안에 넣거나 volatile 키워드를 사용할 수 있습니다 (시맨틱이 약간 혼란 스럽기 때문에주의해야 함).

4. 그러나 동기화로 인해 속도가 느려집니다. 문자열 hashCode와 같은 것은 나쁜 생각입니다. 문자열은 HashMaps에서 키로 자주 사용되므로 다중 스레드 환경을 포함하여 잘 수행하려면 hashCode 메서드가 필요합니다.

5. Java primitives that are 32-bits or less, like int, are special. Unlike, say, a long (64-bit value), you can be sure that you will never read a partially initialized value of an int (32 bits). When you read an int without synchronization, you can't be sure that you'll get the latest set value, but you can be sure that the value you do get is a value that has explicitly been set at some point by your thread or another thread.

The hashCode caching mechanism in java.lang.String is set up to rely on point 5 above. You might understand it better by looking at the source of java.lang.String.hashCode(). Basically, with multiple threads calling hashCode at once, hashCode might end up being calculated multiple times (either if the calculated value is zero or if multiple threads call hashCode at once and both see a zero cached value), but you can be sure that hashCode() will always return the same value. So it's robust, and it's performant too (because there's no synchronization to act as a bottleneck in multi-threaded environments).

Like I said, my understanding of the Java memory model is a little sketchy, but I'm pretty sure I've got the gist of the above right. Ultimately it's a very clever idiom for caching the hashCode without the overhead of synchronization.

---

0 isn't cached as the implementation interprets a cached value of 0 as "cached value not yet initialised". The alternative would have been to use a java.lang.Integer, whereby null implied that the value was not yet cached. However, this would have meant an additional storage overhead.

Regarding the probability of a String's hash code being computed as 0 I would say the probability is quite low and can happen in the following cases:

• The String is empty (although recomputing this hash code each time is effectively O(1)).
• An overflow occurs whereby the final computed hash code is 0 (e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0).
• The String contains only Unicode character 0. Very unlikely as this is a control character with no meaning apart from in the "paper tape world" (!):

From Wikipedia:

Code 0 (ASCII code name NUL) is a special case. In paper tape, it is the case when there are no holes. It is convenient to treat this as a fill character without meaning otherwise.

---

This turns out to be a good question, related to a security vulnerability.

"When hashing a string, Java also caches the hash value in the hash attribute, but only if the result is different from zero. Thus, the target value zero is particularly interesting for an attacker as it prevents caching and forces re-hashing."

---

• Why doesn't String's hashCode() cache 0?

The value zero is reserved as meaning "the hash code is not cached".

• What is the probability that a Java string hashes to 0?

According to the Javadoc, the formula for a String's hashcode is:

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 and n is the length of the string. (The hash of the empty String is defined to be zero as a special case.)

My intuition is that the hashcode function as above gives a uniform spread of String hash values across the range of int values. A uniform spread that would mean that the probability of a randomly generated String hashing to zero was 1 in 2^32.

• What's the best way to avoid the performance penalty of recomputing the hash value every time for strings that hash to 0?

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.

• Is this the best-practice way of caching values? (i.e. cache all except one?)

This is a space versus time trade-off. AFAIK, the alternatives are:

• Add a cached flag to each String object, making every Java String take an extra word.

• Use the top bit of the hash member as the cached flag. That way you can cache all hash values, but you only have half as many possible String hash values.

• Don't cache hashcodes on Strings at all.

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 does not follow that this would always be the best way to deal with caching.

(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.)

---

Well folks, it keeps 0 because if it is zero length, it will end up as zero anyways.

And it doesn't take long to figure out that the len is zero and so must the hashcode be.

So, for your code-reviewz! Here it is in all it's Java 8 glory:

 public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

As you can see, this will always return a quick zero if the string is empty:

  if (h == 0 && value.length > 0) ...

---

The "avoid 0" suggestion seems appropriate to recommend as best practice as it helps a genuine problem (seriously unexpected performance degradation in constructible cases that can be attacker supplied) for the meager cost of a branch operation prior to a write. There is some remaining 'unexpected performance degradation' that can be exercised if the only things going into a set hash to the special adjusted value. But this is at worst a 2x degradation rather than unbounded.

Of course, String's implementation can't be changed but there is no need to perpetuate the problem.

참고URL : https://stackoverflow.com/questions/2310498/why-doesnt-strings-hashcode-cache-0