хеш-функция, обеспечивающая уникальную UINT из пары целочисленных координат - PullRequest
Новая
       21

хеш-функция, обеспечивающая уникальную UINT из пары целочисленных координат

22 голосов
/ 25 марта 2009

Проблема в целом: У меня есть большое 2-х точечное пространство, редко заполненное точками. Думайте об этом как о большом белом холсте, посыпанном черными точками. Мне приходится многократно повторять и искать по этим точкам. Холст (точка пространства) может быть огромным, граничащим с границами из int и его размер неизвестен до установки там точек.

Это привело меня к идее хеширования:

Ideal: Мне нужна хеш-функция, берущая 2D-точку и возвращающая уникальный uint32. Так что никаких столкновений не может произойти. Можно предположить, что число точки на холсте легко подсчитываются с помощью uint32.

ВАЖНО: Невозможно заранее узнать размер холста (это может даже измениться), так что вроде

Ширина холста * у + х

печально не может быть и речи.

Я тоже очень наивно пробовал

абс (х) + абс (у)

но это вызывает слишком много столкновений.

Компромисс: Хеш-функция, которая обеспечивает ключи с очень низкой вероятностью столкновения.

Есть идеи у кого-нибудь? Спасибо за любую помощь.

С уважением, Андреас Т.

Edit: Мне пришлось что-то изменить в тексте вопроса: Я изменил предположение «умеет считать количество точек холста» с помощью uint32 «в» можно посчитать точки на холсте (или количество координатных пар для хранения »с помощью uint32. Мой оригинальный вопрос не имел особого смысла, потому что у меня был бы холст размером sqrt (max (uint32)) xsqrt (max (uint32)), который уникально представлен сдвигом 16 бит и ИЛИ.

Надеюсь, это нормально, поскольку все ответы по-прежнему имеют смысл с обновленными предположениями

Извините за это.

Ответы [ 11 ]

0 голосов
/ 04 ноября 2012

Если вы уже используете языки или платформы, что во всех объектах (даже примитивных, таких как целые числа) реализованы встроенные хэш-функции (языки платформы Java, такие как Java, языки платформы .NET, такие как C #, и другие, такие как Python, Ruby, так далее ). Вы можете использовать встроенные значения хеширования в качестве строительного блока и добавить свой «вкус хэширования» в микс. Как: 

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

public override int GetHashCode() {
   return ( Y.GetHashCode() << 16 ) ^ X.GetHashCode();
}

}

А также наличие тестовых наборов, таких как «предопределенный набор из миллиона точек», работающих с каждым возможным сравнением алгоритма генерации хеша для различных аспектов, таких как: время вычислений, требуемая память, счетчик столкновений ключей и варианты фронтов (слишком большие или слишком малые значения). будь удобен

Страница:
...