Как реализовать хеш-функцию в Java? - PullRequest
1 голос
/ 20 февраля 2010

Я использовал массив в качестве хеш-таблицы для хеширования алогрита со значениями:

int[] arr={4 , 5 , 64 ,432 };

и ключи с последовательными целыми числами в массиве как:

int keys[]={ 1 , 2 , 3 ,4};

Может ли кто-нибудь сказать мне, что было бы хорошим подходом при сопоставлении этих целых ключей с расположением этих массивов? Является ли следующий короткий и лучший подход с небольшим коллизией или без него (или с более значительными значениями)?

 keys[i] % arrlength  // where i is for different element of an array

Заранее спасибо.

Ответы [ 3 ]

2 голосов
/ 20 февраля 2010

Я предполагаю, что вы пытаетесь реализовать какую-то хеш-таблицу в качестве упражнения. В противном случае вы должны просто использовать java.util.HashMap или java.util.HashTree или подобное.

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

Вы определили, что столкновения нежелательны - это правда. Иногда, некоторые знания о вероятных ключах могут помочь вам разработать хорошую хэш-функцию. Иногда можно предположить, что класс ключей будет иметь хороший метод hash(). Поскольку hash () является методом, определенным Object, каждый класс реализует его. Вам было бы полезно использовать метод hash () вашего ключа, а не создавать новый алгоритм специально для вашей карты.

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

1 голос
/ 20 февраля 2010

Купите себе книгу об алгоритмах и структурах данных и прочитайте главу о хеш-таблицах (статья Википедии также будет хорошей отправной точкой). Это сложная тема, которая выходит за рамки вопросов и ответов, подобных этой.

Для начала, использование размера массива по модулю, как правило, ужасная хеш-функция, потому что это приводит к массивным столкновениям, когда значения кратны размеру массива или одному из его делителей. Насколько это плохо, зависит от размера массива: чем больше делителей, тем больше вероятность возникновения коллизий; когда это простое число, это не так уж плохо (но не очень хорошо).

1 голос
/ 20 февраля 2010

Есть ли причина не использовать встроенную HashMap ? Вы должны будете использовать Integer, а не int.

 java.util.Map myMap = new java.util.HashMap<Integer, Integer>();

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

Этот вопрос StackOverflow содержит интересные ссылки для реализации быстрых хэш-карт (хотя для C ++), как и этот (для Java).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...