Описание тега perfect-hash

Вопросы с тегом
A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.
8 ответов

Самый быстрый поиск строковых ключей для известного набора ключей

Рассмотрим функцию поиска со следующей сигнатурой, которая должна возвращать целое число для данного строкового ключа: int GetValue(string key) { ... } Кроме того, учтите, что сопоставления значения ключа, нумерация N, известны заранее, когда пишетс…
16 июл '11 в 01:41
2 ответа

Идеальное хеширование для OpenCL

У меня есть набор (статический, известный во время компиляции) около 2 миллионов значений по 20 байтов каждое. Мне нужен быстрый O(1) способ проверить, находится ли заданное значение в этом наборе. Кажется, что идеальная хеш-функция с битовым массив…
24 июн '12 в 11:13
2 ответа

Минимальная идеальная хеш-функция

У меня есть много целых чисел в диапазоне [0; 2^63-1]. Однако есть только 10^8 целых чисел. Там нет дубликатов. Полный список известен во время компиляции, но это просто уникальные случайные числа. Эти цифры никогда не меняются.Чтобы хранить одно це…
19 июл '11 в 06:55
1 ответ

Создать минимальный идеальный хеш для разреженного 64-битного целого числа без знака

Мне нужна идеальная хеш-функция от 64 до 16 бит для малонаселенного списка ключей. У меня есть словарь в Python, который имеет 48326 ключей длиной 64 бита. Я хотел бы создать минимальный идеальный хэш для этого списка ключей. (Я не хочу ждать нескол…
26 май '18 в 12:41
4 ответа

Являются ли EnumMaps в Java идеальными хэш-картами?

Если список ключей хеш-функции для хэш-функции известен и неизменен, можно создать идеальную хэш-функцию. Enum в Java - это список известных и неизменных элементов. Поэтому должна быть возможность реализовать EnumMap как идеальный хеш. Это в настоящ…
07 июн '13 в 09:06
1 ответ

Идеальная хеш-функция для большого набора целых чисел [1..2^64 - 1]

Мне нужно построить идеальную хеш-функцию, которая отображает набор целых чисел [1..2^64 - 1] на себя (эта функция на самом деле является некоторой сложной перестановкой). Чтобы объяснить эту проблему, предположим, что у нас есть последовательность …
26 май '17 в 11:28
1 ответ

Что такое большой O идеальной хэш-функции?

Обычные хеш-функции, в которых возможны коллизии, выполняются за постоянное время: O(1). Но какова временная сложность идеальной хеш-функции? Это 1?
21 дек '18 в 19:18
3 ответа

Поиск по хеш-таблице - с идеальным хешем, в C

У меня есть приложение на языке C, где мне нужно искать таблицы. Записи являются строками. Все они известны в начале выполнения. Таблица инициализируется один раз, а затем просматривается много раз. Таблица может измениться, но это в основном так, к…
07 сен '11 в 03:38
1 ответ

Существует ли идеальная хэш-функция для комбинированных входных наборов номеров IMEI и MAC-адресов? (C реализация)

Я ищу хэш-функцию, которую я могу использовать, чтобы назначать унифицированные уникальные идентификаторы устройствам, которые подключаются к нашей сети с помощью модема GSM или Ethernet-соединения. Таким образом, для любого данного устройства у мен…
16 авг '11 в 15:32
1 ответ

Идеальный генератор хеш-функций для функций

У меня есть набор функций C++. Я хочу отобразить эти функции в хэш-таблице, что-то вроде: unordered_map<function<ReturnType (Args...)> , SomethingElse>, где SomethingElse не имеет отношения к этому вопросу. Этот набор функций ранее извес…
18 апр '16 в 04:28
1 ответ

Инъективные двусторонние отображения

Я часто имею дело с отображениями, которые являются инъективными. В терминологии программирования это можно выразить в виде словаря, в котором все значения являются уникальными, а также, конечно, все ключи. Существует ли структура данных с эффективн…
29 янв '18 в 01:15
8 ответов

Есть ли способ сделать этот поиск быстрее?

У меня есть требование (очень) быстро обрабатывать строки ограниченного диапазона, подсчитывая их значения. Входной файл имеет форму: January 7 March 22 September 87 March 36 и так далее. Поскольку ширина линий одинакова, я могу просто прочитать в с…
06 авг '10 в 07:45
3 ответа

Идеальный хэш в Scala

У меня есть класс C: class C (...) { ... } Я хочу использовать его для индексации эффективной карты. Самая эффективная карта - Массив. Поэтому я добавляю "глобальный" "статический" счетчик в объект-компаньон, чтобы дать каждому объекту уникальный ид…
09 май '10 в 09:28
0 ответов

Как я могу превратить мои четыре идеальных базовых метода псевдокода в работающий код?

Я пытаюсь выяснить, как я могу превратить мои 4 основных метода псевдокода в моем идеальном хэш-классе в работающие методы, которые в конечном итоге будут использоваться внутри основного метода моего PerfectHash учебный класс. Я знаю, что еще не соз…
02 ноя '17 в 01:00
3 ответа

Определение идеальной таблицы поиска хеша для Pearson Hash

Я разрабатываю язык программирования, и на своем языке программирования я храню объекты в виде хеш-таблиц. Я использую хэш-функцию Pearson Hashing, которая зависит от 256-битной таблицы поиска. Вот функция: char* pearson(char* name, char* lookup) { …
08 сен '09 в 22:37
3 ответа

Идеальный минимальный хэш для математических комбинаций

Сначала определите два целых числа N а также K, где N >= K, оба известны во время компиляции. Например: N = 8 а также K = 3, Затем определите набор целых чисел [0, N) (или же [1, N] если это упрощает ответ) и назовите его S, Например: {0, 1, 2, 3…
04 янв '13 в 16:27
3 ответа

Как сгенерировать уникальный идентификатор для структуры адреса?

У меня есть структура, которая описывает адрес, он выглядит так: class Address { public string AddressLine1 { get; set; } public string AddressLine2 { get; set; } public string City { get; set; } public string Zip { get; set; } public string Country…
07 апр '13 в 11:51
1 ответ

Создание хэш-таблицы и идеальной хэш-функции в JavaScript

Я работаю с Google Maps API и чувствую, что есть лучший способ поиска по панорамным изображениям, кроме огромного switch заявление. Я думаю, что использование внешней хеш-таблицы будет гораздо более эффективным и намного проще в обслуживании. Каждое…
20 фев '13 в 18:45
1 ответ

Использование CMPH в VC++

Я хотел бы использовать минимальный идеальный хэш из CMPH. Любая идея, как я могу использовать его в проекте VC++? Я создал новый проект с использованием VC++ 2008 Express Edition здесь и добавил заголовок и исходные файлы, но он выдает ошибки компи…
08 окт '10 в 03:10
1 ответ

Как лучше реализовать идеальную хеш-функцию для приложения для iOS?

Мне нужно создать идеальный хеш для списка строковых идентификаторов, поэтому прежде чем начать с этой реализацией (я никогда раньше этого не делал), я хочу знать, есть ли какая-нибудь хорошая структура или хороший учебник, который может быть полезе…
26 мар '12 в 16:27