[java] Java HashMap 성능 최적화 / 대안

“on / off topic”의 회색 영역으로 들어가지만 Oscar Reyes의 제안과 관련하여 혼란을 없애기 위해 필요합니다. 더 많은 해시 충돌이 HashMap의 요소 수를 줄이므로 좋은 것입니다. 오스카가 무슨 말을하는지 오해 할 수도 있지만, kdgregory, delfuego, Nash0, 그리고 나는 모두 같은 (오해) 이해를 공유하는 것 같습니다.

Oscar가 동일한 해시 코드를 가진 동일한 클래스에 대해 말하는 것을 이해하면 주어진 해시 코드를 가진 클래스의 인스턴스 하나만 HashMap에 삽입되도록 제안합니다. 예를 들어 해시 코드가 1 인 SomeClass 인스턴스와 해시 코드가 1 인 SomeClass의 두 번째 인스턴스가있는 경우 SomeClass 인스턴스 하나만 삽입됩니다.

http://pastebin.com/f20af40b9 의 Java pastebin 예제 는 위의 내용이 Oscar가 제안한 내용을 올바르게 요약 한 것으로 보입니다.

에 관계없이 어떤 이해 나 오해, 무슨 일 같은 클래스의 다른 인스턴스가 않는 것입니다 되지 는 키가 동일인지 여부 만 결정되지 때까지 -가 동일한 해시 코드가있는 경우의 HashMap에 한 번만 삽입 얻을. 해시 코드 계약에서는 동일한 객체가 동일한 해시 코드를 가져야합니다. 그러나 동일하지 않은 객체가 다른 해시 코드를 가질 필요는 없습니다 (다른 이유로 바람직 할 수 있음) [1].

pastebin.com/f20af40b9 예제 (Oscar가 적어도 두 번 언급 함)는 다음과 같지만 인쇄 라인이 아닌 JUnit 어설 션을 사용하도록 약간 수정되었습니다. 이 예제는 동일한 해시 코드가 충돌을 일으키고 클래스가 동일 할 때 하나의 항목 만 생성된다는 제안을 지원하는 데 사용됩니다 (예 :이 특정 경우에는 하나의 문자열 만).

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

그러나 해시 코드가 완전한 이야기는 아닙니다. pastebin 예제가 무시하는 것은 s및 둘 다 ese동일 하다는 사실입니다. 둘 다 문자열 “ese”입니다. 따라서 s또는 ese또는 "ese"키를 키로 사용하여지도의 콘텐츠를 삽입하거나 가져 오는 것은 모두 동일 s.equals(ese) && s.equals("ese")합니다.

두 번째 테스트는 동일한 클래스의 동일한 해시 코드 가 테스트 1에서 호출 될 때 키-> 값 s -> 1을 덮어 쓰는 이유라는 결론을 내리는 것이 잘못되었음을 보여줍니다 . 시험이에서, 그리고 여전히 같은 해시 코드를 (에 의해 확인으로 ) 그리고 그들은 같은 클래스입니다. 그러나 하고 있는 경우는 없습니다 자바,이 테스트에서 인스턴스 – 유일한 차이점과 같음되는이 테스트에 대한 관련 : 위의 테스트 하나를, 반면에 시험이있는 :ese -> 2map.put(ese, 2)seseassertEquals(s.hashCode(), ese.hashCode());seseMyStringStringString s equals String eseMyStrings s does not equal MyString ese

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}

나중에 언급 한 내용을 바탕으로 오스카는 앞서 말한 내용을 뒤집는 것처럼 보이며 평등의 중요성을 인정합니다. 그러나 “동일한 클래스”가 아니라 동등하다는 개념은 여전히 ​​명확하지 않은 것 같습니다 (내 강조).

“그렇지 않습니다. 목록은 해시가 같지만 키가 다른 경우에만 생성됩니다. 예를 들어 문자열이 해시 코드 2345를 제공하고 정수가 동일한 해시 코드 2345를 제공하면 문자열이 목록에 삽입됩니다. equals (Integer)는 false입니다. 그러나 동일한 클래스 (또는 적어도 .equals가 true를 반환) 가 있으면 동일한 항목이 사용됩니다. 예를 들어 new String ( “one”) 및`new String ( “one”)은 다음과 같이 사용됩니다. 키는 동일한 항목을 사용합니다. 실제로 이것은 처음에 HashMap의 전체 지점입니다. 직접 확인 : pastebin.com/f20af40b9 – Oscar Reyes “

같음에 대한 언급없이 동일한 클래스와 동일한 해시 코드의 중요성을 명시 적으로 설명하는 이전 주석과 비교 :

“@delfuego : 직접보십시오 : pastebin.com/f20af40b9 그래서,이 질문에서 같은 클래스가 사용되고 있습니다 (잠시만, 같은 클래스가 올바르게 사용되고 있습니까?) 이것은 같은 해시가 같은 항목을 사용할 때를 의미합니다 사용되며 항목 “목록”이 없습니다. – Oscar Reyes “

또는

“실제로 이것은 성능을 향상시킬 것입니다. 충돌이 많을수록 해시 테이블 eq의 항목이 적습니다. 할 일이 적습니다. 해시 (잘 보임)도 해시 테이블 (잘 작동 함)도 객체에있을 것입니다. 성능이 저하되는 창작물 – Oscar Reyes “

또는

“@kdgregory : 예,하지만 다른 클래스에서 충돌이 발생하는 경우에만 동일한 클래스 (이 경우)에 대해 동일한 항목이 사용됩니다. – Oscar Reyes”

다시 말하지만, 나는 오스카가 실제로 말하려는 것을 오해 할 수 있습니다. 그러나 그의 원래 의견은 충분한 혼란을 불러 일으켜 일부 명시적인 테스트로 모든 것을 정리하는 것이 현명 해 보이기 때문에 지속적인 의심이 없습니다.

---

[1] -Joshua Bloch의 Effective Java, Second Edition 에서 :

• 응용 프로그램을 실행하는 동안 동일한 객체에서 두 번 이상 호출 될 때마다 hashCode 메서드는 객체에 대한 동일한 비교에 사용 된 정보가 수정되지 않는 한 동일한 정수를 일관되게 반환해야합니다. 이 정수는 애플리케이션의 한 실행에서 동일한 애플리케이션의 다른 실행까지 일관성을 유지할 필요가 없습니다.

• 동일한 s (Obj ect) 메서드에 따라 두 개체가 같은 경우 두 개체 각각에 대해 hashCode 메서드를 호출하면 동일한 정수 결과가 생성되어야합니다.

• 동일한 s (Object) 메서드에 따라 두 개체가 같지 않은 경우 두 개체 각각에 대해 hashCode 메서드를 호출하면 고유 한 정수 결과가 생성되어야하는 것은 아닙니다. 그러나 프로그래머는 같지 않은 개체에 대해 고유 한 정수 결과를 생성하면 해시 테이블의 성능이 향상 될 수 있음을 알고 있어야합니다.

---

답변