Краткое знакомство с [Хэш-алгоритм Classic Times 33], в этой статье мы продолжаем рассказывать о подборе множителей, анализируя алгоритм хеширования класса String Java 1.8.

Исходный код hashCode() класса String

/** Cache the hash code for the string */
private int hash;

/** 
Returns a hash code for this string. The hash code for a String object is computed as 
 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, 
n is the length of the string, and ^ indicates exponentiation. 
(The hash value of the empty string is zero.) 
*/
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;
}

Видно, что хэш-алгоритм String также принимает идею Times 33, но множитель равен 31.

Значение хэша по умолчанию равно 0.
Оценка h == 0 означает кэширование хеш-значения.
Считается, что value.length > 0, потому что хеш-значение пустой строки равно 0.

говорить с данными

В предыдущей статье мы упоминали:

Почему магическое число 33 более эффективно для хеширования, чем многие другие константы (простые или нет), не было адекватно объяснено. Итак, Ральф С. Энгельшалл пытается объяснить, почему, используя свой собственный метод. Проверяя каждое число от 1 до 256,Обнаружено, что эффект хеширования четных чисел очень плохой, и его нельзя использовать согласно. И остальные 128 нечетных чисел, кроме 1, имеют аналогичные эффекты. Все эти нечетные числа хорошо себя зарекомендовали при распределении, заполняя хэш-таблицу с покрытием около 86%.

Судя по хеш-эффекту (Chi^2 должен относиться к распределению хи-квадрат), хотя 33 не обязательно является лучшим значением. ноОчевидное преимущество 17, 31, 33, 63, 127 и 129 перед другими нечетными числами состоит в том, что, поскольку эти нечетные числа отличаются только на 1 от 16, 32, 64 и 128, их можно изменить сдвигом (например, 1 .

Далее давайте проверим утверждение Ральфа С. Энгельшалла с помощью экспериментальных данных, чтобы увидеть эффект хеширования четных, нечетных и магических чисел, таких как 17, 31, 33, 63, 127 и 129.

Подготовка окружающей среды

Персональный ноутбук, операционная система Windows 7, двухъядерный 64-разрядный процессор Core i5.

Тестовые данные: все слова, соответствующие файлу словаря /usr/share/dict/words версии CentOS Linux 7.5.1804.

Поскольку файл словаря не был найден в CentOS, он был установлен через yum -y install words.

/usr/share/dict/words содержит в общей сложности 479828 слов, и исходный файл, связанный с этим файлом, называется linux.words.

Рассчитать частоту столкновений и время хеширования

тестовый код

/**
 * 以1-256为乘数，分别计算/usr/share/dict/words所有单词的哈希冲突率、总耗时.
 * 
 * @throws IOException
 */
@Test
public void testHash() throws IOException {
	List<String> words = getWords();
	
	System.out.println();
	System.out.println("multiplier, conflictSize, conflictRate, timeCost, listSize, minHash, maxHash");
	for (int i = 1; i <=256; i++) {
		computeConflictRate(words, i);
	}
}

/**
 * 读取/usr/share/dict/words所有单词
 * 
 * @return
 * @throws IOException
 */
private List<String> getWords() throws IOException {
	// read file
	InputStream is = HashConflictTester.class.getClassLoader().getResourceAsStream("linux.words");
	List<String> lines = IOUtils.readLines(is, "UTF-8");
	return lines;
}

/**
 * 计算冲突率
 * 
 * @param lines
 */
private void computeConflictRate(List<String> lines, int multiplier) {
	// compute hash
	long startTime = System.currentTimeMillis();
	List<Integer> hashList = computeHashes(lines, multiplier);
	long timeCost = System.currentTimeMillis() - startTime;
	
	// find max and min hash
	Comparator<Integer> comparator = (x,y) -> x > y ? 1 : (x < y ? -1 : 0);
	int maxHash = hashList.parallelStream().max(comparator).get();
	int minHash = hashList.parallelStream().min(comparator).get();
	
	// hash set
	Set<Integer> hashSet = hashList.parallelStream().collect(Collectors.toSet());
	
	int conflictSize = lines.size() - hashSet.size();
	float conflictRate = conflictSize * 1.0f / lines.size();
	System.out.println(String.format("%s, %s, %s, %s, %s, %s, %s", multiplier, conflictSize, conflictRate, timeCost, lines.size(), minHash, maxHash));
}

/**
 * 根据乘数计算hash值
 * 
 * @param lines
 * @param multiplier
 * @return
 */
private List<Integer> computeHashes(List<String> lines, int multiplier) {
	Function<String, Integer> hashFunction = x -> {
		int hash = 0;
		for (int i = 0; i < x.length(); i++) {
			hash = (multiplier * hash) + x.charAt(i);
		}
		return hash;
	};
	return lines.parallelStream().map(hashFunction).collect(Collectors.toList());
}

Выполняем тестовый метод testHash(), через некоторое время получим отчет о тестировании.

Сортировать по частоте столкновений хешей в порядке убывания

Сортируя частоту коллизий хэшей в порядке убывания, получаются следующие результаты.

Анализ результатов

Частота конфликтов с четными номерами в основном высока, лишь за некоторыми исключениями.
Меньший множитель, более высокая частота конфликтов, например, от 1 до 20.
Неравномерное распределение множителей 1, 2, 256. Хэш-значение Java имеет 32-битный тип int и диапазон значений [-2147483648, 2147483647].

Отнимающая много времени сортировка хэшей по убыванию

Затем мы анализируем множители с количеством конфликтов в пределах 1000 и получаем следующие результаты, сортируя время выполнения в порядке убывания.

Анализ 17, 31, 33, 63, 127 и 129

17 выбыло в последнем туре.
63 Расчет занимает много времени.
Коэффициенты конфликтов 31 и 33 составляют 0,13% и 0,14% соответственно, а время выполнения — 10 и 11 соответственно, что в основном одинаково в режиме реального времени..
Коэффициенты конфликтов 127 и 129 составляют 0,01% и 0,004% соответственно, а время выполнения — 9 и 10 соответственно..

В общем, 129 занимает меньше времени на выполнение и имеет наименьшую конфликтность.Кажется, правильнее выбрать его первым?

распределение хэша

Разделите все хеш-пространство [-2147483648, 2147483647] на 128 разделов и подсчитайте количество хэш-значений в каждом разделе, чтобы наблюдать за распределением каждого множителя. Биты ведра хэша на раздел равны 2^32/128 = 33554432.

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

Рассчитать код распределения хэша

@Test
public void testHashDistribution() throws IOException {
	int[] multipliers = {2, 17, 31, 33, 63, 127, 73, 133, 237, 161};
	List<String> words = getWords();
	for (int multiplier : multipliers) {
		List<Integer> hashList = computeHashes(words, multiplier);
		Map<Integer, Integer> hashMap = partition(hashList);
		System.out.println("\n" + multiplier + "\n,count");
		hashMap.forEach((x, y) -> System.out.println(x + "," + y));
	}
}

/**
 * 将整个哈希空间等分成128份，统计每个空间内的哈希值数量
 * 
 * @param hashs
 */
public static Map<Integer, Integer> partition(List<Integer> hashs) {
	// step = 2^32 / 128 = 33554432
	final int step = 33554432;
	List<Integer> nums = new ArrayList<>();
	Map<Integer, Integer> statistics = new LinkedHashMap<>();
	int start = 0;
	for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
		final long min = i;
		final long max = min + step;
		int num = (int) hashs.parallelStream().filter(x -> x >= min && x < max).count();

		statistics.put(start++, num);
		nums.add(num);
	}

	// 为了防止计算出错，这里验证一下
	int hashNum = nums.stream().reduce((x, y) -> x + y).get();
	assert hashNum == hashs.size();

	return statistics;
}

После создания данных сохраните текст как суффикс csv и откройте его в Excel. Затем с помощью функции диаграммы Excel выберите гистограмму, чтобы создать следующую диаграмму.

Множитель 2

Множитель 17

Множитель 31

Множитель 33

Множитель 73

Множитель 127

Множитель 133

Множитель 161

Множитель 237

За исключением 2 и 17, остальные числа в основном распределены равномерно.

Суммировать

Теперь у нас есть общее представление о причинах выбора 31 в качестве хеш-множителя класса Java String.Основные моменты заключаются в следующем.

31 — нечетное простое число.
Распределение хеша относительно равномерное. Частота конфликтов с четными номерами обычно высока, за некоторыми исключениями. Чем меньше множитель, тем выше частота конфликтов, например, от 1 до 20..
Хэш-вычисления выполняются быстро. Вместо умножения можно использовать сдвиги и вычитания. Современные виртуальные машины могут выполнять эту оптимизацию автоматически, например 31 * i = (i .
Скорость вычислений 31 и 33 в основном такая же, как и распределение хэша, а общая производительность хорошая, поэтому их выбор вполне естественен.

Когда в вычислении хэша участвует много элементов, чем больше множитель, тем больше вероятность того, что результат переполнится и информация будет потеряна. Думаю, это одна из причин.

Хотя по результатам теста общая производительность нечетных чисел больше 31 и 33 имеет лучший выбор. Однако 31 и 33 не только хорошо работают в целом, но и 32 имеет наименьшую операцию сдвига.Теоретически скорость вычислений должна быть самой высокой.

В заключение я протестировал и сравнил два других сервера Linux и обнаружил, что результаты в основном одинаковы. Однако вышеуказанные методы испытаний не являются очень строгими, и могут быть отклонения от фактической производственной операции.Результаты приведены только для справки.

Несколько распространенных вариантов реализации

values chosen to initialize h and a for some of the popular implementations

INITIAL_VALUE: начальное значение хеша. Начальное значение хэша строки Java = 0.
a: Множитель хэша. Множитель хеша для Java String равен 31.

Ссылаться на

stackoverflow.com/questions/2…

сегмент fault.com/ah/119000001…

Хорошо. Wikipedia.org/wiki/u_ver…

Действующая версия Java на китайском языке, 2-е издание

Личный публичный аккаунт

Для получения дополнительных статей, пожалуйста, обратите внимание на общедоступный номер: Binary Road