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

Question

[up7]

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

Вот метод поиска. Сам алгоритм работает, но всегда выводит 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;
    }

Comments

[MaxLich]

что такое "chet ноль или единицу"???

[MaxLich]

Хотите написать свою HashMap? Зачем?
Если возникают сложности, можно посмотреть исходный код этого классы и статьи про него, например, эту: хабр, статья про внутренности хэш-мэп

Answer 1

[Rsa97]

А почему вы решили, что должно быть больше переходов? Прогоните программу пошагово в отладчике, посмотрите как и что происходит.

Comments

[up7]

Спасибо за ответ. Тогда число переходов вот в этой функции считать?

private int myhash1(String x )
    { 
        int hashVal = x.hashCode( );
        hashVal %= TABLE_SIZE;
        if (hashVal < 0)
            hashVal += TABLE_SIZE;
        return hashVal;
    }

Сколько раз выполняется? Я уже всю голову сломал, как посчитать сложность поиска в этих чертовых таблицах ((

[Rsa97]

up7, А откуда здесь переходы по таблице? Это же просто вычисление хэша.

[up7]

Rsa97, так больше нет ничего. Функция поиска (get) и функция хэширования. Остальные в поиске не участвуют. А у преподавателя вопрос посчитать сложность поиска каждого из
значений в заполнненой таблице (количество “переходов”).

Таблицу я создал, заполнил ключами и значениями, захешировал, есть метод поиска, но как узнать эту самую сложность? ((

[Rsa97]

up7, Так вы её уже посчитали. Только не доверяете своему же подсчёту. Значит либо пошаговая отладка в IDE, либо на бумажке вручную пошагово повторять алгоритм.

[Денис Загаевский]

up7, ты уверен, что это твой код?

[Stanislav Pugachev]

нормально кто-то на вами подшутил, задавая такое задание :)

Answer 2

[Therapyx]

Написать свою хеш таблицу, в ручную и на каждую функцию ->next() считать каунтер))
По идее, если память не изменяет просто так взять и посчитать сложность хешпоиска в STL нельзя, разве что его править(но могу конечно и ошибаться). Ибо учил все это в плюсах.
В Хештаблице неизвестное кол во коллизий.
К примеру представь телефонный справочник
Хешсимвол А - связь с Артём -> next() -> Алекс -> next() -> Аня....
Хешсимвол Б - связь с Билл-> next() -> Боря - next() -> Бронислав....
Артем знает Алекса, но Артем не нает Аню
Билл знает Борю, но Билл не знает Бронислава
Таким принципом идет связь между елементами связанными с "хешем". Поэтому чтобы посчитать конечную инстанцию. Надо пройтись по всему связанному списку и постчитать его позицию в данном "на этот момент" состоянии твоей таблицы. После каждого измениня в хеше - оно может измениться.

п.с. если же есть такие "уникальные" функции в жаве, то интересно будет почитать тоже. Но сомниваюсь... ))

Answer 3

[MaxLich]

В идеальном случае - О(1), в худшем - О(n). В чём проблема?