Хэш-функции Python

Question

Каков хороший способ хэширования иерархии (похожей на файловую структуру) в python?

Я мог бы преобразовать всю иерархию в пунктирную строку, а затем хэшировать ее, но есть ли лучший (или более эффективный) способ сделать это, не возвращаясь все время назад и вперед?

Пример структуры, которую я хотел бы хэшировать:

a -> b1 -> c -> 1 -> d
a -> b2 -> c -> 2 -> d
a -> c -> 1 -> d

Answer 1

Если у вас есть доступ к вашим компонентам иерархии в виде кортежа, просто хешируйте его - кортежи можно хэшировать. Вы не можете получить много выгоды от преобразования в строку с разделителями и из нее, но это только начало.

Если это не поможет, возможно, вы могли бы предоставить больше информации о том, как вы храните информацию об иерархии / пути.

Answer 2

Как вы хотите получить доступ к вашей иерархии?

Если вы всегда будете проверять полный путь, тогда, как и предлагалось, используйте кортеж: например:

>>> d["a","b1","c",1,"d"] = value

Однако, если вы собираетесь делать такие вещи, как "быстро найти все элементы ниже" a -> b1 ", возможно, имеет смысл сохранить его как вложенную хеш-таблицу (в противном случае вы должны выполнить итерацию по всем найдите тех, в ком вы заинтересованы).

Для этого defaultdict - это, вероятно, самый простой способ хранения. Например:

from collections import defaultdict

def new_dict(): return defaultdict(new_dict)
d = defaultdict(new_dict)

d["a"]["b1"]["c"][1]["d"] = "test"
d["a"]["b2"]["c"][2]["d"] = "test2"
d["a"]["c"][1]["d"] = "test3"

print d["a"]["c"][1]["d"]  # Prints test3
print d["a"].keys()        # Prints ["c", "b1", "b2"]

Answer 3

Вы можете сделать любой объект хешируемым, реализовав метод __hash__()

Таким образом, вы можете просто добавить подходящий __hash__() метод к объектам, хранящим вашу иерархию, например вычислять хеш рекурсивно и т. д.