왜 외부 인터페이스가 HashMap에 hashCode/equals를 제공하도록 허용하지 않습니까?

Question

TreeMap을 사용하면 Comparator 사용자 지정을 제공하는 것이 간단하므로 Comparable 개체가지도에 추가 된 의미를 재정의 할 수 있습니다. 그러나 HashMap s는이 방식으로 제어 할 수 없습니다. 해시 값과 평등 검사를 제공하는 함수는 '횡'로드 될 수 없습니다.

인터페이스를 디자인하고 이것을 HashMap (또는 새 클래스)에 개조하는 것이 쉽고 유용 할 것으로 생각됩니다. 더 좋은 이름을 제외하고 이런 식으로 뭔가 :

new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY); 

이이 행할 수 있을까, 또는 당신이이 방법에 근본적인 문제를 볼 수 있습니다

interface Hasharator<T> { 
    int alternativeHashCode(T t); 
    boolean alternativeEquals(T t1, T t2); 
    } 

    class HasharatorMap<K, V> { 
    HasharatorMap(Hasharator<? super K> hasharator) { ... } 
    } 

    class HasharatorSet<T> { 
    HasharatorSet(Hasharator<? super T> hasharator) { ... } 
    } 

case insensitive Map 문제는 사소한 솔루션을 얻는다?

기존 (비 JRE) 라이브러리에서 접근법이 사용됩니까? no로 제목을 변경하지 :;

EDIT (. 구글, 행운을 시도))

편집을 hazzen 제시 니스 해결 방법을하지만 난 두려워 이것은 내가 ... 피하기 위해 노력하고있어 해결 방법은 더 긴 언급 "비교 자"; 나는 이것이 약간 혼란 스럽다고 생각한다.

편집 : 성능과 관련된 대답을 수락했습니다. 더 구체적인 답변을 사랑합니다!

편집 : 구현이 있습니다. 아래의 대답을 참조하십시오.

EDIT : 첫 번째 문장을 다시 말하면 내가 쓴 사이드 로딩임을 명확하게 나타내 었으며 (주문하지 않고 주문은 HashMap에 속하지 않음).

Answer 1

Trove4j에는 내가 가지고있는 기능이 있으며 해싱 전략이라고 부릅니다.

맵의 구현에는 제한이 다르므로 다른 전제 조건이 있으므로 Java의 "기본"HashMap 구현이 가능할 것이라는 암묵적인 의미는 아닙니다.

Answer 2

참고 : 다른 모든 답변에서 언급했듯이 HashMaps에는 명시적인 순서가 없습니다. 그들은 단지 "평등"만을 인정합니다. 해시 기반 데이터 구조에서 주문을받는 것은 의미가 없습니다. 각 객체는 해시 (기본적으로 난수)로 변환되기 때문에 의미가 없습니다.

신중하게하는 한 항상 클래스의 해시 함수를 작성할 수 있습니다 (종종 필요한 경우도 있음). 해시 기반 데이터 구조는 임의의 균일 한 해시 값 분포에 의존하기 때문에 제대로 수행하기가 어렵습니다. Effective Java에는 좋은 동작을하는 해시 메소드를 올바르게 구현하는 데 많은 양의 텍스트가 사용됩니다.

해쉬가 String의 대소 문자를 무시하기를 원하면이 목적으로 String 주위에 래퍼 클래스를 작성하여 데이터 구조에 삽입하면됩니다.

간단한 구현 :

public class LowerStringWrapper { 
    public LowerStringWrapper(String s) { 
     this.s = s; 
     this.lowerString = s.toLowerString(); 
    } 

    // getter methods omitted 

    // Rely on the hashing of String, as we know it to be good. 
    public int hashCode() { return lowerString.hashCode(); } 

    // We overrode hashCode, so we MUST also override equals. It is required 
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must 
    // restore that invariant. 
    public boolean equals(Object obj) { 
     if (obj instanceof LowerStringWrapper) { 
      return lowerString.equals(((LowerStringWrapper)obj).lowerString; 
     } else { 
      return lowerString.equals(obj); 
     } 
    } 

    private String s; 
    private String lowerString; 
} 

Answer 3

닷넷 (다른 인스턴스 자체를 비교할 수있는 타입) 및 IEquatable (두 객체를 비교할 수있는 타입) IEqualityComparer 통해이있다.

실제로 java.lang.Object 또는 System.Object에서 평등 및 해시 코드를 정의하는 것은 실수 였다고 생각합니다. 특히 평등은 상속으로 이해되는 방식으로 정의하기가 어렵습니다. 나는 이것에 관해 blog에 의미를 유지한다. ..

그러나 긍정, 근본적으로 생각은 건강하다.

Answer 4

좋은 질문은 josh bloch에게 문의하십시오. 그 개념을 자바 7의 RFE로 제출했지만, 그 이유는 뭔가 성능과 관련이 있다고 생각했다. 그래도 나는해야한다고 생각합니다.

Answer 5

hashCode 캐싱을 방지 할 수 있기 때문에 이것이 수행되지 않았을 것으로 생각됩니다.

모든 키를 자동으로 감싸는 일반 맵 솔루션을 만들려고했습니다. 래퍼가 래핑 된 객체, 캐쉬 된 hashCode 및 동등성 검사를 담당하는 콜백 인터페이스에 대한 참조를 보유해야한다는 것이 밝혀졌습니다. 이것은 분명히 래퍼 클래스를 사용하는 것만 큼 효율적이지는 않습니다. 원본 클래스와 하나의 객체를 캐시하면됩니다 (hazzens 응답 참조).

(제네릭과 관련된 문제도 발생 했으므로 get-method는 Object를 입력으로 받아 들일 수 있으므로 해시를 담당하는 콜백 인터페이스는 instanceof-check를 추가로 수행해야합니다.

Answer 6

이것은 흥미로운 아이디어이지만 성능면에서 끔찍한 점입니다. 그 이유는 idea of a hashtable에서 매우 기본입니다. 주문은 신뢰할 수 없습니다. Hashtables는 매우 빠릅니다 (constant time). 테이블의 요소를 인덱싱하는 방식 때문에 해당 요소에 대해 의사 고유의 정수 해시를 계산하고 배열에서 해당 위치에 액세스합니다. 말 그대로 메모리의 위치를 ​​계산하고 요소를 직접 저장합니다.

균형 이진 검색 트리 (TreeMap)와는 대조적으로 루트에서 시작하여 조회가 필요할 때마다 원하는 노드로 이동해야합니다. 위키피디아에는 more in-depth analysis이 있습니다. 요약하면 트리 맵의 효율성은 일관된 순서에 따라 달라 지므로 요소의 순서는 예측 가능하고 정상적입니다. 그러나 "목적지로 이동"방식으로 인해 성능이 저하되므로 BST는 O (log (n)) 성능 만 제공 할 수 있습니다. 큰지도의 경우 이는 상당한 성능 저하 일 수 있습니다.

해시 테이블에 일관된 순서를 지정할 수도 있지만 LinkedHashMap과 유사한 기술을 사용하고 순서를 수동으로 유지해야합니다. 또는 해시 테이블과 트리의 두 가지 개별 데이터 구조를 내부적으로 유지 관리 할 수 ​​있습니다. 나무는 조회에 사용할 수있는 반면 트리는 반복에 사용할 수 있습니다. 문제는 필요한 메모리를 두 배 이상 사용한다는 것입니다. 또한 삽입은 트리만큼 빠릅니다 : O (log (n)). 동시 트릭을 사용하면 성능이 약간 떨어질 수 있지만 신뢰할 수있는 성능 최적화는 아닙니다.

간단히 말해서 은 실제로이라고 말하지만 실제로 구현하려고 시도하면 엄청난 성능 제한이 따르는 것을 알 수 있습니다. 최종 평결은 (그리고 수십 년 동안) : 성능이 필요하면 해시 테이블을 사용하십시오. 주문이 필요하고 성능이 저하 될 수있는 경우 균형 이진 검색 트리를 사용하십시오. 두 가지 구조를 효율적으로 조합하는 것이 실제로 어떤 것이 든 하나의 보장을 잃지 않고 두려워합니다.

Answer 7

com.google.common.collect.CustomConcurrentHashMap에는 이러한 기능이 있습니다. 현재 Equivalence (Hasharator)을 설정하는 방법은 공개되어 있지 않습니다.어쩌면 그들은 그것으로 아직 끝나지 않았을 것입니다, 아마 그들은 그 기능이 충분히 유용하다고 생각하지 않습니다. guava mailing list에 문의하십시오.

2 년 전이 talk에서 언급했듯이 왜 아직 일어나지 않았는지 궁금합니다.

Answer 8

비트 당신을 위해 늦었지만 미래 방문자를 위해, 그것은 평민 - 컬렉션은 AbstractHashedMap (4.0에서 3.2.1과와 제네릭)가 있는지 알고 가치가있을 수도 있습니다. 당신은 당신의 원하는 동작을 달성하기 위해 이러한 보호 방법을 재정의 할 수의

protected int hash(Object key) { ... } 
protected boolean isEqualKey(Object key1, Object key2) { ... } 
protected boolean isEqualValue(Object value1, Object value2) { ... } 
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... } 

예 구현 등의 대안 HashedMap입니다 평민 - 컬렉션 '자신의 IdentityMap (Java와 같은에만 최대 3.2.1 1.4 이후 its own있다).

Map 인스턴스에 외부 "Hasharator"을 제공하는 것만 큼 강력하지는 않습니다. 모든 해싱 전략 (구성 vs. 상속 등)에 대해 새로운지도 클래스를 구현해야합니다. 그러나 여전히 잘 알고 있습니다.

Answer 9

HashingStrategy 당신이 찾고있는 개념입니다. 이 인터페이스는 equals 및 hashcode의 사용자 정의 구현을 정의 할 수있는 전략 인터페이스입니다.

public interface HashingStrategy<E> 
{ 
    int computeHashCode(E object); 
    boolean equals(E object1, E object2); 
} 

당신은 HashSet 또는 HashMap 내장과 HashingStrategy을 사용할 수 없습니다. GS Collections은 UnifiedSetWithHashingStrategy이라는 java.util.Set과 UnifiedMapWithHashingStrategy이라는 java.util.Map을 포함합니다.

예를 살펴 보겠습니다. 당신이 UnifiedSetWithHashingStrategy을 설정하고 사용할 수있는 방법은 다음과

public class Data 
{ 
    private final int id; 

    public Data(int id) 
    { 
     this.id = id; 
    } 

    public int getId() 
    { 
     return id; 
    } 

    // No equals or hashcode 
} 

입니다.

java.util.Set<Data> set = 
    new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId)); 
Assert.assertTrue(set.add(new Data(1))); 

// contains returns true even without hashcode and equals 
Assert.assertTrue(set.contains(new Data(1))); 

// Second call to add() doesn't do anything and returns false 
Assert.assertFalse(set.add(new Data(1))); 

Map을 사용하지 않는 이유는 무엇입니까? UnifiedSetWithHashingStrategy은 UnifiedMap의 절반의 메모리를 사용하고 1/4의 메모리는 HashMap의 메모리를 사용합니다. 그리고 때로는 편리한 키가 없으며 튜플과 같은 합성 키를 만들어야합니다. 그것은 더 많은 메모리를 낭비 할 수 있습니다.

어떻게 조회를 수행합니까? 세트는 이지만, get()은 아님을 기억하십시오. UnifiedSetWithHashingStrategy은 Set 외에 Pool을 구현하므로 get()의 양식도 구현합니다.

다음은 대소 문자를 구분하지 않는 간단한 문자열 처리 방법입니다.

UnifiedSetWithHashingStrategy<String> set = 
    new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase)); 
set.add("ABC"); 
Assert.assertTrue(set.contains("ABC")); 
Assert.assertTrue(set.contains("abc")); 
Assert.assertFalse(set.contains("def")); 
Assert.assertEquals("ABC", set.get("aBc")); 

이것은 API에서 벗어나지 만 제작에는 적합하지 않습니다. 문제는 HashingStrategy가 가비지 문자열을 많이 생성하는 String.toLowerCase()에 지속적으로 위임한다는 것입니다. 다음은 대소 문자를 구별하지 않는 문자열을위한 효율적인 해싱 전략을 만드는 방법입니다.

public static final HashingStrategy<String> CASE_INSENSITIVE = 
    new HashingStrategy<String>() 
    { 
    @Override 
    public int computeHashCode(String string) 
    { 
     int hashCode = 0; 
     for (int i = 0; i < string.length(); i++) 
     { 
     hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i)); 
     } 
     return hashCode; 
    } 

    @Override 
    public boolean equals(String string1, String string2) 
    { 
     return string1.equalsIgnoreCase(string2); 
    } 
    }; 

참고 : 나는 GS 컬렉션의 개발자입니다.