Почему у String.hashcode() столько конфликтов?
Я читаю String.hashCode() в jdk1.6, ниже приведены коды
public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
Это выглядит довольно запутанным для меня, потому что у него так много конфликтов; хотя не обязательно быть уникальным (мы все еще можем полагаться на equals()), но меньше конфликтов означает лучшую производительность, не посещая записи в связанном списке.
Предположим, что у нас есть два символа, тогда, пока мы можем найти две строки, соответствующие ниже уравнения, тогда у нас будет тот же hashcode()
a * 31 +b = c * 31 +d
Нетрудно заключить, что (a-c) * 31 = d-b
взять простой пример: a-c = 1 и d-b = 31;
поэтому я написал ниже коды для простого теста
public void testHash() {
System.out.println("A:" + (int)'A');
System.out.println("B:" + (int)'B');
System.out.println("a:" + (int)'a');
System.out.println("Aa".hashCode() + "," + "BB".hashCode());
System.out.println("Ba".hashCode() + "," + "CB".hashCode());
System.out.println("Ca".hashCode() + "," + "DB".hashCode());
System.out.println("Da".hashCode() + "," + "EB".hashCode());
}
он будет печатать ниже результатов, что означает, что все строки имеют одинаковый хэш-код(), и это легко сделать в цикле.
A:65
B:66
a:97
2112,2112
2143,2143
2174,2174
2205,2205
еще хуже, предположим, что у нас есть 4 символа в строке, согласно алгоритму, предположим, что первые 2 символа производят a2, 2-й символ - b2;
хэш-код будет a2 * 31^2 + b2
таким образом, с a2 и b2, равными между двумя строками, мы получим больше строк с конфликтом hashcode().
такими примерами являются "AaAa", "BBBB" и т.д.;
то у нас будет 6 символов, 8 символов......
Предположим, что большую часть времени мы используем символы в таблице ascii в строке, которая будет использоваться в хэш-карте или хэш-таблице, тогда выбранное простое число 31 здесь, безусловно, слишком мало,
одним простым решением является использование большего простого числа (к счастью, 257 - простое число), которое может избежать этого конфликта. конечно, выберете слишком большой номер, потому что возвращаемое значение int будет переполнено, если строка очень длинная, но я предполагаю большую часть времени, когда строка, используемая в качестве ключа, не такая большая? конечно, он все равно может вернуть длинное значение, чтобы избежать этого.
ниже - моя модифицированная версия besthash(), которая легко разрешает такие конфликты запустив коды, он будет печатать ниже значений, которые эффективны для решения этой проблемы.
16802,17028
17059,17285
17316,17542
17573,17799
но почему jdk не исправляет его? спасибо.
@Test
public void testBetterhash() {
System.out.println(betterHash("Aa") + "," + betterHash("BB"));
System.out.println(betterHash("Ba") + "," + betterHash("CB"));
System.out.println(betterHash("Ca") + "," + betterHash("DB"));
System.out.println(betterHash("Da") + "," + betterHash("EB"));
}
public static int betterHash(String s) {
int h = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
h = 257*h + s.charAt(i);
}
return h;
}
