Разработка эффективного хэша
У меня есть набор узлов (N), организованных в одну или несколько сетей. Каждая сеть имеет один или несколько корневых узлов. Каждый узел имеет уникальный идентификатор (UID), представляющий собой 32-разрядное целое число. Если бы было 100 000 узлов, это было бы большой проблемой - 1 000 000 было бы почти невозможно гигантским. Мне нужно проверить, все ли узлы подключены хотя бы к одному корневому узлу, и я пытаюсь разработать хэш-функцию, чтобы помочь мне.
Мой текущий код начинается с каждого корневого узла и отслеживает все пути, записывая каждый подключенный узел. Он делает это без хэширования, так как раньше я мог полагаться на то, что жидкости относительно малы и в основном смежны. Наряду с начальным смещением он просто использует UID непосредственно для индексации в растровый массив. Растровое изображение сравнивается с членами N, чтобы определить, какие узлы не соединены.
Теперь, однако, я сталкиваюсь с ситуациями, когда есть большие пробелы в UIDS (например, скачок от 100 000 до 100 000 000) - это делает простое увеличение размера растрового изображения все более и более непрактичным, следовательно, необходимость в хэше. В общем случае, если пользователь не полностью запутался, я бы ожидал, что количество несвязанных узлов будет меньше, чем количество подключенных (но не обязательно).
Как мне, например, выбрать, сколько ведер я должен использовать для хэширования, чтобы сбалансировать использование памяти с вероятностью столкновений? Может ли это (должно ли это?) быть сделано динамически? (т. е. должен ли я динамически выделять свой массив ведер на основе размера N?) Является ли более эффективным начать с хэширования всех моих uid узлов в ведра, а затем очистить "связанные" хэши по мере их обнаружения? Как я могу определить наилучший способ обработки столкновений? Можно ли динамически создать идеальный хэш?
Что я уже пробовал:
Ничего больше, чем гуглить. Я не специалист по компьютерам, так что это немного ново для меня. Я нахожу массу онлайн - информации немного трудной для переваривания-отсюда и обращение к экспертам.