Основная структура хеш-данных Python для словарей

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

Python использует структуру хеш-данных для хранения словарей (не путать с криптографической хеш-функцией). Поиск выполняется за O (1), но если хеш-таблица заполнена, ее нужно перехешировать, что очень дорого.

Мой вопрос: лучше ли мне использовать двоичное дерево поиска AVL или достаточно ли хеш-таблицы?