Здравствуйте, IROV.., Вы писали:

IRO>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время
В комментариях к реализации (см. dictnotes) CPython2 есть такой абзац. В CPython3 уже нет. Ну и в коде вообще нет. Возможно проверили и оптимизация не зажгла. Возможно и не проверяли.

IRO>(проверять только на is то есть указатели)
IRO>что я упустил?
Знаешь про ABA?
Проверять указатели можно, но их равенство не говорит об том, что это тот же объект, что и был до этого. Пример:

class Foo: ...
class Bar: ...
assert Foo() != Bar()

u = Foo()
d = {deepcopy(u):1}

if u in d: # словарь d проверил наличие и попутно запомнил указатель (id) ключа u
   idu = id(u)
   del u
   v = Bar()
   idv = id(v)
   assert idu == idv # равенство id не запрещено, если время жизни объектов не пересекается
   print(d[v]) # Грабли: указатель на v и на бывший u совпали, но v не равно u.

То есть даже в случае равенства указателей нужно всё-равно обязательно запускать полное сравнение объектов, и вычислять хеш-функцию.

Ну и в текущей реализации dict в CPython сначала сравниваются указатели на объекты, а не сразу объекты. Но это корректно так как словарь владеет ключами своих объектов и ABA там невозможна. Кеш же владеть объектами не должен (иначе это больше боли принесёт чем пользы), weakref из кеша тоже не всегда возможен (нет же слабых ссылок на int, например).

Так что тут разве что выиграть на времени прохода по корзинам хеш-таблицы можно. Впрочем, в CPython стоит достаточно низкий порог заполнения таблицы, и просматривается обычно не так уж много корзин — и даже среди просматриваемых не для каждой вызывается функция сравнения объектов (так как в хеш-таблице с открытой адресацией часть вторичных коллизий разрешается по сравнению значений хеш-функций, а не самих объектов).

В общем, сделать такую оптимизацию можно. Но вот этот пример с ABA-подобным поведением не даст ей работать эффективно. Но попробовать можно, либо найди кто уже пробовал :)
А так, кажется, что всех уже приучили в таких ситуациях использовать .get(key, None), или .setdefault, или defaultdict, что в общем-то работает не особо плохо. Хотя,согласен, что это всё же не идеально, так как переносит проблему с интерпретатора на программиста.