Краткий ответ:
Вы не можете моделировать использование идентификаторов объектов в качестве ключей dict, используя случайные целые числа в качестве ключей dict.У них разные хеш-функции.
Столкновения случаются.«Наличие уникальных штуковин означает отсутствие столкновений» неправильно для нескольких значений «штуковин».
Вам не следует беспокоиться о столкновениях.
Длинный ответ:
Некоторые пояснения, полученные из чтения исходного кода :
Диктовка реализована в виде таблицы из 2 ** i записей, где i - целое число.
диктов не более 2/3.Следовательно, для 15000 ключей i должно быть 15, а 2 ** i - 32768.
Когда o - произвольный экземпляр класса, который не определяет __hash__(), , это НЕ верно, что хеш(o) == id (o) .Поскольку адрес, вероятно, будет иметь нули в младших 3 или 4 битах, хеш создается путем поворота адреса вправо на 4 бита;см. исходный файл Objects / object.c , функция _Py_HashPointer
Было бы проблемой, если бы было много нулей в младших разрядах, потому что для доступа к таблицеразмер 2 ** i (например, 32768), хеш-значение (часто намного больше этого) должно быть сокращено, чтобы соответствовать, и это делается очень просто и быстро, беря младший бит i (например, 15) битового значения.
Следовательно, столкновения неизбежны .
Однако это не повод для паники.Остальные биты значения хэша учитываются при расчете того, где будет следующий зонд.Вероятность необходимости 3-го зонда и т. Д. Должна быть довольно малой, тем более что полнота никогда не бывает более 2/3 полной.Стоимость нескольких зондов снижается за счет дешевой стоимости расчета слота для первого и последующих зондов.
Приведенный ниже код представляет собой простой эксперимент, иллюстрирующий большую часть вышеприведенного обсуждения.Это предполагает случайный доступ к dict после того, как он достиг своего максимального размера.В Python2.7.1 он показывает около 2000 коллизий для 15000 объектов (13,3%).
В любом случае, суть в том, что вы действительно должны отвлечь свое внимание в другом месте.Столкновения не являются вашей проблемой, если вы не достигли какого-то чрезвычайно ненормального способа получить память для ваших объектов.Вы должны посмотреть, как вы используете диктовку, например, использовать k in d или попробовать / исключить, а не d.has_key(k).Рассмотрим один диктовку, к которой обращаются d[(x, y)] вместо двух уровней, к которым обращаются d[x][y]Если вам нужна помощь в этом, задайте отдельный вопрос.
Обновление после тестирования на Python 2.6:
Поворот адреса не был введен до Python 2.7;см. этот отчет об ошибках для всестороннего обсуждения и тестов производительности.Основные выводы ИМХО по-прежнему действительны и могут быть дополнены "Обновить, если можете".
>>> n = 15000
>>> i = 0
>>> while 2 ** i / 1.5 < n:
... i += 1
...
>>> print i, 2 ** i, int(2 ** i / 1.5)
15 32768 21845
>>> probe_mask = 2 ** i - 1
>>> print hex(probe_mask)
0x7fff
>>> class Foo(object):
... pass
...
>>> olist = [Foo() for j in xrange(n)]
>>> hashes = [hash(o) for o in olist]
>>> print len(set(hashes))
15000
>>> probes = [h & probe_mask for h in hashes]
>>> print len(set(probes))
12997
>>>