Задать вопрос
@up7
java

Как узнать сложность (количество переходов) в поиске по хэш таблице?

Подскажите, пожалуйста, как посчитать сложность поиска каждого из значений в заполннной хэш таблице (количество “переходов”)?

Вот метод поиска. Сам алгоритм работает, но всегда выводит chet ноль или единицу ( Подскажите, где ошибка?

public int get(String key) 
    {
        int chet=0;
        int hash1 = myhash1( key );
        int hash2 = myhash2( key );
 
        while (table[hash1] != null && !table[hash1].key.equals(key))
        {
            chet++;
            hash1 += hash2;
            hash1 %= TABLE_SIZE;
        }
        System.out.println(chet);
        return table[hash1].value;
    }
  • Вопрос задан
  • 348 просмотров
2 комментария
Подписаться 1 Простой 2 комментария
Пригласить эксперта
Ответы на вопрос 3
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
А почему вы решили, что должно быть больше переходов? Прогоните программу пошагово в отладчике, посмотрите как и что происходит.
Ответ написан
6 комментариев
6 комментариев
Therapyx
@Therapyx
Data Science
Написать свою хеш таблицу, в ручную и на каждую функцию ->next() считать каунтер))
По идее, если память не изменяет просто так взять и посчитать сложность хешпоиска в STL нельзя, разве что его править(но могу конечно и ошибаться). Ибо учил все это в плюсах.
В Хештаблице неизвестное кол во коллизий.
К примеру представь телефонный справочник
Хешсимвол А - связь с Артём -> next() -> Алекс -> next() -> Аня....
Хешсимвол Б - связь с Билл-> next() -> Боря - next() -> Бронислав....
Артем знает Алекса, но Артем не нает Аню
Билл знает Борю, но Билл не знает Бронислава
Таким принципом идет связь между елементами связанными с "хешем". Поэтому чтобы посчитать конечную инстанцию. Надо пройтись по всему связанному списку и постчитать его позицию в данном "на этот момент" состоянии твоей таблицы. После каждого измениня в хеше - оно может измениться.

п.с. если же есть такие "уникальные" функции в жаве, то интересно будет почитать тоже. Но сомниваюсь... ))
Ответ написан
Комментировать
Комментировать
@MaxLich
java developer
В идеальном случае - О(1), в худшем - О(n). В чём проблема?
Ответ написан
Комментировать
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
Lead Java
Bell Integrator • Ульяновск
До 400 000 ₽
Lead Java
Bell Integrator • Хабаровск
До 400 000 ₽
Lead Java
Bell Integrator • Ижевск
До 400 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
[python,go] Залить ВИДЕО в тикток
19 апр. 2024, в 23:00
5000 руб./за проект
Разработка VST-плагина
19 апр. 2024, в 20:43
20000 руб./за проект
Нарисовать баннер для интернет-магазина
19 апр. 2024, в 20:35
500 руб./в час
Ещё заказы