Получить индекс элемента массива java с hashCode

Question

У меня есть массив строк, который содержит много слов.Я хочу получить индекс слова, содержащегося в массиве (-1, если он не содержится).

Сначала я сделал цикл для поиска по всем элементам массива при увеличении переменной и когда янайти его, я возвращаю значение переменной.

Однако массив может быть очень очень очень большим, поэтому поиск по всем элементам очень медленный.Я решил, что перед добавлением нового слова в мой строковый массив я бы использовал hashCode() % arrayLength, чтобы получить индекс того, куда я должен его поместить.Затем, чтобы вернуть индекс, я бы просто использовал hashCode() % arrayLength, чтобы сразу узнать, по какому индексу это происходит.

Проблема в том, что иногда возникают "конфликты", и два элемента могут иметь одинаковый индекс в массиве.

У кого-нибудь есть идеи, как с этим бороться?Или любые другие альтернативы, чтобы получить индекс элемента быстрее?

Answer 1

Техника, на которую вы ссылаетесь, является одной из реализаций хеш-таблиц в целом.Это называется линейным зондированием, которое является формой общей техники, называемой открытой адресацией.Если вы вычислили индекс слова на основе hashCode() % array.length и обнаружили конфликт (непустой элемент или не тот элемент, который вы ищете);тогда у вас есть три способа разрешения конфликта:

Линейный поиск

Это делается путем увеличения позиции и проверки, если она пуста или содержит искомый элемент.То есть ваша вторая позиция будет (hashCode(input) + 2) % array.length, а затем (hashCode(input) + 3) % array.length и так далее.Проблема этого подхода заключается в том, что ваша производительность вставки или поиска снизится до линейного O (n), если массив близок к полностью заполненному.

Квадратичный поиск

Это всего лишь оптимизация длявыше техника, прыгая в квадрате, если вы найдете столкновение.Итак, ваш второй индекс будет (hashCode(input) + 2*2) % array.length, а затем (hashCode(input) + 3*3) % array.length и т. Д., Что поможет быстрее добраться до нужного места.

Двойное хеширование

Это еще более эффективный подход для обработкиразрешите, введя другую функцию хеширования hashCode2(), которую вы используете в сочетании с первой.В этом случае ваш следующий индекс поиска будет (hashCode(input) + 2*hashCode2(input)) % array.length, а затем (hashCode(input) + 3*hashCode2(input)) % array.length и т. Д.

Чем более случайно распределены ваши переходы, тем выше производительность по сравнению с большими хеш-таблицами

Надеюсь это поможет.

Answer 2

Вы пытаетесь реализовать Открытая адресация с использованием массива.Если это не домашнее задание, в стандартной библиотеке Java уже есть классы для решения проблемы поиска и столкновений.

Возможно, вы захотите использовать HashSet, чтобы проверить, существует ли String.За сценой используется HashMap, который реализует Раздельное объединение в цепочку для разрешения конфликтов.

String[] words = { "a" };
Set<String> set = new HashSet<>(Arrays.asList(words));
return set.contains("My Word") ? 1 : -1;