Форум на Исходниках.RU > Алгоритмы > Хеш-функция (хеш-таблица) для кодирования номеров телефонов
Автор: FasterHarder 23.04.19, 14:03
Всем хай! Сходу к делу!
Есть текстовый файл, в котором хранятся номера моб.телефонов(на 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млн.записей, то в какой размер ХТ это желательно отразить? №тел.задаются ХАОТИЧНО и там нет никакой частотности или закономерности. Какую ХФ лучше взять?
нашел такой пример в инете хеширования строк!
№тел.такой: 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), тогда правая граница значительно сократится!
Но в любом случае, хэш-таблица будет представлять собой динамический массив, у которого кол-во элементов равно этому "инифинити". Но ведь таблица будет очень РАЗРЯЖЕННОЙ, т к не все хеш-коды можно сгенерить. Это нормально, да??
Кстати, этот алгоритм очень мне напоминает алгоритм сравнения двух дат, когда ДД, ММ и ГГГГ умножаются на возрастающие коэффы, а потом складываются...
Наверное, так тупо и буду делать или есть ГОРАЗДО лучше что-то??
а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)? в 1-ом посте и спрашиваю в том числе про это кол-во.
'0' --> 0 или '0' --> 48??
ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??
Автор: Akina 24.04.19, 04:36
Нужно, нужно... хрень голимая. Всё, что делается - делается зачем-то, а не для умственного онанизма. А потому - формулируй задачу. Наху зачем тебе это хэширование нужно? Искать номер? считать статистику? что-то ещё? от задачи и будет плясать оптимальное решение.
смутно помню, в основе индексов лежат какие-то древовидные структуры данных
После получения хэша тебе ещё надо оптимизировать таблицу этих хэшей для быстрого поиска. И эта оптимизированная таблица поиска у тебя будет сортированной, а оптимизацию самого поиска ты будешь производить, интерпретируя сортированный массив хэшей как дерево - явно или неявно (если не хочешь проиграть по дисковым операциям и операциям поиска в загруженном в память массиве). Заодно придёшь к мысли о кластеризации хэш-таблицы, и... поздравляю, ты придумал свою СУБД.
1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел.
Во-первых, коллизия для любого телефона с вероятностью 1-0,94999999. Т.е. вероятностью отсутствия коллизии можно смело пренебречь. А не прогнозируемые тобой 90%.
Во-вторых, почему одну, а не, скажем, 4 или 5?
а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)?
Нисколько. Я бы битовым массивом тупо всё сделал. Его размер получился бы 128 мегабайт всего. Всяко меньше, чем вся хеш-таблица, содержащая 50 миллионов номеров.
ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??
С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет.
Автор: FasterHarder 24.04.19, 10:50
Akina, ну есть файл с телефонами и нужно создать на ее основе хеш-таблицу методом цепочек ДЛЯ ПОИСКА. вот и все условие. Детали формата написаны в 1-ом посте (там все тривиально).
Вот я и думаю), какую бы ХФ пооптимальнее соорудить...
С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет.
ну, в принципе да! сдвинуть в 0 даже удобнее с позиции языка СИ, т к нумерация элементов идет от 0...
а вот именно по этой причине и был создан вопрос в разделе "Алгоритмы", что понять, 1цифру или 4 или 5, а может даже 6! Или вообще совсем др.подход использовать...
я чисто для себя полюбопытствовать (хотя битовую сетка в задании не нужна). Битовая сетка - это ведь набор элементов/бит, принимающих значения из множества {0, 1}.
Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??
Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??
У тебя номера телефонов, судя по маске, 9 циферные. Т.е. всего номеров 1 миллиард. Заводим битовый массив длиной миллиард, в котором 0 - телефона нет. 1 - есть. Всё же очевидно. Твоему номеру телефона соответствует число 11193890 - элемент с таким номером и задавай в 1. И кстати, а чем это не хеш-функция? Причём она идеальная без коллизий
прогга у меня на "чистом" С89. Насколько помню, самый дешевый тип данных там char (8 бит). Логич.типа нету, есть он в стандарте C99 (<stdbool.h>), но и там логич.тип наверняка 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. В этом случае будет возникать переполнение. НУ И ЧТО! пусть идет вычет по модулю, да и все. В этом случае будет гораздо меньше элементов в ХТ.
В общем вот так буду делать, и там все должно быть норм. и красиво и быстро и эффективно и не заморочено! УРА!
P.S. но вообще, создание хороших ХФ (не как в моем трив.случае), требует не дюжей подготовки в Computer Science, ага...Ну это мое мнение, разумеется)
Автор: AVA12 24.04.19, 15:33
Что вопрос решен - это хорошо, но было бы любопытно узнать: а в чем, собственно, вопрос заключался? Задача "захэшировать пятьдесят миллионов значений в таблицу на пять тыщ позиций" изначально звучит бредово. Какова же настоящая задача?
P. S.
Цитата
В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт.
Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!
Гм. Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет.
прогга у меня на "чистом" С89.
...
А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит.
В Плюсах есть std::bitset<> и std::vector<bool>. Тебе какой?
Автор: AVA12 24.04.19, 18:16
Цитата
быстрый поиск №тел. с применением ХТ на цепочках! все!
Гм. Полный перебор цепочки из десяти тысяч (в среднем!) записей - это быстрый поиск? Ну, не знаю.
Цитата
не путай Программистов и дилетантов)
Гм. Дилетант, не понимающий, как решить тривиальную задачу (реализация битового массива), но уже замахивающийся на структуры поиска? Тут явно порядок сортировки перепутан.
Дилетант, не понимающий, как решить тривиальную задачу (реализация битового массива)
поставь мне задачу на создание бит.массива (т е что-то локальное, где нужно именно иметь понимание получения этого типа массива)! вдруг смогу сделать! не смогу - так не смогу)) бывает...
