Подсчет коллизий в словаре Python

Ответ 1

Короткий ответ:

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

Столкновения происходят. "Наличие уникальных штучек означает отсутствие столкновений" неверно для нескольких значений "thingy".

Вы не должны беспокоиться о столкновениях.

Длинный ответ:

Некоторые объяснения, полученные из чтение исходного кода:

A dict реализуется как таблица из 2 ** я записей, где я - целое число.

dicts не превышает 2/3. Следовательно, для 15000 ключей я должен быть 15 и 2 ** я - 32768.

Если o - произвольный экземпляр класса, который не определяет __hash__(), это НЕ верно, что hash (o) == id (o). Поскольку адрес, вероятно, имеет нули в младших 3 или 4 битах, хэш создается путем поворота адреса на 4 бита; см. исходный файл Objects/object.c, function _Py_HashPointer

Было бы проблемой, если бы было много нулей в младших битах, потому что для доступа к таблице размера 2 ** я (например, 32768) хеш-значение (часто намного больше) должно быть хрустело чтобы соответствовать, и это делается очень просто и быстро, взяв младший бит я (например, 15) хэш-значения.

Следовательно, столкновения неизбежны.

Однако это не вызывает паники. Остальные биты хэш-значения учитываются при расчете того, где будет следующий пробник. Вероятность необходимости 3-го и т.д. Зонда должна быть довольно небольшой, тем более, что дикты не превышают 2/3. Стоимость нескольких зондов снижается за счет дешевой стоимости расчета слота для первого и последующих зондов.

Ниже приведен простой пример, иллюстрирующий большую часть приведенного выше обсуждения. Он предполагает случайный доступ к dict после того, как он достиг своего максимального размера. С Python2.7.1 он показывает около 2000 столкновений для 15000 объектов (13.3%).

В любом случае суть в том, что вы должны действительно отвлечь свое внимание в другом месте. Коллизии не являются вашей проблемой, если вы не достигли чрезвычайно необычного способа получения памяти для своих объектов. Вы должны посмотреть, как вы используете дикты, например. используйте k in d или try/except, а не d.has_key(k). Рассмотрим, что один диск получил доступ как d[(x, y)] вместо двух уровней, доступных как d[x][y]. Если вам нужна помощь, задайте отдельный вопрос.

Обновить после тестирования на Python 2.6:

Вращение адреса не было введено до Python 2.7; см. этот отчет об ошибках для всестороннего обсуждения и тестов. Основные выводы IMHO по-прежнему действительны и могут быть дополнены "Обновить, если вы можете".

>>> 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
>>>

Ответ 2

Эта идея на самом деле не работает, см. обсуждение в вопросе.

Быстрый просмотр реализации C на python показывает, что код для разрешения конфликтов не вычисляет или не сохраняет количество столкновений.

Однако он будет вызывать PyObject_RichCompareBool на клавишах, чтобы проверить, совпадают ли они. Это означает, что __eq__ на ключе будет вызываться для каждого столкновения.

Итак:

Замените свои ключи объектами, которые определяют __eq__ и увеличивают счетчик при его вызове. Это будет медленнее из-за накладных расходов, связанных с переходом на python для сравнения. Однако это должно дать вам представление о том, сколько коллизий происходит.

Убедитесь, что в качестве ключа используются разные объекты, иначе python будет использовать ярлык, потому что объект всегда равен самому себе. Кроме того, убедитесь, что хэш объектов имеет то же значение, что и исходные ключи.

Ответ 3

Если ваши ключи гарантированно являются уникальными целыми числами, а так как Python использует hash() на клавишах, то вам не должно быть никаких коллизий.