Шаблонная хэш-функция

#cpp #хеширование

Допустим, мне нужно сделать некий шаблонный контейнер Map на хэш-таблице. Контейнер,
естественно, может принимать ключем значение любых типов  - как, в таком случае, написать
хэш-функцию? Как привести произвольный тип T (для которого может быть не перегружен
оператор приведения) к целочисленному типу? 
Вроде как должен помочь reinterpret_cast, который приводит к указателю, но конструкция вида

reinterpret_cast  (key);


Отказывается компилироваться, когда key имеет не-целочисленный тип.

Если же приводить указатель к указателю (как в примере на msdn)

reinterpret_cast  (&key);


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

Можно ли как-то насильно интерпретировать байты произвольного объекта в памяти как
целочисленный тип?
Вообще, какое решение будет правильным? Как эта проблема решена в std::unordered_map
или QMap?
    

Ответы

Ответ 1

Классы наподобие unordered_set вычисляют хеш не сами, а используют std::hash (а также
дают возможность пользователю указать свою реализацию хеширования, если он недоволен
стандартной, или если её не существует).

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

Мне кажется, вам стоит не изобретать велосипед, а воспользоваться той же идеей. А
ещё проще, просто используйте std::hash. Поверьте, в написании контейнера есть много
сложностей помимо этой.



Таким образом, просто используйте 

size_t hash_value = std::hash()(t);

Можно ли сохранить экземпляр TDictionary целиком, включая хэши?

#delphi #оптимизация #хеширование #словари #биоинформатика

Учитывая, что теперь можно спокойно выделять большие объемы памяти внутри TMemoryStream,
я вернулся к идее хранения данных геномных исследований, используемых нами внутри TDictionary
в файле для будущего повторного использования. Класс определен так:

type
  PosIndex = packed record
     chr, pos:integer;
  end;
  PosIndexData = record
    gname, rname, promoter: string;
    count:array[0..NOfTissues-1] of byte;
  end;

TPosDict = class (TDictionary)
 private
   procedure SaveToStream(stream: TStream);
   procedure LoadFromStream(stream: TStream);
 public
   procedure SaveToFile(filename:string);
   procedure LoadFromFile(filename:string);
   procedure LoadFromZip(AFileName, InnerName: string);
   procedure SaveToZip(AFileName, InnerName: string);
end;


Предупреждая вопросы и комментарии в стиле "Зачем нужен TDictionary, когда есть базы
данных?", сразу скажу: у нас мобильное (не в плане телефона, а в плане, что оно часто
запускается где попало) приложение, мы не можем использовать стационарный сервер БД,
как коллега в своём вопросе Как оптимизировать таблицы/запрос в MySQL?, а работа с
файловыми БД с нашими объёмами данных, увы, крайне медленна. А вот с TDictionary поиск
происходит пусть не мгновенно, но для нас вполне подходяще по времени.

Запись в поток (этот метод затем используют и SaveToFile и SaveToZip) происходит так:

procedure TPosDict.SaveToStream(stream: TStream);
var
  writer: TWriter;
  ps:PosIndex;
  pid:PosIndexData;
  l:integer;
begin
  writer := TWriter.Create(stream, 4096);
  l:=sizeof(pid.count);
  try
    writer.WriteListBegin;
    for ps in Self.Keys do
      begin
        pid:=Items[ps];
        writer.WriteInteger(ps.chr);
        writer.WriteInteger(ps.pos);
        writer.WriteString(pid.gname);
        writer.WriteString(pid.rname);
        writer.WriteString(pid.promoter);
        writer.Write(pid.count,l);
      end;
    writer.WriteListEnd;
  finally
    writer.Free;
  end;
end;


Метод быстр, гигабайтные данные сохраняются быстро даже в ZIP-файл. А вот считывание
из файла крайне медленно из-за того, что данные добавляются во вновь созданный TDictionary,
происходит хэширование и проверка на уникальность:

procedure TPosDict.LoadFromStream(stream: TStream);
var
  reader: TReader;
  ps:PosIndex;
  pid:PosIndexData;
  l:integer;

begin
  Clear;
  l:=sizeof(pid.count);
  reader := TReader.Create(stream, 9192);
  try
    reader.ReadListBegin;
    while not reader.EndOfList do
    begin
       ps.chr:=reader.ReadInteger;
       ps.pos:=reader.ReadInteger;
       pid.gname:=reader.ReadString;
       pid.rname:=reader.ReadString;
       pid.promoter:=reader.ReadString;
       reader.Read(pid.count,l);
       Add(ps,pid); // вот это всё тормозит!!!
    end;
    reader.ReadListEnd;
  finally
    reader.Free;
  end;
end;


Избежать этого, как я понимаю, нельзя. Но ведь это уже было сделано, когда объект
существовал ранее, все хэши уже были созданы и работали. Появилась идея: можно ли при
сохранении TDictionary как-то сохранить объект целиком, включая хэши, а затем так же
восстановить из файла, чтобы не тратилось время на перехэширование. Ну, или другие
идеи, как убрать бутылочное горло при восстановлении данных.
    

Ответы

Ответ 1

Особенность TDictionary в том, что когда заканчивается ёмкость под хэши, он увеличивает
размер и в этот момент происходит перехэширование всей имеющийся (на данный момент)
коллекции. Поэтому если заранее примерно известен размер коллекции, то этот размер
умноженный на 2-3 можно поставить в capacity.

Пароль с солью (salt+password)

#безопасность #хеширование

Есть ли смысл "солить" пароль несколько раз?
$db_password = $salt.hash_func($salt.hash_func($salt.hash_func($salt.$my_password)))

Или это не повысит эффективность?    

Ответы

Ответ 1

@Knes есть прямой смысл солить несколько раз и использовать несколько разных хэш
алгоритмов. Смысл здесь такой, что радужные таблицы составляются для конкретного хэш
алгоритма, а поскольку соль хранится в открытом доступе то подобрать алгоритм соления
пароля при однократном солении все же можно, а если соление примерно такое:
db_password=hash1(salt1/2+hash2(password+salt2)+salt1/2)

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


Ответ 2

Я думаю что здесь большую роль играет длина и сложность самой соли а не количество
раз ее использования.

Десятичный хэш

#алгоритм #php #хеширование

Числовые ключи в MySQL работают много быстрее, чем строковые. 
Нужно изготовить десятичные числа из любого хэша.
На стэке нашел решение примерно такое:
hexdec(substr(md5($element_id),-15,15)));

Есть ли более изящные методы получения десятичного хэша?
P.S. более изящных методов ведения БД пока что предлагать не нужно.
Первая строка дана только для ориентировки, например, по длине, либо чтобы не возникло
возражения, что шестнадцатиричное число - тоже число.    

Ответы

Ответ 1

Лично мне кажется, что эта задача неразрешима, поскольку все варианты с выделением
фрагмента уникального хэша автоматически теряют свойство уникальности, и не могут использоваться
в качестве ключа.


Что-то похожее на ваш вариант, кстати говоря, делается здесь (на основании хэша sha1).


То есть, вы, конечно, можете воспользоваться своим вариантом  (да и любым другим
вариантом с конвертированием некоторой значимой части уникального хэша), однако рискуете
нарваться на неприятности в случае большого количества записей в базе данных или в
случае, если звезды будут неблагосклонны :)


Тем более, я думаю, что если такое преобразование было бы возможным, то это давным
давно уже было бы реализовано на стороне популярных баз данных, которые допускают строковые
ключи.


Ответ 2

Не очень понимаю, почему это неразрешимая коллизия. Давайте посмотрим спокойно:

Есть набор байтов представляющих из себя некий хэш
Набор байтов однозначно и всегда (взаимно обратимо) транслируется в целое значение
- вопрос только в длине набора байтов.

Пример: есть допустим хэш длиной 8 байт - это всегда и взаимно обратимо можно переложить
на long (Java).
Весь вопрос только упирается в длину целого. В Java этой проблемы не существует -
ибо всегда можно: new BigInteger(byte[] val) и получить целое произвольной длины.


Ответ 3

А не проще вычислять хэш самому? https://code.google.com/p/boyanov/wiki/FNVHash

Поиск наибольшего общего префикса двух строк бинарным поиском

#cpp #алгоритм #хеширование

Пишу сейчас задачу, для которой нужно уметь быстро находить наибольший общий префикс
двух строк. 

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

Полиномиальный хеш как раз позволяет найти сначала хеш всей строки, а потом за O(1)
находить хеш подстроки, что удобно для сравнения этих самых подстрок.

Но есть проблема: мой бинарный поиск напонятно по каким причинам находит неправильную
длину префикса и я никак не могу это отдебагать.

В чём проблема? 

Поиск префикса:

int d(string &a, string &b) {

    StrHash ha(a), hb(b);
    int mid, l = 0, r = min(a.size(), b.size()) - 1;

    while(l < r) {
        mid = (l + r) / 2;
        if(ha.get(0, mid) == hb.get(0, mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    int common;
    ///А тут мы проверяем, нашли мы префикс или нет.
    if(ha.get(0, l) == hb.get(0, l)) common = l + 1;
    else common = 0;

    return common;
}


Тест с багом, находит ответ 0:

s1 = 'aaaaa'
s2 = 'ab'

    

Ответы

Ответ 1

Я нашёл решение. Думаю, это больше всё-таки похоже на костыль, но всё же.

Я предположил, что l в конце работы алгоритма бинарного поиска может быть больше
нужного, на самом деле не знаю, в каком случае, только на единицу. Это я предположил
исходя из того, что в более классической релизации бинарного поиска ответом может быть
как l = m + 1, так и просто m, если ответ был найден ещё до выхода из while.

Заменил в итоге это:

if(ha.get(0, l) == hb.get(0, l)) common = l + 1;
else common = 0;


На это:

int common;
int variant1 = l, variant2 = l - 1;
if(ha.get(0, variant1) == hb.get(0, variant1)) {
    common = variant1 + 1;
} else {
    if(l - 1 >= 0 && ha.get(0, variant2) == hb.get(0, variant2)) {
        common = variant2 + 1;
    } else {
        common = 0;
    }
}

Различные хэши одинаковых строк в node.js и php

#php #javascript #nodejs #хеширование #sha1

Для расчета хэшей в nodejs использую этот скрипт. В php использую стандартную реализацию.
Пишу алгоритм hmac для nodejs. Есть код на php, пытался его продублировать в node,
но возникла проблема при генерации хэша. 

Вот код php: `

$opad = str_repeat(chr(0x5C), 64);
$ipad = str_repeat(chr(0x36), 64);

for ($i = 0; $i < strlen($key); $i++) {

    $opad[$i] = $opad[$i] ^ $key[$i];
    $ipad[$i] = $ipad[$i] ^ $key[$i];

}

return sha1($ipad);`


Строка $ipad


  "�n�³� `�3{G�_p�#�66666666666666666666666666666666666666666666"


Коды символов 


  "248,110,215,194,179,18,221,15,32,96,224,51,123,71,220,95,112,168,35,241,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54"


Выводит "f0146b3c71d411ec5924ded1e47fe73d6db427a0".

В node код такой: 



var opad = Array(64);
var ipad = Array(64);

var opadStr = '';
var ipadStr = '';

for (var i = 0; i < key.length; i++) {

  opad[i] = key.charCodeAt(i) ^ 0x5C;
  ipad[i] = key.charCodeAt(i) ^ 0x36;

}

for(var i = 0; i < 64; i++) {
  opadStr += String.fromCharCode(opad[i]);
  ipadStr += String.fromCharCode(ipad[i]);
}

return sha1(ipadStr);




Строка ipadStr "øn׳Ýà3{GÜ_p¨#ñ66666666666666666666666666666666666666666666"`

Коды символов 


  "248,110,215,194,179,18,221,15,32,96,224,51,123,71,220,95,112,168,35,241,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54,54"


Выводит такой хэш "38e3f69f2d7d0cb8d6672050271a57e8448ec451".

Может, в кодировке дело.
    

Ответы

Ответ 1

Сталкивался с подобными трудностями при написание расчета md5 для js

Да различие в кодировках, JS оперирует внутри UCS-2 или UTF-16, а php использует
ISO-8859-1 (для работы с мультибайтными строками используются функции mb_*)

PHP каждый раз после преобразованиея код->чимвол и обратно оперирует 1 символ есть
1 байт, а JS каждый раз при преобразовании код -> символ дает 2 байта

Я в свое время выкрутился переездом со строк на Uint8Array

Хеши целых чисел в Python

#python #криптография #хеширование #структуры_данных

Добрый день.

Сейчас начал углублённо читать про хеши и хеш-таблицы. И появился один вопрос, который
вызывает у меня недоумение.

Как известно, в питоне хеш от целого числа - само это число. Однако, если я правильно
понимаю, такая хеш-функция должна считаться очень плохой - она совершенно не обладает
свойством лавинности, и хеши от идущих подряд ключей будут идущими подряд числами.

В чём же дело? Я что-то неправильно понимаю о концепции хорошей хеш-функции? Или
в питоновских словарях и множествах не используется напрямую результат функции hash(),
а как-то дополнительно обрабатывается?
    

Ответы

Ответ 1

Встроенная хеш-функция имеет совсем другие задачи, не связанные с криптографией.
Она используется для быстрого и удобного сравнения ключей словарей.


  Hash values are integers. They are used to quickly compare dictionary
  keys during a dictionary lookup. Numeric values that compare equal
  have the same hash value (even if they are of different types, as is
  the case for 1 and 1.0).


По поводу идущих подряд ключей:

In [37]: hash('aaaa')
Out[37]: 5927745366728125705

In [38]: hash('aaab')
Out[38]: 3762861188151674483

In [39]: hash('aaac')
Out[39]: -5197229166136799781


Для "криптографических" целей стоит обратить внимание на модуль hashlib:

In [35]: hashlib.sha512(b'aaa').hexdigest()
Out[35]: 'd6f644b19812e97b5d871658d6d3400ecd4787faeb9b8990c1e7608288664be77257104a58d033bcf1a0e0945ff06468ebe53e2dff36e248424c7273117dac09'

In [36]: hashlib.sha512(b'123').hexdigest()
Out[36]: '3c9909afec25354d551dae21590bb26e38d53f2173b8d3dc3eee4c047e7ab1c1eb8b85103e3be7ba613b31bb5c9c36214dc9f14a42fd7a2fdb84856bca5c44c2'


Пример из доки с использованием "соли":

>>> import os
>>> from hashlib import blake2b
>>> msg = b'some message'
>>> # Calculate the first hash with a random salt.
>>> salt1 = os.urandom(blake2b.SALT_SIZE)
>>> h1 = blake2b(salt=salt1)
>>> h1.update(msg)
>>> # Calculate the second hash with a different random salt.
>>> salt2 = os.urandom(blake2b.SALT_SIZE)
>>> h2 = blake2b(salt=salt2)
>>> h2.update(msg)
>>> # The digests are different.
>>> h1.digest() != h2.digest()
True

Стат сумма, хеширование, контрольная сумма для сравнения двух текстовых строк.

#алгоритм #хеширование

Есть следующая задача, допустим, есть текстовые строки одинаковой длины. 
Допустим, используются только буквы ABCD. Нужно ввести метрику, способ подсчёта контрольной
суммы и тп. (не знаю как более точно обозвать), чтобы можно было сравнивать строки
между собой по их контрольным суммам. 
То есть:
ABCDABCD и ABCDABCC - очень близкие строки с одной заменой. (1)
ABCDABCD и ABCDDABC - тоже очень близкие строки с одной вставкой "D".
Насколько я представляю, нужно иметь на выходе некоторую постоянную и вариабельную
часть. 
Чтобы в первом примере (1) SUM(ABCDABCD)='wtyy45t'.004 а SUM(ABCDABCC)='wtyy45t'.007
(цифры и буквы условны). 
И в тоже время:  SUM(ABCDABCD)='wtyy45t'.004 а SUM(DDACBADB)='yiejq07'.163
Чтобы можно было потом легко сравнивать похожие строки и откидывать совсем разные. 
Буду благодарен за любые ссылки на алгоритмы, предложения, советы. Спасибо.
UPD
Основной момент - различных строк будет несколько сотен тысяч. Нет возможности их
сравнивать между собой по сложным критериям. Хочется группировать их в кластеры по
общей постоянной части контрольной суммы.    

Ответы

Ответ 1

Как уже отметил margosh, вам следует уточнить требуемое понятие похожести, алгоритма
is_strings_similar_like_i_want нет, и подобной функции не найдете даже в пхп. Пока
можно рекомендовать полистать Энциклопедический словарь расстояний, в главе 11 приведены
все известные метрики на множествах строк.


Ответ 2

Есть некие мысли по поводу алгоритма, не уверена что подобное Вам подойдет, но учитывая
все вышесказанное, предложения следующие :

Выяснить длину строки и предел количества символов, которые могут быть отличны (судя
по Вашим пояснениям - 30%)
Поисмвольно вычесть одну строку из другой, если количество "ненулевых" символов в
результате превышает предел и данные символы располагаются вразброс - в строке были
замены, стока по количеству замен отбрасывается, если же ненулевые символы идут строем
- на лицо сдвиг или делеция, и необходимо сохранить позицию первого отличного символа
и продолжить анализ. Соответственно при количестве "ненулевых" символов в результате
меньше предела - строки похожи.
Далее, в случае сдвигов и делеций должен быть цикл, ограниченный пределом количества
отличных символов (Nlim), в котором проверяются : сопадение первого несовпавшего символа
(позиция m) с одним из символов последующих позиций базовой строки (но не более m +
Nlim). В случае совпадения на некоторой позиции r, проверяется совпадение последующих
символов строки m+i с символами базовой строки m+r+i,теоретически, можно вынести эти
куски в отдельные строки и воспользоваться пунктом 2.
Для вставки сверяем символы строки в позиции от m до m+Nlim с символом базовой строки
в позиции m.


Пример : 
вставка : ABCDABCD и ABCDCDABСD, рез. - 00001111, m=4,r=6, позиции 4-7 базовой и
6-9 совпадают
Как быть со строками разной длины - Вам, как автору темы, виднее.

PS: Эти наброски, безусловно, не претендуют на полноту, простоту и быстроту реализации.


Ответ 3

Учитывая то что ваши строки имеют одинаковую длину, то я бы ввел метрику редактирования,
то есть сколько замен букв требуется, для получения одного слова из другого.
ABCDABCD и ABCDABCC - очень близкие строки с одной заменой. (1)
Алгоритм вычисления данной метрики O(LENGTH(str)).


Ответ 4

Если число используемых символов ограничено какой-то разумной величиной N (ну скажем
меньше 16), то лучший способ это трансляция строк в некое длинное целое используя в
качестве метрики позиционный способ записи N-тиричной системе счисления. Скажем ваш
пример с четырьмя символами ABCD - легко ложится под 4-х тиричную систему счисления.
Строка:

ABCDABCD -> 01230123
ABCDABCC -> 01230122

Ну а дальше сравнение целых это уже просто.


Ответ 5

Вопрос, на самом деле, очень хороший! И пока, решение @Barmaleyя самое лучшее. У
меня нет лучшей идеи по этому поводу, разве что только XORить строки с определенной
"солью" и опять же снова вычислять номер каждого символа. Это будет надежнее, но гораздо
дольше, чем "неХОРеные" строки. 

А вообще советую вам смотреть в сторону PHP-функции similar_text() . Эта функция
вычисляет степень похожести двух строк. Посмотрите её сорцы( они, как мне известно
на C++ ), да поймете, как она работает, напишете свою.


Ответ 6

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


Ответ 7

Я думаю, здесь поможет преобразование Барроуза-Уилера.

Можно ли это назвать хеш-таблицей. Если нет то почему ?

#data_structures #структуры_данных #алгоритм #хеширование #cpp

Почитал кормена и написал хеш-таблицу на основе сцепления элементов. Можно ли это
назвать хеш-таблицей и если нет то почему, какие ошибки есть логические ?
node.hpp
#ifndef NODE_HPP
#define NODE_HPP

template 
class list;

template 
class node
{
    private:
        friend class list;

    private:
        node* m_next;
        node* m_prev;
        T m_data;

    public:
        node() :  m_next(0)
                , m_prev(0)
                , m_data(0) {}

        explicit node(T d) :  m_next(0)
                            , m_prev(0)
                            , m_data(d) {}
        T get_data()
        {
            return m_data;
        }
};

#endif // NODE_HPP

list.hpp
#ifndef LIST_HPP
#define LIST_HPP

#include 
#include 

#include "node.hpp"

template 
class list
{
    private:
        node* m_head;
        node* m_tail;
        unsigned m_size;

    public:
        list() :   m_size(0) 
                 , m_head(0)
                 , m_tail(0){}

        node* get_new_node(T d) const;
        node* find(T data) const;
        void insert_at_front(T data);
        void insert_at_back(T data);
        void delete_at_front();
        void delete_at_back();
        bool is_empty() const;
        void print() const;
        node* get_begin() const
        {
            return m_head;
        }
        node* get_end() const
        {
            return m_tail;
        }
        unsigned get_size() const
        {
            return m_size;
        }
};

template 
node* list::get_new_node(T data) const 
{
    node* n = new node(data);
    assert(n != 0);
    return n;
}

template 
bool list::is_empty() const
{
    if(m_head == 0)
    {
        return true;
    }
    return false;
}

template 
void list::print() const 
{
    if(is_empty())
    {
        return;
    }
    node* t = m_head;
    while(t != 0)
    {
        std::cout << t->m_data << " ";
        t = t->m_next;
    }
}

template 
node* list::find(T data) const
{
    if(is_empty())
    {
        return 0;
    }
    node* t = m_head;
    while(t != 0 && t->m_data != data)
    {
        t = t->m_next;
    }
    return t;
}

template 
void list::insert_at_front(T data)
{
    node* n = get_new_node(data);
    if(m_head == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        n->m_next = m_head;
        if(m_head != 0)
        {
            m_head->m_prev = n;
        }
        m_head = n;
        n->m_prev = 0;
        ++m_size;
    }
}

template 
void list::insert_at_back(T data)
{
    node* n = get_new_node(data);
    if(m_tail == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        m_tail->m_next = n;
        n->m_prev = m_tail;
        m_tail = n;
        ++m_size;
    }

}

template 
void list::delete_at_front()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_head->m_next;
        t->m_prev = 0;
        delete m_head;
        m_head = t;
        --m_size;
    }
}

template 
void list::delete_at_back()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_tail->m_prev;
        t->m_next = 0;
        delete m_tail;
        m_tail = t;
        --m_size;
    }
}

#endif // LIST_HPP

hash_table.hpp
#ifndef HASH_TABLE_HPP
#define HASH_TABLE_HPP

#include "list.hpp"

template 
class hash_table
{
    private:
        list** m_table;
        unsigned m_size;

    private:
        int get_hash(int key);

    public:
        explicit hash_table(unsigned);
        T find(const T&, const T&); 
        void insert(const T&, unsigned);
        void remove(const T&);
};

template 
hash_table::hash_table(unsigned size)
{
    m_size = size;
    m_table = new list*[m_size];
    for(int i = 0; i < m_size; ++i)
    {
        m_table[i] = new list();
    }
}

template 
int hash_table::get_hash(int key)
{
    return (key % m_size);
}

template 
T hash_table::find(const T& d, const T& i)
{
    int h = get_hash(i);
    node* n = m_table[h]->find(d);
    assert(n != 0);
    return n->get_data();
}

template 
void hash_table::insert(const T& d, unsigned key)
{
    unsigned h = get_hash(key);
    m_table[h]->insert_at_front(d);
}

#endif // HASH_TABLE_HPP

Поправил код find(...)
template 
T hash_table::find(const T& i)
{
    int h = get_hash(i);
    if(m_table[h]->get_begin() != 0)
    {
        return m_table[h]->get_begin()->get_data();
    }
    return 0;
}

но так получается что функция всегда возвращает только голову списка а если есть
коллизия то этот случай не учитывается ... ?    

Ответы

Ответ 1

Есть несколько замечаний по реализации:




Непонятна сигнатура find(T, T). Почему не find(Key)?


Непонятно ваше разделение  для элементов хэш-таблицы. То есть, сигнатуры
методов должны выглядеть как insert(Key, Value) / find(Key) / remove(Key), либо как
insert(Value) / find(Value) / remove(Value) для случая, когда в хэш-таблице хранятся
не пары ключ-значение, а сами значения. Других вариантов нет.


Не предложена имплементация remove(T). Вместо траты времени на реализацию своего
std::list, лучше бы уж написали метод удаления элементов из хэш-таблицы.


Крайне странное решение, в котором вызов функции find() coredump'ится в случае отсутствующего
в хэш-таблице значения.


Вообще, предложенный код, за исключением последних пятнадцати строчек, не имеет к
хэш-таблицам никакого отношения, а просто предлагает какой-то неочевидный способ реализации
аналога std::list. Решение с наследованием node ← list, кстати, кажется очень
странным.




А так, ну да, обычная хэш-таблица с chaining'ом для резолвинга коллизий.


Ответ 2

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

Все эти три операции я  вижу. Правда было бы  не плохо перегрузить operator [] (что
бы реализовать интерфейс "массива").
Меня  только смущает порядок параметров в функции вставки. Я думаю, ключ должен идти
первым.
Обязательно напишите тестовые примеры и проверьте, что бы Ваша таблица работала как
нужно.

Как получить хэш от произвольного класса для unordered контейнера?

#cpp #хеширование

Для того чтобы использовать в качестве ключа собственный класс в unordered_map (к
примеру) необходимо определить хэш функцию. Пример с cppreference.com

template<>
struct hash
{
    typedef S argument_type;
    typedef std::size_t result_type;

    result_type operator()(argument_type const& s) const
    {
        result_type const h1 ( std::hash()(s.first_name) );
        result_type const h2 ( std::hash()(s.last_name) );
        return h1 ^ (h2 << 1);
    }
};


это касается двух полей, меня смущает этот момент h1 ^ (h2 << 1) я видел примеры
без сдвига и теперь не совсем понимаю как мне проецировать этот пример на большее число
полей, по какому правилу. 
Я могу сделать просто h1 ^ h2 ^ ... ^ h(n) ? 
или же каждый последующий хэш мне нужно сдвигать? h1 ^ ( h2 << 1 ) ^ ... ^ ( h(n) << n )?

Не хотелось бы столкнуться с коллизиями, их будет очень сложно обнаружить, но подпортят
работу они значительно.
    

Ответы

Ответ 1

На самом деле, лучше всего стараться «перемешивать» хэшкоды как можно больше. Например,
Jon Skeet приводит такой пример:

result_type hash = (result_type)2166136261;
hash = hash * 16777619 ^ std::hash()(s.first_name);
hash = hash * 16777619 ^ std::hash()(s.second_name);
hash = hash * 16777619 ^ std::hash()(s.third_name);
return hash;


Код

h1 ^ h2 ^ ... ^ h(n)


считается неправильным, потому что довольно часто поля имеют одинаковые значения
и имеют равные хэши (а для целочисленных полей часто в качестве хэша используется само
поле). Поскольку при операции ^ равные значения взаимно уничтожаются, то у нас получается
меньшее количество хэш-значений и соответственно много коллизий.

Также популярный вариант такой:

result_type hash = start;
hash = hash * factor + std::hash()(s.first_name);
hash = hash * factor + std::hash()(s.second_name);
hash = hash * factor + std::hash()(s.third_name);
return hash;


(им пользуется Java и .NET) для подходящего значения start и factor. В качестве factor
обычно используется небольшое простое число, наподобие 13 или там 29. start должно
быть по идее взаимно простым с factor (например, другое простое число, обычно побольше).



Вот хорошая обзорная статья (на английском) по различным методикам вычисления хэша.


Ответ 2

Вот еще вариант по ссылке с использованием boost 

#include 

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

Сравнение хешей строк

#строки #хеширование

Допустимо ли делать выводы о равенстве содержимого строк на основе равенства их хешей?    

Ответы

Ответ 1

В общем случае, хэширование не является взаимно однозначным отображение, то есть
нельзя утверждать, что две разные строки дадут два разных хэша. Возьмем для примера
MD5 хэш. На вход поступает строка произвольной длины. На выходе - хэш длиной 128 бит.
Таким образом, на входе бесконечное множество, а на выходе - конечное. Очевидно, что
в бесконечном множестве найдется бесконечное количество строк, которые дадут один и
тот же хэш.


Ответ 2

Нет, однозначно на основе сравнения кешей можно говорить о неравенстве объектов при
неравенстве кешей. Совпадение кешей говорит о вероятном равенстве кешируемых объектов,
поэтому нужно проверять их равенство непосредственно.


Ответ 3

Конечно. Равенство хэшей означает бинарную эквивалентность содержимого строк. Естественно,
для лексикографического сравнения хэши не подойдут.

Учитывая комментарии о коллизиях, отмечу, что хэш-функция должна быть тщательно выбрана.

Подбор части пароля перебором (brute force attack) по маске и sha-256

#python #python_3x #криптография #хеширование

У меня есть кусок пароля *elp** (вместо звездочек должны быть символы, которые надо
подобрать), но я знаю от него sha256 хеш: 

fda23a72c73c92a1ad61cd18c58961b90c2c127028c8b87fd1a65c5e1f55d17e


Мне надо подобрать из всей этой информации к нему пароль
(если что, пароль helpMe)

я написала кусок программы и не знаю как сделать дальше 

import hashlib
mas = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","1","2","3","4","5","6","7","8","9","0"]

a = b'Hello'
sha = hashlib.sha256(a).hexdigest()

print(sha) 

    

Ответы

Ответ 1

Попробуйте так:

import string    
import hashlib
from itertools import product

def brute_force(mask, hsh, alphabet=string.ascii_letters+string.digits, verbose=False):
    # экранируем фигурные скобки
    # и заменяем '*' на '{}' для последующей подстановки в 'str.format()'
    pwd_pat = mask.replace('{', '{{').replace('}','}}').replace('*', '{}')
    # число звездочек - будем использовать в качестве `product(.., repeat)`
    N = mask.count('*')
    i = 0
    for chars in product(alphabet, repeat=N):
        if verbose:
            i += 1
            if i % 10000 == 0:
                print('Iterations: {}'.format(i))
        if hsh == hashlib.sha256(pwd_pat.format(*chars).encode()).hexdigest():
            return pwd_pat.format(*chars)
    return None


Тест:

hsh = 'fda23a72c73c92a1ad61cd18c58961b90c2c127028c8b87fd1a65c5e1f55d17e'

In [245]: brute_force('*elp**', hsh, verbose=True)
Iterations: 10000
Iterations: 20000
Out[245]: 'helpMe'


Ответ 2

Вариант, который работает с байтами и использует все доступные CPU:

#!/usr/bin/env python3
import hashlib
import itertools
import multiprocessing
import string
from functools import partial

alphabet = string.ascii_lowercase.encode()


def sha256(data):
    return hashlib.sha256(data).digest()


def check_sha256(repls_parent, bytes_format, n, target_sha256):
    for repls in itertools.product(alphabet, repeat=n):
        data = bytes_format % (repls_parent + repls)
        if sha256(data) == target_sha256:
            return data


def brute_force(mask, target_sha256, n_cutoff=4):
    """
    n_cutoff -- number of `*` to process in a worker process
    """
    bytes_format = mask.replace(b'%', b'%%').replace(b'*', b'%c')
    mp_check = partial(check_sha256,
                       bytes_format=bytes_format,
                       n=min(n_cutoff, mask.count(b'*')),
                       target_sha256=target_sha256)
    n = max(0, mask.count(b'*') - n_cutoff)
    all_repls_parent = itertools.product(alphabet, repeat=n)
    with multiprocessing.Pool() as pool:
        for data in pool.imap_unordered(mp_check, all_repls_parent):
            if data is not None:
                return data


Пример:

import binascii

sha256_hex = b'c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a'
passw_bytes = brute_force(b'******t horse battery staple',
                          binascii.unhexlify(sha256_hex))
print(passw_bytes.decode())


Задача распараллеливается, делегированием генерации n_cutoff замен в дочерние процессы.
Задача подходит для вычисления на GPU. Из-за связи sha256 с Bitcoin mining существуют
ASIC, заточенные под вычисление хэшей.

Чтобы отслеживать прогресс, можно tqdm модуль использовать:

from tqdm import tqdm

#...
all_repls_parent = itertools.product(alphabet, repeat=n)
with multiprocessing.Pool() as pool:
    for data in tqdm(pool.imap_unordered(mp_check, all_repls_parent),
                     total=len(alphabet)**n):
        if data is not None:
            return data

Получение hash-а SHA256 многопоточно

#c_sharp #многопоточность #хеширование

Есть файл, файл делится на блоки (последовательности байтов).
Как многопоточно вычислить значение hash-функции SHA256 для каждого блока файла,
используя Thread-ы? 
    

Ответы

Ответ 1

Сначала давайте напишем функцию для одного блока.

public static class Sha256Service
{
    private const long blockSize = 16384;

    public static byte[] CalculateHash(string filename, int blockIndex)
    {
        using (var stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
        using (var hasher = new SHA256Managed())
        {
            stream.Seek(blockIndex * blockSize, SeekOrigin.Begin);
            var buffer = new byte[blockSize];
            var actualLength = stream.Read(buffer, 0, buffer.Length);

            return hasher.ComputeHash(buffer, 0, actualLength);
        }
    }
}


Теперь эту функцию надо вызывать параллельно для каждого блока в файле. Самостоятельно
создавать Thread трудоёмко, я бы использовал PLINQ.

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

var blockCount = (fileSize + blockSize - 1)/blockSize;


Дописываем второй метод для параллельного вызова первого:

public static byte[][] Calculate(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize)/blockSize);
    var result = new byte[blockCount][];

    Parallel.For(0, blockCount, (i) => result[i] = calculate(filename, i));

    return result;
}


Файл будет открыт для чтения в нескольких потоках. Это не представляет проблемы для
RAID-массивов и твердотельных дисков, но, насколько я узнал на одиночных жёстких дисках
производительность будет снижаться.

Если делать через Thread, то код начнёт выглядеть гораздо страшнее. Приблизительно так:

static byte[][] Calculate2(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize) / blockSize);
    var result = new byte[blockCount][];
    var threads = new Thread[blockCount];

    for (int i = 0; i < blockCount; i++)
    {
        var i1 = i;
        threads[i] = new Thread(() => result[i1] = CalculateHash(filename, i1));
        threads[i].Start();
    }

    for (int i = 0; i < blockCount; i++)
        threads[i].Join();

    return result;
}


На что здесь нужно обратить внимание? Во-первых, на то, как хитро дублируется переменная
i внутри первого цикла for. Это известный паттерн для работы с переменными цикла внутри
замыканий. Страшно.

Во-вторых, у Thread нет метода WaitAll, приходится писать такой же почти вручную.

ОТВЕТ НА ДОПОЛНИТЕЛЬНЫЙ ВОПРОС В КОММЕНТАРИИ

Приведённый код мог бы обрабатывать и файлы, большие, чем ОЗУ, если бы не одно «но» —
он создает поток на каждый блок, а у потока размер стека по умолчанию составляет 1
мегабайт.

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

Задание тестовое, и я бы не стал заморачиваться, положив количество потоков равным
4 или 8. Тогда хеши блоков удобнее было бы считать большими кусками, состоящими из
большого количества последовательных блоков. Делать можно было бы в 4 или 8 потоков.
Метод CalculateHash стал бы сложнее:

public static void CalculateHash2(string filename, int inclusiveStartBlock, int exclusiveEndBlock,
byte[][] hashes)
{
    var buffer = new byte[bufferSize];

    using (var stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
    using (var hasher = new SHA256Managed())
    {
        stream.Seek(inclusiveStartBlock * blockSize, SeekOrigin.Begin);

        for (int i = inclusiveStartBlock; i < exclusiveEndBlock; i++)
        {
            var actualLength = stream.Read(buffer, 0, buffer.Length);
            hashes[i] = hasher.ComputeHash(buffer, 0, actualLength);
        }
    }
}


Метод Calcualte для 4-х потоков стал бы выглядеть так:

public static byte[][] Calculate3(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize) / blockSize);
    var result = new byte[blockCount][];
    var thread1 = new Thread(() => CalculateHash2(filename, 0, blockCount/4, result));
    var thread2 = new Thread(() => CalculateHash2(filename, blockCount/4, blockCount/2,
result));
    var thread3 = new Thread(() => CalculateHash2(filename, blockCount/2, 3*blockCount/4,
result));
    var thread4 = new Thread(() => CalculateHash2(filename, 3*blockCount/4, blockCount,
result));

    thread1.Start();
    thread2.Start();
    thread3.Start();
    thread4.Start();

    thread1.Join();
    thread2.Join();
    thread3.Join();
    thread4.Join();

    return result;
}


Считаем количество блоков, выделяем память под хеши, разбиваем все блоки на 4 почти
равные части, и для блоков каждой части считаем хеши в 4-х разных потоках.

Вроде всё.


Ответ 2

Если вам нужно посчитать просто хэши блоков, то нет ничего сложного: читаете по N
байт из файла, скармливаете эти N байт алгоритму и получаете ответ. Каждый поток получает
номер блока и читает байты от N * i до max(N * (i + 1), file_length), где i -- номер
блока, начинающийся с нуля.

Если же вам нужно вычислить хэш для всего файла поблочно, то используйте hash tree
(русская статья содержит описание Tiger tree hash, использующего Tiger hash, но фактически
можно использовать другой алгоритм). Идея состоит в том, что для каждого блока вы вычисляете
хэш, затем вычисляете хэши для каждой пары (или более) и так вверх по дереву, пока
не получите единственный хэш. Этот алгоритм используется в P2P сетях для проверки целостности
файлов.

Опишите подробнее, что именно вам нужно сделать и с чем возникли трудности, и я дополню
ответ.

Сортирует ли примитивы коллекции HashSet()?

#java #хеширование #коллекции

import java.util.HashSet;
import java.util.Set;

public class Main2 {
    public static void main(String[] args) {
        Set intset = new HashSet();
        intset.add(1);
        intset.add(2);
        intset.add(35);
        intset.add(42);
        intset.add(5);
        intset.add(6);
        intset.add(7);
        intset.add(832);
        intset.add(9);
        intset.add(1000);
        intset.add(11);
        intset.add(12);
        intset.add(13);
        intset.add(14);
System.out.println("hash set: "+intset);

    }

}
// Output:
// hash set: [1, 2, 5, 6, 7, 9, 11, 12, 13, 14, 35, 42, 832, 1000]

    

Ответы

Ответ 1

Нет, не сортирует. Вам просто повезло, что числа оказались упорядочены на вашей версии
Java. Вероятно, это связано с тем, что на вашей версии над хэшкодом не делается дополнительных
преобразований, а хэшкод целого числа — это само число. Но никто не гарантирует, будут
делаться преобразования или нет. Естественно, алгоритм хэширования не стохастический:
если один раз получилось упорядочено, то и другой раз получится. Но тем не менее никто
не гарантирует, что порядок сохранится на другой машине или в другой версии Java. К
примеру, Oracle JDK 7u60 выдаёт:

>"C:\Program Files\Java\jdk1.7.0_60\bin\java.exe" Main2
hash set: [1000, 35, 1, 832, 2, 5, 6, 7, 42, 9, 11, 12, 13, 14]


А Oracle JDK 8u60 выдаёт:

>"C:\Program Files\Java\jdk1.8.0_60\bin\java.exe" Main2
hash set: [832, 1, 2, 35, 5, 6, 7, 1000, 9, 42, 11, 12, 13, 14]


У вас, наверно, какая-нибудь Java на андроиде, в которой своя библиотека классов
(порождённая Apache Harmony). В других версиях Java порядок может отличаться.


Ответ 2

Когда вы конкатенируете HashSet со строкой ("hash set: "+intset), коллекция приводится
к строковому типу неявным вызовом метода toString().

Сам метод toString() определен в классе java.util.AbstractCollection, который, в
свою очередь, для перечисления элементов коллекции обращается к java.util.HashSet#iterator.
И вот, что говорит JavaDoc этого метода:

/**
 * Returns an iterator over the elements in this set.  The elements
 * are returned in no particular order.
 */


То есть итерация по элементам множества не обещает какой-либо конкретный порядок.
Кроме того в самом начале JavaDoc класса HashSet мы видим:


  It makes no guarantees as to the iteration order of the set; in particular, it
does not guarantee that the order will remain constant over time.


То есть никаких гарантий на порядок обхода вообще нет, а если вы заметили какой-то
порядок, то он может в следующий раз быть другим.


Ответ 3

Итак, дорогие мои. Отвечаю на собственный вопрос. Все мы ми знаем, или не все, что
HashSet это тотже самое что и HashMap, только у HashSet -> values всегда null. Когда
мы инициализируем HashSet или HashMap с конструктором по умолчанию, то создается масив
на 16 корзин в котором будет содержатся "информация"(!) о hashCode обєкта ключа, которая
будет соответствовать індексу корзины масива, где и будет содержатся ссылка на цельный
обект(пара(ключ и значение)).
Логически получается следующее, что если вы будете в качестве обекта ключа использовать
клас Integer со значением в диапазоне от 0 - 15, то hashCode вам вернет само значение
обєкта Integer, а это значение и будет индексом корзины в масиве к которому и будет
привязана ссылка на целестный об*ект(пара(ключ и значение)).

Уникальный хеш на больше 8 миллионов строк

#c_sharp #алгоритм #хеширование

Есть база с огромным количеством строк. Все строки уникальны. Содержат в себе английские,
русские буквы и цифры, могут содержать спецсимволы. В строке от 1 до N слов.
Вопрос: как можно для каждого сделать уникальный хеш?
Использование long возможно, но необходимо вписаться в рамки int.
Описываться алгоритм будет на c#, по идее для ускорения можно использовать asm, но
над этим думаем. 
    

Ответы

Ответ 1

Допустим, у нас есть случайная хеш-функция, M возможных ее значений и N элементов.
Тогда вероятность, что хеши элементов будут разными, равна 1 × (1 - 1/M) × (1 - 2/M)
× ... × (1 - (N-1)/M) = M! / ((M-N)! × MN). При M = 232 и N = 8 000 000 она будет равна
1,75 × 10-3238.

Для сравнения - вероятность падения метеорита завтра вам на голову больше, чем вероятность
отсутствия коллизий в таких условиях.

Это величина более чем достаточно маленькая чтобы признать перебор хеш-функций в
поисках подходящей невозможным.



Если строки неизвестны вам заранее - на этом можно закончить. Любая функция, которую
бы вы не выбрали, почти наверняка даст коллизии на неизвестном заранее наборе строк.

А вот если строки заранее известны - то алгоритм идеального хеширования для них построить
можно. Делается это так:


Выбираем число бит для "старшей" части хеша. Число бит h даст H=2h разных значений.
Берем любую хеш-функцию, и делим в соответствии с ней исходные строки по H корзинам.
В среднем получим N1 = N/H строк в корзине.
Для каждой корзины подбираем (автоматически, разумеется) отдельную идеальную хеш-функцию
для младших бит хеша. Это будет M1 = M/H разных значений.


Чтобы шаг 3 длился адекватное время, величина M12 должна быть сравнима с N1. Получаем
- M2 / H2 ∽ N / H - то есть надо брать H порядка M2 / N.

Получаем H = 16 384 (h = 14), M1 = 288, N1 = 262 144.

Итого, алгоритм получения хеш-фукции будет такой:


Считаем хеш-функцию 1 по модулю 16 384, запоминаем в переменной h1.
Идем в таблицу, посчитанную заранее, по индексу h1. Получаем параметры для хеш-функции 2.
Считаем хеш-функцию 2 по модулю 262 144, запоминаем в переменной h2.
Считаем (h1 << 18) + h2 - это и есть уникальный хеш.


В качестве хеш-функции 2 надо выбрать что-нибудь параметрическое, чтобы было где
выбирать случайные параметры. То есть тут неплохо подойдет полиноминальный хеш.

В качестве хеш-функции 1 можно выбрать любую хорошую хеш-функцию.

Алгоритм получается довольно быстрым (asm не нужен) - но потребует константной таблицы
килобайт на 32 или 64.


Ответ 2

Обратите внимание на комментарий @Harry!!!


Гарантированную уникальность можно обеспечить только лишь словарем
Любые хэш-функции - обеспечивают лишь высокую вероятность уникальности


Многие спецы непроизвольно путают предметную область использования вероятностных
величин. Если мы работаем с вероятностной величиной, то мы должны, несмотря на величину
вероятности, обрабатывать два исхода "сработало" vs "не сработало". В противном случае
мы должны указать, что создаваемая подсистема на дает 100% гарантии отказа. Простой
пример правильного использования вероятностных величин - алгоритмы сжатия по предсказанию.
Нашли часто повторяющиеся последовательности - хорошо, не нашли - все равно обработали.
Поэтому не нужно "покупаться" на величину, даже столь внушительную, вероятности. Далее
шуточный пример ...

"Упал на голову кирпич"

Небольшое размышление по поводу вероятностей на простом, можно сказать обыденном
событии, которое увы, изредка происходит.
А история такова. Шел мужик по делам возле строийки. На голову упал кирпич. Нет мужика.
Какова была вероятность прожить мужику еще немножко?

Постулаты:


площадь поверхности нашей планеты 510 072 000 км²
1км² = 1000000м²
полщадь суши к площади воды относится примерно 3 к 7
для постройки жилого 12-этажного кирпичного дома требуется 1854288 кирпичей (считал
относительно расчетного для одноэтажного, взял 6 квартир на этаже и 12 этажей, плюс
внес поправку на 2/3, типа экономия)
в году 365*24*60*60 = 31536000 секунд 
с сутках 24*60*60 = 86400 секунд
у обычного человека будет не более 500 жизненных ситуаций, которые побудят его на
то или иное действие
человек пойдет пешком, если путь его составит не более 2км, иначе воспользуется транспортом
человек старше 10 лет пойдет самостоятельно, пусть продолжительность жизни 70 лет,
тогда 60 лет = 1892160000 секунд


Мужик идет в нужном месте, в нужное время, по нужному делу, срывается нужный кирпич,
и в нужный момент совершенно ненужно попадает в голову.
Итак, все события совершаются независимо:  

Теорема умножения вероятностей для независимых событий 

P(AB) = P(A)*P(B) - вероятность одновременного наступления двух независимых событий
равна произведению вероятностей этих событий.

Далее расчет на замечательном Ruby:

v1 = 510072000000000*3/7 # площадь суши в кв.метрах
v2 = 1854288             # количество кирпичей для постройки 12-этажного дома
v3 = 31536000            # количество секунд в году
v4 = 86400               # количество секунд в сутках
v5 = 500                 # жизненных ситуаций
v6 = 2000                # путь в метрах
v7 = 1892160000          # "самостоятельная жизнь в секундах"   

puts "Сколько было вариантов у мужика выжить: #{v1*v2*v3*v4*v5*v6*v7-1}"


Ответ:

Сколько вариантов было у мужика выжить: 2089825832201191353090774690693119999999999999999


Ну или примерная вероятность такого вот попадания была: 10⁻⁴⁹

Правда практически нереально? 

PS. Безусловно все расчеты крайне-крайне приблизителны, цель была осознать порядок
малости вероятностной величины.

Какие есть способы хеширования данных в android?

#java #android #хеширование

Мне необходимо обеспечить защиту своего приложения от копирования. Наткнулся на защиту
самим сервисом google play, там, чтобы каждый раз не производить проверку, данные хешируются
в обычный XML, а для меня это большая лажа, т.к. этот файлик легко достаётся и просматривается
специальными программами и забить лицензию в пиратские копии не составляет труда.  

Далее я придумал свой способ защиты, но данные также хранились в XML, но зашифрованны
специальным способом и для каждого мобильника не подошли бы. Я уже было начал радоваться,
что придумал что-то нормальное, и оно работало, когда я через программу расшарил своё
приложение, оно действительно не запускалось на других телефонах, но была одна беда.
Если я делал бэкап приложения, то данный фал успешно удалялся и прога успешно запускалась
на других телефонах. Отсюда у меня и появилась нужда использовать какой-нибудь файл
для хеширования (может, в папке assets или папке raw), главное, чтобы при бэкапе файлы
не удалялись. Также стал задумываться об использовании 2-х этих методов, но сначала
хотел бы услышать мнение знающих людей. 
    

Ответы

Ответ 1

Если действительно нужно защитить приложение от злоумышленников, то можно использовать,
например, dexprotector.


Ответ 2

Посмотрите вот это:


https://www.eldos.com/sbb/java-xml.php


Или же как вариант, в JAVA использовать AES, а в XML файле хранить что то в шифрованном
виде, а уже сама JAVA пускай расшифровывает

Также можно использовать XSS4J (XML Security Suite for Java) от IBM или XMLCipher

Деревья Меркле. Проверка “листьев” в ее составе

#алгоритм #хеширование #дерево #blockchain

Читаю интернет и не до конца понимаю одну вещь. Есть Дерево Меркля (или Меркле).
Допустим оно имеет N-количество отсортированных "листьев", представляющими блоки данных.
Как проверяется, что конкретный "блок" не находится в дереве?


    

Ответы

Ответ 1

Проверка принадлежности происходит очень просто - считается хеш блока, а потом просто
проверка с хешом во всех листьях. Если есть совпадение, дальше проверяется валидность
самого дерева, проходом от этого листа до корня дерева. Например, если это L2 на вашем
рисунке, тогда проверяется Hash(Hash(0-0), Hash(0-1)), и дальше корневой хеш: Hash(Hash(0),
Hash(1))

Свойства криптографических хеш-функций гарантируют, что произведя всего несколько
простых вычислений хеша над небольшими объемами данных, мы гарантируем, что этот блок
данных действительно входит в хеш в корне дерева.

Можете представить себе, если бы весь блок данных занимал несколько гигабайт, а вам
нужно проверить принадлежность небольшой части, допустим 1 мб.

Еще хочу добавить, что операция проверки блока в дереве, это не то, ради чего используют
дерево Меркля в blockchain-технологиях. Основное преимущество, это очень быстрый пересчет
хеша при поступлении новых данных. А так же быстрый пересчет хеша, при удалении блока
данных.

Пример с биткоин. Майнер непрерывно изменяет несколько байт в блоке, и считает хеш,
что бы получить хеш начинающийся с множества нулей. В это время приходят новые транзакции,
и нужно быстро пересчитать хеш в корне дерева (который является частью блока). Для
этого понадобится всего O(log n) операций пересчета хеша. Если майнер решил выкинуть
транзакцию с блока, и включить другую (с большей комиссией), все так же нужно O(log
n) пересчетов.

Что значит стоимость вычисления при хэшировании пароля?

#php #хеширование

В мане по php столкнулся с такой функцией хэширования password_hash()
в эту функцию передается три аргумента: пароль, алгоритм шифрования, дополнительные опции

Дополнительные опции здесь передаются как ассоциативный массив...в одном примере
мана написано так:

$options = [
    'cost' => 11,
    'salt' => mcrypt_create_iv(22, MCRYPT_DEV_URANDOM),
];


Понятно что salt - это соль и под значением понимается функция которая генерирует
эту соль, но мне неясно одно, что такое cost, и какую роль оно играет при шифровании?
    

Ответы

Ответ 1

Вот достаточно развернутый ответ на английском языке. А на Wiki есть описание алгоритма,
где вы можете понять, в каком месте используется cost.

Если коротко, то cost влияет на количество операций при получении хэша, как степень
числа 2. При cost = 11 у вас будет 2**11 повторений алгоритма для вычисления.


Ответ 2

Раньше различные хэширующие алгоритмы как MD5, SHA1 и SHA256 были спроектированы
очень быстрыми и эффективными. При наличии современных технологий и оборудования, стало
довольно просто выяснить результат этих алгоритмов методом "грубой силы" для определения
оригинальных вводимых данных. 

Появилось такое понятие как Cost - стоимость вычисления хеша.

Чем выше стоимость вычисления хэширующего алгоритма, тем больше времени требуется
для взлома его вывода методом "грубой силы".

По сути при cost = 13. Стоимость вычислений равна 2^13 итераций функции формирования
ключа. Стандартный cost = 10 и вычисляется за миллисекунды, увеличение cost на 1, увеличивает
время выполнения примерно в 2 раза. 

Например cost = 13 выполняется за 0.2 ms, а вот cost = 16 уже будет выполнен за несколько
секунд.

Подскажите функцию, похожую на хэш, но короче и без коллизий

#алгоритм #хеширование #множества

Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные
коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K
соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды
сильно различались, а не одним-двумя символами.

Пример:

0    KXBR6Z
1    8FLWGG
2    PAZT73


Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость
не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается
для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по
X имеющимся на руках кодам тоже интересно!

Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами
0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы
из кода получить целое, либо узнать, что код невалиден. 

Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )

P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения,
каждый раз при создании нового, проверяя уникальность.
    

Ответы

Ответ 1

С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать
- это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать
одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно
зашифровать данные блочным или асиметричным шифрованием.
накидал пример кода с подстановкой, результат:
input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188

сам код:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Substitution {
    private static final int NUMBER_COUNT = 10;
    private static final int LETTER_COUNT = 26;
    private static final int ZERO_ASCII_CODE = 48;
    private static final int A_CHAR_ASCII_CODE = 97;

    // substitution tables
    private static final Map> numToChar = new HashMap>(
            NUMBER_COUNT);
    private static final Map charToNum = new HashMap(
            LETTER_COUNT);

    // init tables
    static {
        // add list containers
        for (int i = 0; i < NUMBER_COUNT; i++) {
            numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
                    new LinkedList());
        }

        // init substitution table
        for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {

            // number = (symbol ascii code) mod 9
            Character num = Character
                    .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
            Character ch = Character.valueOf((char) i);

            numToChar.get(num).add(ch);
            charToNum.put(ch, num);
        }
    }

    public static void main(String[] args) {
        System.out.println("dumping straight substitution table");
        for (Character num : numToChar.keySet()) {
            System.out.println("num to char - " + num + ", replacements = "
                    + numToChar.get(num));
        }
        System.out.println();
        System.out.println("dumping reverse substitution table");
        for (Character ch : charToNum.keySet()) {
            System.out.println("char to num - " + ch + ", replacements = "
                    + charToNum.get(ch));
        }

        // test
        String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
        String r = null;
        for (int i = 0; i < nums.length; i++) {
            r = decode(nums[i], true);
            System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
                    + " / " + decode(r, false));
        }

    }

    public static String decode(String input, boolean direction) {
        // result buffer
        StringBuilder b = new StringBuilder(input.length());

        // ensure all latters are in lower case
        String data = input.toLowerCase();

        // store indexes (determines which letter to use when coding a number)
        Map indexes = new HashMap();

        // encode string
        for (int i = 0; i < input.length(); i++) {
            b.append(decode(indexes, data.charAt(i), direction));
        }

        return b.toString();
    }

    // straight - number to letter
    // reverse - letter to number
    private static Character decode(Map indexes, char ch,
            boolean direction) {
        // convert character
        Character character = Character.valueOf(ch);
        if (direction) {
            // get list
            List list = numToChar.get(character);

            // get index to use
            Integer index = indexes.get(character);
            if (null == index) {
                index = Integer.valueOf(0);
            }

            // update index map
            int next = index.intValue() + 1;
            if (next == list.size()) {
                next = 0;
            }

            indexes.put(character, Integer.valueOf(next));

            return list.get(index);
        }

        return charToNum.get(character);
    }
}

Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать
код который будет делать подстановки отдельных символов и/или их последовательностей


Ответ 2

В качестве одного из плохих вариантов, который, тем не менее, решает задачу, могу
предложить следующий подход (плох он из соображений, описанных ниже): 



  
  Кодировать исходный номер купона N в системе кодирования Base36.
  Дописывать недостающие нули в начало для того, чтобы получить желаемую длину кода.
  Совершать какие-либо битовые преобразования, чтобы коды для N и N + 1 не выглядели
похожими, сохраняющие биективность и эффективную вычислимость обратной функции.
  



Сама по себе постановка задачи немного странная - требуется найти биективную функцию,
для которой существует эффективно вычислимая обратная функция ("чтобы из кода получить
целое"). В такой постановка любой купон или серийник, выданный пользователю, автоматически
уязвим для для реверсинга.



  Если выгода, получаемая с такого купона / серийника / ... окажется достаточной,
то наверняка найдется человек, который найдет обратную функцию, а следовательно, сможет
проэксплуатировать систему.



Если же снять ограничение на эффективную вычислимость обратной функции, то практически
задача теряет смысл, поскольку организовать проверку валидности для произвольно взятого
кода купона становится на порядок сложнее.



  Нужно опять каким-то образом сравнивать хэши кодов купонов, исключать коллизии
и т.п. Мне кажется, что для кодов типа KXBR6Z можно доказать, что с приемлемой с практической
точки зрения вероятностью этого не получится. Хотя, возможно, здесь я упускаю что-то
очевидное. [?]



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



  Попробуйте представить, например, как проставить купону, полученному с помощью
некоторой функции, статус revoked или invalid. Или, скажем, разрешить использовать
какой-либо купон дважды.



Из референсов, которые могут быть полезны:



  
  Create a set of “coupon codes” based on an algorithm (см. про Partial Key Verification).
  [CPAN] CouponCode.


Ответ 3

У нас две задачи: сгенерировать для каждого купона уникальное число. Это называется
perfect hash. Вторая задача - сделать так, чтобы каждому купону соответствовало число
от 0 до N-1. Как решить обе эти задачи одним алгоритмом, я не представляю, но по отдельности
- вполне.
Код купона состоит из 6 символов, каждый из которых может иметь одно из 36 значений.
То есть код представляет собой шестизначное число в 36-ричной системе счисления! К
счастью, такое число укладывается в 32 бита. Можешь проверить по калькулятору, что
36^6 < 2^32.
unsigned to_hash(const char* coupon)
{
    unsigned hash = 0;
    char c;
    for( int i = 0; i < 6; ++i ) {
        c = coupon[i];
        if( c < 'A' ) {
            c -= '0';
        } else {
            c -= '7';
        }
        hash *= 36;
        hash += c;
    }
    return hash;
}

Теперь вторая задача - нумерация этих хэшей и поиск номера хэша по самому хэшу. Это
очень просто, если заранее составить массив хэшей купонов в возрастающем порядке и
определять индекс бинарным поиском. Если индекс не найден - значит, купон некорректный.
Если заранее составить массив хэшей невозможно, то задача усложняется, но ненамного.
Надо будет использовать индексированный список и сортировку вставками. Но это уже другая
история.


Ответ 4

Без коллизий нельзя (если хеш постоянной длины), на общем наборе данных. Для последовательности
чисел, чем md5 с солью и выделение части хеша необходимой длинны не подходит?
upd:
Если алгоритм на серверной стороне, возьми простое: серию, если таковая есть, и свою
уникальную соль. Проверку-то, снова будешь на сервере выполнять, в чем тогда отличие
от функции. Пример:
Серия: 101010
Код: e25019

Для них на сервере:
Серия:101010
Соль(приватные данные): Yap!
Md5(101010Yap!) = e2501912913cd181d4199bcea5dd401c
Выделил 6 символов. Проверил. И ты не зависишь от коллизий.

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

Зачем нужен контейнер std::map? В чем он обходит hash map?

#cpp #stl #map #хеширование

Зачем (в с++) существует контейнер map, если есть hash_map, который быстрее? Например,
std::map  чем лучше std::unordered_map'a?
    

Ответы

Ответ 1

Нет понятия «лучше» или «хуже», есть различные свойства контейнера.

std::map держит данные в отсортированном по ключу виде, в отличие от std::unordered_map.
Если вам нужно это свойство, вам нужен std::map. Если нет, достаточно и std::unordered_map.

(Как следствие отсортированности, например, в std::map есть функция lower_bound,
которой нет в std::unordered_map.)


Ответ 2

Как видно из самого названия контейнера std::unordered_map элементы этого контейнера
не упорядочены. В то время как элементы контейнера std::map упорядочены в соответствии
с ключом.


Ответ 3

Для hash_map можно задать hash функцию.