java HashMap key swap во время get()

Question

В случае использования у меня есть HashMap, который содержит 1 запись, а ключ - A. Мне нужно многократно вызывать get() с ключом B. A равно() в B, но A и B не являются одним и тем же объектом. Ключ содержит длинный массив, поэтому его equals() стоит дорого. Я пытаюсь улучшить производительность для этой операции проверки карты. Я знаю, что есть подходящие способы решения проблемы производительности. Тем не менее, я рассматриваю взлом, который является наиболее целесообразным.

Следующая от HashMap.java:

public V get(Object key) { 
     if (key == null) 
      return getForNullKey(); 
     int hash = hash(key.hashCode()); 
     for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
      e != null; 
      e = e.next) { 
      Object k; 
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
       return e.value; 
     } 
     return null; 
    } 

если я изменить, если блок в цикл для:

 if (e.hash == hash) { 
      if (e.key == key) { 
       return e.value; 
      } else if (e.key.equals(key)) { 
       e.key = (K) key; 
       return e.value; 
      } 
     } 

Я думаю, что это поможет ПРЕДСТАВЛЕНИЕМ много. В первый раз, когда я вызываю get() с ключом B, будет вызываться equals() B. В остальное время B будет == к ключу на карте, таким образом, сохраняет вызов equals().

Однако нельзя просто расширить HashMap и переопределить get(), так как HashMap.field защищен пакетом и Entry.key является окончательным.

Вопросы:

1. Будет ли эта схема работы?

2. Копирование HashMap.java и связанного с ним кода только для изменения одного метода не очень привлекательно. Каков наилучший способ реализации этого взлома?

Спасибо!

Answer 1

1. Да, это должно работать, если equals выполнено правильно (симметрично).

Попытка взломать equals метод в классе ключей вашей карты:

equals(Object obj) { 
    if (this == obj) return true; 
    if (obj == null) return false; 
    if (!(obj instanceof MyClass)) return false; 
    MyClass other = (MyClass) obj; 
    if (this.longArray == other.longArray) return true; 
    if (Arrays.equals(this.longArray, other.longArray)) { 
     this.longArray = other.longArray; 
     return true; 
    } 
    return false; 
} 

Поскольку ваш класс неизменен, этот трюк должен быть безопасным. Вы должны сделать longArray поле вне финала, но это не повредит производительности, я обещаю.

Answer 2

Это ужасная идея. Вы изменяете ключ входа под обложками.

Решение состоит в том, чтобы создать собственное внутреннее «значение хеш-идентификатора», то, что вы можете рассчитать и гарантировать, уникально для каждого значения. Затем используйте это как прокси для дорогого сравнения в вашем методе equals().

Например (псевдо-Java):

class ExpensiveEquals 
{ 
    private class InxpensiveEqualsIdentity 
    { 
     ... 
     public InexpensiveEqualsIdentity(ExpensiveEquals obj) { ... } 
     public boolean equals() { an inexpensive comparison } 
    } 
    private InxpensiveEqualsIdentity identity; 
    public ExpensiveEquals(...) 
    { 
     ... fill in the object 
     this.identity = new InexpensiveEqualsIdentity(this); 
    } 
    public int hashCode() { return this.identity.hashCode(); } 
    public boolean equals(Object o) 
    { 
     if (this == o) return true; 
     if (o == null || !o instanceof this.getClass()) return false; 
     return (this.identity.equals(((ExpensiveEquals)o).identity)); 
    } 
} 

Answer 3

Если B ключ вы действительно заинтересованы в том, что вы можете просто выполнить обмен с внешней стороны.

V val = map.remove(b); 
map.put(b, val); 

С этого опорного равенства достаточно для B, но вы не возиться с внутренним механизмом.

Answer 4

Моей простая ленивая идея построены на вершине @ Джим Гаррисон отвечает:

private long hash0, hash1; 

void initHash() { 
    // Compute a hash using md5 and store it in hash0 and hash1 
    // The collision probability for two objects is 2**-128, i.e., very small, 
    // and grows with the square of the number of objects. 
    // Use SHA-1 if you're scared. 
} 

void assureHash() { 
    if (hash0 == 0 && hash1 == 0) initHash(); 
} 


public int hashCode() { 
    // If both hashes are zero, assume it wasn't computed yet. 
    assureHash(); 
    return (int) hash0; 
} 

public boolean equals(Object o) { 
    if (this == o) return true; 
    if (!(o instanceof ExpensiveEquals)) return false; 
    ExpensiveEquals that = (ExpensiveEquals) o; 
    this.assureHash(); 
    that.assureHash(); 
    return this.hash0 == that.hash0 && this.hash1 == that.hash1; 
} 

Это гарантирует, что все равно заклинания, но первый будет довольно дешево. Изменения, которые две случайно выбранные пары длин равны, пренебрежимо малы, даже если принять на себя тысячи объектов и учитывать парадокс дня рождения. С помощью криптографической хеш-функции числа столь же хороши, как и случайные.

Если md5 и два long s недостаточно хороши, используйте SHA-1 и еще один int (вот что такое git).