Форум на Исходниках.RU

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

Dushevny — Thu, 25 Apr 2019 06:22:50 +0000

Dushevny:

Цитата OpenGL @ 25.04.19, 04:33

что любой байт содержит 8 бит

Не любой. Но автору темы экзотические архитектуры с размером байта, не равным 8 битам, скорее всего, не встретятся.

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

OpenGL — Thu, 25 Apr 2019 04:33:00 +0000

OpenGL:

Цитата FasterHarder @ 24.04.19, 14:52

Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!

Ты в курсе, что любой байт содержит 8 бит и что в "чистом" С89 существуют битовые операции? :D

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Wed, 24 Apr 2019 18:39:28 +0000

FasterHarder:

Цитата Qraizer @ 24.04.19, 16:48

В Плюсах есть std::bitset<> и std::vector. Тебе какой?

ага, с битсетом знаком, даже когда-то вроде где-то юзал, но прожка текущая на сях ;)

Цитата AVA12 @ 24.04.19, 18:16

Гм. Полный перебор цепочки из десяти тысяч (в среднем!) записей - это быстрый поиск? Ну, не знаю.

да нет там такого, там все норм. и красиво будет и быстро в том числе (относительно)

Цитата AVA12 @ 24.04.19, 18:16

Дилетант, не понимающий, как решить тривиальную задачу (реализация битового массива)

поставь мне задачу на создание бит.массива (т е что-то локальное, где нужно именно иметь понимание получения этого типа массива)! вдруг смогу сделать! не смогу - так не смогу)) бывает...

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

AVA12 — Wed, 24 Apr 2019 18:16:12 +0000

AVA12:

Цитата

быстрый поиск №тел. с применением ХТ на цепочках! все!

Гм. Полный перебор цепочки из десяти тысяч (в среднем!) записей - это быстрый поиск? Ну, не знаю.

Цитата

не путай Программистов и дилетантов)

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

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

Qraizer — Wed, 24 Apr 2019 16:48:33 +0000

Qraizer:

Цитата FasterHarder @ 24.04.19, 14:52

прогга у меня на "чистом" С89.
...
А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит.

В Плюсах есть std::bitset<> и std::vector. Тебе какой?

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Wed, 24 Apr 2019 15:36:59 +0000

FasterHarder:

Цитата AVA12 @ 24.04.19, 15:33

Какова же настоящая задача?

быстрый поиск №тел. с применением ХТ на цепочках! все!

Цитата AVA12 @ 24.04.19, 15:33

Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет.

не путай Программистов и дилетантов)

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

AVA12 — Wed, 24 Apr 2019 15:33:47 +0000

AVA12: Что вопрос решен - это хорошо, но было бы любопытно узнать: а в чем, собственно, вопрос заключался? Задача "захэшировать пятьдесят миллионов значений в таблицу на пять тыщ позиций" изначально звучит бредово. Какова же настоящая задача?

P. S.

Цитата

В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт.

Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!

Гм. Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет.

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Wed, 24 Apr 2019 14:52:11 +0000

FasterHarder:

Цитата OpenGL @ 24.04.19, 12:01

Заводим битовый массив длиной миллиард

прогга у меня на "чистом" С89. Насколько помню, самый дешевый тип данных там char (8 бит). Логич.типа нету, есть он в стандарте C99 (), но и там логич.тип наверняка 1байтовый.
А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит. В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт.

Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!

Итак, решено делать так, тем более, что в сети декларируют, что мол это один из лучших варианов хеширования. окэй!
Дан телефон в виде строки: "8(928) 183-18-35". Строим из него число x = 281 831 835 (тип данных х --> unsigned, до 4.2 лярдов держит, мне хватит!).
Берем минимальное простое число, которое перекрывает множество алфавита, это число 11.
Можно считать, что имеем число 281831835 по основанию (11). Далее переводим из СС(11) в СС(10) по правилам.
Вообще, по идее, можно числовое представление и не получать,а сразу обрабатывать строковое представление №телефона.

b0 * 11^0 + b1 * 11^1 + ... + b7 * 11^7 + b8 * 11^8, по идее для этой суммы хватит того же unsigned. В алгоритме, который видел бегут по строке СЛЕВА НАПРАВО, я же пойду наоборот. А какая разница-то? Да, никакой!
Т е ХФ вернет значение вот этой суммы. Хэш-таблица - одномерный динамический массив, у которой тип данных элементов самый дешевый, ну, например, ну, не знаю unsigned char (нету типа данных = 1биту).

Допустим, ХФ вернуло значение 99 832 104, лезем по этому индексу в ХТ и ставим, ну, не знаю, какой-то признак, ну, например, символ 'y' (типа 'y' - YES, т е есть такой №тел.). По умолчанию все элементы пустой ХТ равны чему-то, ну, не знаю чему. Да хоть чему, главное не 'y')

Как я понимаю, в этом случае коллизий не будет вообще, т к любое уникальное число в СС(11) преобразуется в уникальное значение в СС(10).
Я не знаю, вроде хотелось цепочки получать, а их тут НЕ БУДЕТ физически ни одной (кроме 1-го элемента).
На самом деле их можно получить, если, допустим для суммы взять не тип данных unsigned, а, например, unsigned short. В этом случае будет возникать переполнение. НУ И ЧТО! пусть идет вычет по модулю, да и все. В этом случае будет гораздо меньше элементов в ХТ.

В общем вот так буду делать, и там все должно быть норм. и красиво и быстро и эффективно и не заморочено! УРА! 8-)

P.S. но вообще, создание хороших ХФ (не как в моем трив.случае), требует не дюжей подготовки в Computer Science, ага...Ну это мое мнение, разумеется)

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

OpenGL — Wed, 24 Apr 2019 12:01:47 +0000

OpenGL:

Цитата FasterHarder @ 24.04.19, 10:50

Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??

У тебя номера телефонов, судя по маске, 9 циферные. Т.е. всего номеров 1 миллиард. Заводим битовый массив длиной миллиард, в котором 0 - телефона нет. 1 - есть. Всё же очевидно. Твоему номеру телефона соответствует число 11193890 - элемент с таким номером и задавай в 1. И кстати, а чем это не хеш-функция? Причём она идеальная без коллизий :D

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Wed, 24 Apr 2019 10:50:45 +0000

FasterHarder: Akina, ну есть файл с телефонами и нужно создать на ее основе хеш-таблицу методом цепочек ДЛЯ ПОИСКА. вот и все условие. Детали формата написаны в 1-ом посте (там все тривиально).
Вот я и думаю), какую бы ХФ пооптимальнее соорудить...

Цитата OpenGL @ 24.04.19, 05:21

С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет.

ну, в принципе да! сдвинуть в 0 даже удобнее с позиции языка СИ, т к нумерация элементов идет от 0...

Добавлено 24.04.19, 10:51

Цитата Akina @ 24.04.19, 04:36

Во-вторых, почему одну, а не, скажем, 4 или 5?

а вот именно по этой причине и был создан вопрос в разделе "Алгоритмы", что понять, 1цифру или 4 или 5, а может даже 6! Или вообще совсем др.подход использовать...

Добавлено 24.04.19, 10:57

Цитата OpenGL @ 24.04.19, 05:21

Я бы битовым массивом тупо всё сделал.

я чисто для себя полюбопытствовать (хотя битовую сетка в задании не нужна). Битовая сетка - это ведь набор элементов/бит, принимающих значения из множества {0, 1}.
Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

OpenGL — Wed, 24 Apr 2019 05:21:53 +0000

OpenGL:

Цитата FasterHarder @ 23.04.19, 20:00

а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)?

Нисколько. Я бы битовым массивом тупо всё сделал. Его размер получился бы 128 мегабайт всего. Всяко меньше, чем вся хеш-таблица, содержащая 50 миллионов номеров.

Цитата FasterHarder @ 23.04.19, 20:00

ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

Akina — Wed, 24 Apr 2019 04:36:08 +0000

Akina: Нужно, нужно... хрень голимая. Всё, что делается - делается зачем-то, а не для умственного онанизма. А потому - формулируй задачу. Наху зачем тебе это хэширование нужно? Искать номер? считать статистику? что-то ещё? от задачи и будет плясать оптимальное решение.

Цитата Gonarh @ 23.04.19, 17:30

Есть. БД. Индексы.

+146% Правильно спроектированная и проиндексированная БД - выиграет у любого рукописного приложения, за исключением узкоспецифичных однозадачников.

Цитата FasterHarder @ 23.04.19, 18:12

смутно помню, в основе индексов лежат какие-то древовидные структуры данных

После получения хэша тебе ещё надо оптимизировать таблицу этих хэшей для быстрого поиска. И эта оптимизированная таблица поиска у тебя будет сортированной, а оптимизацию самого поиска ты будешь производить, интерпретируя сортированный массив хэшей как дерево - явно или неявно (если не хочешь проиграть по дисковым операциям и операциям поиска в загруженном в память массиве). Заодно придёшь к мысли о кластеризации хэш-таблицы, и... поздравляю, ты придумал свою СУБД.

Цитата FasterHarder @ 23.04.19, 14:03

1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел.

Во-первых, коллизия для любого телефона с вероятностью 1-0,9^4999999. Т.е. вероятностью отсутствия коллизии можно смело пренебречь. А не прогнозируемые тобой 90%.
Во-вторых, почему одну, а не, скажем, 4 или 5?

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Tue, 23 Apr 2019 20:00:47 +0000

FasterHarder:

Цитата OpenGL @ 23.04.19, 19:28

или сколько тебе там значений хеша нужно

а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)? в 1-ом посте и спрашиваю в том числе про это кол-во.

'0' --> 0 или '0' --> 48??
ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

OpenGL — Tue, 23 Apr 2019 19:28:14 +0000

OpenGL: Номер телефона, преобразованный в число mod 5000 (или сколько тебе там значений хеша нужно) и всё, если уж хочешь изобретать велосипед.

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Tue, 23 Apr 2019 18:12:47 +0000

FasterHarder:

Цитата Gonarh @ 23.04.19, 17:30

БД. Индексы.

насколько смутно помню, в основе индексов лежат какие-то древовидные структуры данных!
меня интересует почти оптимальная хэш-функция...

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

Gonarh — Tue, 23 Apr 2019 17:30:23 +0000

Gonarh: Есть. БД. Индексы.

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Tue, 23 Apr 2019 17:10:28 +0000

FasterHarder: нашел такой пример в инете хеширования строк!
№тел.такой: 8(9ХХ) ХХХ-ХХ-ХХ, преобразуем в строку вида "ХХХХХХХХХ", т е в строку, состоящую ТОЛЬКО из 10-ных цифр в кол-ве РОВНО 9 штук.
Мощность алфавита М = 10 (т к всего 10 различных цифр). Берем максимальное простое число, попадающее по значению в мощность множества Р = 7 (Р <= M) + Р-простое.
И после этого вычисляем ХЭШ по правилу:
<АСКИ-код 1-й цифры строки> * P^0 + <АСКИ-код 2-й цифры> * P^1 + ... + <АСКИ-код предпоследней цифры> * P^7 + <АСКИ-код последней> * P^8

Номера телефонов лежат на отрезке ["000000000" .. "999999999"]. Значит, хеш-код будет лежать на отрезке от 0 до
57 + 57*7 + 57*7^2 + ... + 57*7^7 + 57*7^8 = infinity

вот тут не знаю, может имеет смысл брать не АСКИ-коды цифр-символов ('0' --> 48, '1'---> 49, ..., '9'--> 57), а цифру-цифру равную символе-цифре('0' --> 0, .., '9' --> 9), тогда правая граница значительно сократится!

Но в любом случае, хэш-таблица будет представлять собой динамический массив, у которого кол-во элементов равно этому "инифинити". Но ведь таблица будет очень РАЗРЯЖЕННОЙ, т к не все хеш-коды можно сгенерить. Это нормально, да??

Кстати, этот алгоритм очень мне напоминает алгоритм сравнения двух дат, когда ДД, ММ и ГГГГ умножаются на возрастающие коэффы, а потом складываются...

Наверное, так тупо и буду делать или есть ГОРАЗДО лучше что-то??

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

Pavia — Tue, 23 Apr 2019 15:21:18 +0000

Pavia: А зачем вам метод цепочек?
Использовать двойное хэширование и всё.
Не могу до конца понять двойное хеширование (перемешанные таблицы)

Хеш-функция (хеш-таблица) для кодирования номеров телефонов

FasterHarder — Tue, 23 Apr 2019 14:03:36 +0000

FasterHarder: Всем хай! Сходу к делу!

Есть текстовый файл, в котором хранятся номера моб.телефонов(на 1 строке файла лежит 1 номер).
Маска телефонов: 8(9XX) XXX-XX-XX, X - цифра, т е принимает целое значение от 0 до 9.
Примеры правильных ном. телефонов:
1. 8(919) 100-08-73
2. 8(903) 981-02-22
...
В файле может хранится до 50 млн. РАЗЛИЧНЫХ ном.телефонов.
Нужно в общем их захешировать по оптимальнее (не прям чтоб идеально) методом цепочек.
===================================================
Вот, если требовалось бы только искать ном.телефонов, тогда я бы преобразовал ном.телефонов в целые числа (без учета первой 8-ки и 9-ки), отсортировал бы Хоаром и дихотомией бы искал. Оптимальнее способа ИМХО не существовало бы. Но тогда бы вставка была бы недопустимой из-за сдвига на 1 позицию влево-вправо лютого кол-ва элементов. Прогга умерла бы при вставке, удалении (с послед.сжатием).

Нужна какая-то хэш-функция! Желательно получше...
1. Нужно понять, в каком типе данных обрабатывать ном.тел.: строка или перевод в целое число?
2. Хотелось бы эти 50млн. записей в файле ОТРАЗИТЬ в хеш-таблицу, в которой не более 5000 записей. Т е в отношении 1 к 10 000. Или мало 5000 для хеш-таблицы?? Очевидно, что коллизий НЕ ИЗБЕЖАТЬ ни при каких раскладах...

Примеры ХФ:
1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел.
2. вернуть (сумму цифр тел.) mod (длина номера) - некий аналоги способа 1.
3. вернуть самую часто встречаемую цифру в №тел. - опять-таки, будет всего 10 записей в ХТ и коллизия на каждом 10-ом
...

т е все, что приходит на ум из простого отображает все номера телефонов в 10 записей ХТ. Это ведь плохо, так?

Если привязывать к АСКИ-кодам цифр (№тел. рассматривается как строка), тут, что можно придумать?

Я хотел бы узнать у общества, вот, если подается 50млн.записей, то в какой размер ХТ это желательно отразить? №тел.задаются ХАОТИЧНО и там нет никакой частотности или закономерности.
Какую ХФ лучше взять?