Some services (for instance ProtonMail) claim to store hashes of phone numbers, instead of phone numbers themselves (while they don’t say how they hash it). Now, given that the number of potentially valid phone numbers is very small (about 26 bits worth of information in an 8-digit phone numbers), it should be quite easy to recover a phone number from its hash.
So what’s the point?
asked Mar 15, 2018 at 14:35
BlenderBenderBlenderBender
5391 gold badge4 silver badges7 bronze badges
7
ProtonMail may request your phone number to perform a human check:
- ProtonMail detects that you’re attempting to create several accounts.
- It requests you a phone number, to send you a token via SMS.
- You must send that token to ProtonMail to prove you’re the phone number owner.
Then, ProtonMail doesn’t need your phone number anymore, but it still need to use it to prevent spammers to create multiple accounts.
Hashing the phone number allows it to not store the original number and to prevent someone to use the same number twice.
From their FAQ:
However, using the same phone number will result in obtaining the same cryptographic hash, so by comparing hashes, we can detect re-use of phone number or email addresses for human verification.
Thus ProtonMail doesn’t seem to use unique salts.
We also know thanks to a tweet from Bart Butler (ProtonMail CTO) that:
- ProtonMail regularly flushes stored hashes.
- Stored hashes aren’t linked to any account.
Bart Butler also tweeted:
We use a slow password hash (With a salt) and flush the list and rotate the salt at irregular intervals.
In conclusion: brute-forcing them is possible, but it’s neither practical nor useful.
answered Mar 15, 2018 at 14:48
Benoit EsnardBenoit Esnard
14k7 gold badges65 silver badges65 bronze badges
21
The hash is useful as an indirect map, even if it’s not as secure as a typical hashing setup. One of the biggest benefits is purely social. Hashing (even a weak hash) draws a clear line in the sand for an employee about what is acceptable to view. Putting up any barriers to viewing the real phone number will help keep honest people honest.
it should be quite easy to recover a phone number from its hash
Easy is a relative term. True, this hashing setup may not help much against a determined attacker who is willing to perform hash cracking. But you also have to think of the 99% of other employees with access to the data who don’t even know what a hash really is, let alone how to crack them.
answered Mar 16, 2018 at 18:07
ryanyuyuryanyuyu
2111 silver badge5 bronze badges
2
The point is to not store them in plaintext.
That is probably pretty much it. As D.W. pointed out in his comments, that Benoit’s answer, tells you their reason why they store phone numbers and that they hash them. ProtonMail does not tell you why they hash them. We all can only speculate about this, until an employee of ProtonMail tells us the exact reason.
The most probable reason is (in my opinion) is the following:
ProtonMail is a company whose whole business model is founded on secure products and protecting a customer’s privacy. If they told you, that they saved phone numbers in plaintext, that would be pretty weird. Hashing them makes much more sense in that regard, don’t you think?
On the other hand, ProtonMail doesn’t link phone number hashes to user profiles, they flush the hashes regularly and as you stated yourself, there’s not much to gain from a phone number.
Hashing phone numbers if they have to store them is better than not hashing them. That’s why they do it.
Does it strengthen security much? No.
Is it better than storing them in plaintext? Yes.
answered Mar 16, 2018 at 10:04
Tom K.Tom K.
7,9633 gold badges30 silver badges53 bronze badges
There are two reasons for storing hashed phone numbers, one is useful the other one is not:
1) Allow to verify the user. Here a salted slow hash is useful. While brute-forcing a phone number is faster than a password, it still provides added security.
2) Pretend to provide a more safe lookup (i.e. in several of whatsapp competitors). Here you cannot salt the hash, because you would not be able to search for the hash when only knowing the phone number. This means a rainbow table is easy to create as the search space of unsalted hashes is really small.
Note that 1) still provides an easy proof of existence when you have the database. Hash your phone number with all the salts used in the database and look it up. If it is stored in there, you will find it.
answered Mar 16, 2018 at 9:29
alloallo
3,30511 silver badges24 bronze badges
Some services (for instance ProtonMail) claim to store hashes of phone numbers, instead of phone numbers themselves (while they don’t say how they hash it). Now, given that the number of potentially valid phone numbers is very small (about 26 bits worth of information in an 8-digit phone numbers), it should be quite easy to recover a phone number from its hash.
So what’s the point?
asked Mar 15, 2018 at 14:35
BlenderBenderBlenderBender
5391 gold badge4 silver badges7 bronze badges
7
ProtonMail may request your phone number to perform a human check:
- ProtonMail detects that you’re attempting to create several accounts.
- It requests you a phone number, to send you a token via SMS.
- You must send that token to ProtonMail to prove you’re the phone number owner.
Then, ProtonMail doesn’t need your phone number anymore, but it still need to use it to prevent spammers to create multiple accounts.
Hashing the phone number allows it to not store the original number and to prevent someone to use the same number twice.
From their FAQ:
However, using the same phone number will result in obtaining the same cryptographic hash, so by comparing hashes, we can detect re-use of phone number or email addresses for human verification.
Thus ProtonMail doesn’t seem to use unique salts.
We also know thanks to a tweet from Bart Butler (ProtonMail CTO) that:
- ProtonMail regularly flushes stored hashes.
- Stored hashes aren’t linked to any account.
Bart Butler also tweeted:
We use a slow password hash (With a salt) and flush the list and rotate the salt at irregular intervals.
In conclusion: brute-forcing them is possible, but it’s neither practical nor useful.
answered Mar 15, 2018 at 14:48
Benoit EsnardBenoit Esnard
14k7 gold badges65 silver badges65 bronze badges
21
The hash is useful as an indirect map, even if it’s not as secure as a typical hashing setup. One of the biggest benefits is purely social. Hashing (even a weak hash) draws a clear line in the sand for an employee about what is acceptable to view. Putting up any barriers to viewing the real phone number will help keep honest people honest.
it should be quite easy to recover a phone number from its hash
Easy is a relative term. True, this hashing setup may not help much against a determined attacker who is willing to perform hash cracking. But you also have to think of the 99% of other employees with access to the data who don’t even know what a hash really is, let alone how to crack them.
answered Mar 16, 2018 at 18:07
ryanyuyuryanyuyu
2111 silver badge5 bronze badges
2
The point is to not store them in plaintext.
That is probably pretty much it. As D.W. pointed out in his comments, that Benoit’s answer, tells you their reason why they store phone numbers and that they hash them. ProtonMail does not tell you why they hash them. We all can only speculate about this, until an employee of ProtonMail tells us the exact reason.
The most probable reason is (in my opinion) is the following:
ProtonMail is a company whose whole business model is founded on secure products and protecting a customer’s privacy. If they told you, that they saved phone numbers in plaintext, that would be pretty weird. Hashing them makes much more sense in that regard, don’t you think?
On the other hand, ProtonMail doesn’t link phone number hashes to user profiles, they flush the hashes regularly and as you stated yourself, there’s not much to gain from a phone number.
Hashing phone numbers if they have to store them is better than not hashing them. That’s why they do it.
Does it strengthen security much? No.
Is it better than storing them in plaintext? Yes.
answered Mar 16, 2018 at 10:04
Tom K.Tom K.
7,9633 gold badges30 silver badges53 bronze badges
There are two reasons for storing hashed phone numbers, one is useful the other one is not:
1) Allow to verify the user. Here a salted slow hash is useful. While brute-forcing a phone number is faster than a password, it still provides added security.
2) Pretend to provide a more safe lookup (i.e. in several of whatsapp competitors). Here you cannot salt the hash, because you would not be able to search for the hash when only knowing the phone number. This means a rainbow table is easy to create as the search space of unsalted hashes is really small.
Note that 1) still provides an easy proof of existence when you have the database. Hash your phone number with all the salts used in the database and look it up. If it is stored in there, you will find it.
answered Mar 16, 2018 at 9:29
alloallo
3,30511 silver badges24 bronze badges
В этом цикле статей мы научимся хэшировать пользовательские данные, генерировать импортный файл для рекламных систем, а также передавать их по API Аудиторий и Management API. В этом гайде, мы напишем класс, для хэширования и генерации номер мобильных телефонов и мейлов. В конце гайда можно будет скачать готовый для работы класс.
Давайте для начала разберемся форматом файла, который вы должны подготовить перед использованием класса.
- Формат: CSV (UTF-8)
- Столбцы и заголовки: phone,email
- Формат номера мобильного телефона: 79251234567
- Скачать образец
Напомним, что для яндекса мы используем алгоритм хэширования md5, а для google sha256. Если вам неинтересно читать как работает класс Hasher (готовый класс для генерации и хэширования аудитории по списку), просто скачайте архив с кодом и образцом csv по кнопке.
Скачать архив с кодом
Хэширование md5 и sha256 в Python
Для хэширования данных будем использовать библиотеку hashlib, которая идет вместе с интерпретатором Python. Давайте импортируем библиотеку и разберем функции, которые нам понадобятся. Напишем тестовый код, для демонстрации работы:
import hashlib line = '79214532167' m = hashlib.md5() # Создаем объект класса <class '_hashlib.HASH'> m.update(line.encode()) # Юникод-объекты должны быть закодированы перед хэшированием print(m.hexdigest()) # дайджест HEX строки # Вывод: 2c0beef2cdd0ddae1b7777b928c7dd29 m = hashlib.sha256() # Создаем объект класса <class '_hashlib.HASH'> m.update(line.encode()) # Юникод-объекты должны быть закодированы перед хэшированием print(m.hexdigest()) # дайджест HEX строки # Вывод: cb24e31afad0ab104eabaaacf7ef203dd4ec93cbd5a506db89327a515c36a92b
Окей, мы поняли как работает хэширование, осталось только сгенерировать файлы для рекламных систем, приводить этот код не имеет особого смысла, так как там создаем простой DataFrame где происходят манипуляции с колонками. Однако, я все же покажу как происходят вызовы функций.
Для того, чтобы применить функцию хэширования мы обращаемся к функции .apply, подробнее в коде ниже.
''' Мы создаем еще одну захешированную колонку в DataFrame, а к исходной колонке применяем функцию apply, которая применяет лямбда-функцию к каждоой строчке данной колонки, где и происходят вызовы функции get_md5. Подробнее в полном коде под статьей. P.S. Я сознательно не разбираю особенности Python, потому что не являюсь профессиональным разработчиком. Подробнее про функции читайте в документации и в блогах экспертов. ''' buffer_df['mail_md5'] = buffer_df['email'].apply(lambda x: self.get_md5(str(x)))
По необходимости, вы можете использовать код как отдельный инструмент, например, выгружать пользовательские данные из базы данных.
- Выполняем запрос к базе данных с помощью функции pd.read_sql получая на выходе DataFrame
- И сразу вызываем Hasher передавая в него dataframe с колонками email и phone
В архиве с кодом, который вы можете скачать выше находится класс Hasher. Я постарался максимально прокомментировать блоки кода, поэтому пользуйтесь и повышайте эффективность ваших рекламных активностей, преследуя главную цель маркетолога — улучшение пользовательского опыта взаимодействия с вашим продуктом, пускай и с помощью релевантной контекстной рекламы.
Требования к файлу с хэшированными данными Google Ads: https://support.google.com/google-ads/answer/7659867?hl=ru
Требования к файлу с хэшированными данными Yandex.Direct: https://yandex.ru/support/audience/file.html
Цитата OpenGL @ 24.04.19, 12:01
Заводим битовый массив длиной миллиард
прогга у меня на «чистом» С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, ага…Ну это мое мнение, разумеется)
Сообщение отредактировано: FasterHarder — 24.04.19, 15:03
Description of problem:
I’m in the process of working with a highly sensitive data-set that contains the people’s phone number information as one of the columns. I need to apply (encryption/hash function on them) to convert them as some encoded values and do my analysis. It can be an one-way hash — i.e, after processing with the encrypted data we wont be converting them back to original phone numbers. Essentially, am looking for an anonymizer that takes phone numbers and converts them to some random value on which I can do my processing. Suggest the best way to do about this process. Recommendations on the best algorithms to use are welcome.
Update: size of the dataset
My dataset is really huge in the size of hundreds of GB.
Update: Sensitive
By sensitive, I meant that phone number should not be a part of our analysis.So, basically I would need a one-way hashing function but without redundancy — Each phone number should map to unique value —Two phones numbers should not map to a same value.
Update: Implementation ?
Thanks for your answers.I am looking for elaborate implementation.I was going through python’s hashlib library for hashing, Does it necessarily do the same set of steps that you suggested ? Here is the link
Can you give me some example code to achieve the process , preferably in Python ?
asked Apr 8, 2013 at 20:28
15
Generate a key for your data set (16 or 32 bytes) and keep it secret. Use Hmac-sha1 on your data with this key, and base 64 encode that and you have a random unique string per phonenumber that isn’t reversable (without the key).
Example (Hmac-Sha1 with 256bit key) using Keyczar:
Create random secret key:
$> python keyczart.py create --location=path_to_key_set --purpose=sign
$> python keyczart.py addkey --location=path_to_key_set --status=primary
Anonymize phone number:
from keyczar import keyczar
def anonymize(phone_num):
signer = keyczar.Signer.Read("path_to_key_set");
return signer.Sign(phone_num)
answered Apr 8, 2013 at 21:07
jbtulejbtule
31.2k12 gold badges95 silver badges128 bronze badges
5
If you’re going to use cryptography, you want to apply a pseudorandom function to each phone number and throw away the key. Collision-resistant hashes such as SHA-256 do not provide the right security guarantees. Really, though, are there that many different phone numbers that you can’t just construct incrementally a map representing an actually random function?
answered Apr 8, 2013 at 21:32
David EisenstatDavid Eisenstat
62.6k7 gold badges61 silver badges120 bronze badges
10
sort your data by the respective column and start counting distinct values … replace the actual values with their respective counter value … collision free … one way …
answered Apr 8, 2013 at 23:05
DarkSquirrel42DarkSquirrel42
10k3 gold badges19 silver badges30 bronze badges
3
«So, basically I would need a one-way hashing function but without redundancy — Each phone number should map to unique value —Two phones numbers should not map to a same value.«
This screams for a solution based on a cryptographic hash function. MD5 and SHA-1 are the best known examples, and work wonderfully for this. You will read that «MD5 has been cracked», but for your purpose that doesn’t matter.
answered Apr 8, 2013 at 22:55
2
Description of problem:
I’m in the process of working with a highly sensitive data-set that contains the people’s phone number information as one of the columns. I need to apply (encryption/hash function on them) to convert them as some encoded values and do my analysis. It can be an one-way hash — i.e, after processing with the encrypted data we wont be converting them back to original phone numbers. Essentially, am looking for an anonymizer that takes phone numbers and converts them to some random value on which I can do my processing. Suggest the best way to do about this process. Recommendations on the best algorithms to use are welcome.
Update: size of the dataset
My dataset is really huge in the size of hundreds of GB.
Update: Sensitive
By sensitive, I meant that phone number should not be a part of our analysis.So, basically I would need a one-way hashing function but without redundancy — Each phone number should map to unique value —Two phones numbers should not map to a same value.
Update: Implementation ?
Thanks for your answers.I am looking for elaborate implementation.I was going through python’s hashlib library for hashing, Does it necessarily do the same set of steps that you suggested ? Here is the link
Can you give me some example code to achieve the process , preferably in Python ?
asked Apr 8, 2013 at 20:28
15
Generate a key for your data set (16 or 32 bytes) and keep it secret. Use Hmac-sha1 on your data with this key, and base 64 encode that and you have a random unique string per phonenumber that isn’t reversable (without the key).
Example (Hmac-Sha1 with 256bit key) using Keyczar:
Create random secret key:
$> python keyczart.py create --location=path_to_key_set --purpose=sign
$> python keyczart.py addkey --location=path_to_key_set --status=primary
Anonymize phone number:
from keyczar import keyczar
def anonymize(phone_num):
signer = keyczar.Signer.Read("path_to_key_set");
return signer.Sign(phone_num)
answered Apr 8, 2013 at 21:07
jbtulejbtule
31.2k12 gold badges95 silver badges128 bronze badges
5
If you’re going to use cryptography, you want to apply a pseudorandom function to each phone number and throw away the key. Collision-resistant hashes such as SHA-256 do not provide the right security guarantees. Really, though, are there that many different phone numbers that you can’t just construct incrementally a map representing an actually random function?
answered Apr 8, 2013 at 21:32
David EisenstatDavid Eisenstat
62.6k7 gold badges61 silver badges120 bronze badges
10
sort your data by the respective column and start counting distinct values … replace the actual values with their respective counter value … collision free … one way …
answered Apr 8, 2013 at 23:05
DarkSquirrel42DarkSquirrel42
10k3 gold badges19 silver badges30 bronze badges
3
«So, basically I would need a one-way hashing function but without redundancy — Each phone number should map to unique value —Two phones numbers should not map to a same value.«
This screams for a solution based on a cryptographic hash function. MD5 and SHA-1 are the best known examples, and work wonderfully for this. You will read that «MD5 has been cracked», but for your purpose that doesn’t matter.
answered Apr 8, 2013 at 22:55
2
Why do you need to a non-standard hash function at all?
There are plenty of hash functions which are well tested and have known properties which will work fine for any input, thus will also work well for phone numbers, which are after all a subset of ASCII strings. Is your application so time critical that you need to design your own hash function and risk something with more collisions? If not, why not use one of the well known hash functions?
For instance, if you need something with cryptographically demonstrable collision resistance, use SHA-256 (truncated if you want). If you are not worried about an adversary, use something like universal hashing. Unless your problem is very specialised, you will be better off using someone else’s well tested hash algorithm than trying to invent one yourself.
An even easier hash is the original hash perl used, which worked as follows:
# Return the hashed value of a string: $hash = perlhash("key")
# (Defined by the PERL_HASH macro in hv.h)
sub perlhash
{
$hash = 0;
foreach (split //, shift) {
$hash = $hash*33 + ord($_);
}
return $hash;
}
In English, it takes the current hash value, multiplies by 33, and adds the ASCII value of the next character on. It’s not a great hash, but it worked for perl for a long while.
Предположим, мы хотим разработать систему хранения записей сотрудников, введенных с использованием телефонных номеров. И мы хотим, чтобы следующие запросы выполнялись эффективно:
- Введите номер телефона и соответствующую информацию.
- Найдите номер телефона и получите информацию.
- Удалить номер телефона и соответствующую информацию.
Мы можем подумать об использовании следующих структур данных для хранения информации о разных телефонных номерах.
- Массив телефонных номеров и записей.
- Связанный список телефонных номеров и записей.
- Сбалансированное двоичное дерево поиска с телефонными номерами в качестве ключей.
- Таблица прямого доступа.
Для массивов и связанных списков нам нужно искать линейно, что на практике может быть дорогостоящим. Если мы используем массивы и сохраняем данные отсортированными, то телефонный номер можно искать за O (Logn) время с помощью бинарного поиска, но операции вставки и удаления становятся дорогостоящими, поскольку мы должны поддерживать отсортированный порядок.
При сбалансированном бинарном дереве поиска мы получаем умеренное время поиска, вставки и удаления. Все эти операции могут быть гарантированно выполнены за время O (Logn).
Другое решение, о котором можно подумать, — это использовать таблицу прямого доступа, где мы создаем большой массив и используем номера телефонов в качестве индекса в массиве. Запись в массиве равна NIL, если номер телефона отсутствует, иначе запись массива хранит указатель на записи, соответствующие номеру телефона. Сложность по времени это решение является лучшим среди всех, мы можем выполнять все операции за O (1) времени. Например, чтобы вставить номер телефона, мы создаем запись с подробностями данного номера телефона, используем номер телефона в качестве индекса и сохраняем указатель на созданную запись в таблице.
Это решение имеет много практических ограничений. Первая проблема с этим решением — дополнительное пространство, которое требуется. Например, если номер телефона состоит из n цифр, нам нужно O (m * 10 n ) место для таблицы, где m — размер указателя на запись. Другая проблема заключается в том, что целое число в языке программирования может не хранить n цифр.
Из-за вышеуказанных ограничений таблица прямого доступа не всегда может быть использована. Хеширование — это решение, которое может использоваться практически во всех таких ситуациях и работает очень хорошо по сравнению с вышеупомянутыми структурами данных, такими как массив, связанный список, сбалансированный BST на практике. С хэшированием мы получаем O (1) время поиска в среднем (при разумных допущениях) и O (n) в худшем случае.
Хеширование является улучшением по сравнению с таблицей прямого доступа. Идея состоит в том, чтобы использовать хеш-функцию, которая преобразует данный номер телефона или любую другую клавишу в меньшее число и использует небольшое число в качестве индекса в таблице, называемой хеш-таблицей.
Функция хеширования : функция, которая преобразует данный большой номер телефона в небольшое практическое целое значение. Отображенное целочисленное значение используется в качестве индекса в хэш-таблице. Проще говоря, хеш-функция отображает большое число или строку в маленькое целое число, которое можно использовать в качестве индекса в хеш-таблице.
Хорошая хеш-функция должна иметь следующие свойства
1) Эффективно вычислимо.
2) Должны равномерно распределять ключи (каждая позиция таблицы одинаково вероятна для каждого ключа)
Например, для телефонных номеров плохая хеш-функция состоит в том, чтобы брать первые три цифры. Лучшая функция — рассмотреть последние три цифры. Обратите внимание, что это может быть не самой лучшей хэш-функцией. Там могут быть лучшие способы.
Хеш-таблица : массив, в котором хранятся указатели на записи, соответствующие данному номеру телефона. Запись в хэш-таблице равна NIL, если ни один из существующих телефонных номеров не имеет значения хэш-функции, равного индексу для записи.
Обработка коллизий : поскольку хэш-функция получает небольшое число для большого ключа, существует вероятность, что два ключа приводят к одному значению. Ситуация, когда вновь вставленный ключ отображается на уже занятый слот в хэш-таблице, называется коллизией и должна обрабатываться с использованием некоторой техники обработки коллизий. Ниже приведены способы обработки столкновений:
- Цепочка: идея состоит в том, чтобы каждая ячейка хеш-таблицы указывала на связанный список записей, имеющих одинаковое значение хеш-функции. Цепочка проста, но требует дополнительной памяти вне таблицы.
- Открытая адресация. При открытой адресации все элементы хранятся в самой хеш-таблице. Каждая запись в таблице содержит либо запись, либо NIL. При поиске элемента мы один за другим проверяем слоты таблицы, пока не будет найден нужный элемент или пока не станет ясно, что элемента нет в таблице.
Следующие сообщения:
Отдельная цепочка для обработки столкновений
Открытая адресация для обработки столкновений
Ссылки:
MIT Video Lecture
IITD Видео Лекция
«Введение в алгоритмы», второе издание Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста и Клиффорда Стейна .
http://www.cs.princeton.edu/~rs/AlgsDS07/10Hashing.pdf
http://www.martinbroadhurst.com/articles/hash-table.html
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Преобразовать массив в уменьшенную форму | Набор 1 (простой и хэширующий)
- Перемешивание кукушки — наихудший случай O (1) Поиск!
- Top 20 Hash Technique на основе вопросов для интервью
- Хеширование | Набор 2 (отдельная цепочка)
- Хеширование | Набор 3 (Открытая адресация)
- Союз и пересечение двух связанных списков | Set-3 (Хеширование)
- Отображение индекса (или тривиальное хеширование) с разрешенными негативами
- Проблемы с практикой хеширования
- C ++ программа для хеширования с цепочкой
- Двойное хеширование
- Объединенное хеширование
- Элемент большинства Set-2 (Хеширование)
- Приложения хеширования
- Хеширование на Java
- Сортировка адресов с использованием хеширования
Хеширование | Комплект 1 (Введение)
0.00 (0%) 0 votes