Деревья поиска определенно не могут обрабатывать два узла с одним и тем же ключом, поэтому вам нужно хранить записи со встречными ключами в отдельной структуре данных (обычно, как вы говорите, связанный список, прикрепленный к узлу дерева).У вас действительно не будет сложности O в худшем случае O (log n), так же как ассоциативный массив, реализованный в виде хеш-таблицы, не будет иметь операций O (1) в худшем случае.
Как отмечает Эпитафия, одинпопробуйте увеличить длину ваших хеш-ключей, чтобы не возникало коллизий.Однако вы не можете гарантировать, что этого не сделаете, и вам нужно сделать какое-то условие для двух объектов с одинаковым хешем.Однако, если вы правильно выберете алгоритм хеширования, это должно быть редким случаем, и ваша средняя сложность времени для поисков будет O (log n), даже если он может ухудшиться до O (n) ввырожденный случай, когда все имеет одинаковый хэш-ключ.