Ninazu
@Ninazu

Разновидность MerkleTree с динамической высотой?

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

Что-то похожее на дерево Меркла, только которое строится динамически и для которого не нужно иметь все значения
Root1 = Hash(Value1);
Root2 = Hash(Root1 + Value2);
Root3 = Hash(Root2 + Value3);
Root4 = Hash(Root3 + Value4);


То есть на выходе мы имеем высоту хеша (В нашем случае 4), корневой хеш (В нашем случае Root4) и значение, вхождение которого нужно рекурсивно проверить в этой цепочке (В нашем случае Value2)
Root4->Exist(Value2)

И второй очень важный момент. Можно ли удалять значения из цепочки.
Root3 = Root4->Remove(Value1)
  • Вопрос задан
  • 29 просмотров
Пригласить эксперта
Ответы на вопрос 1
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Есть ли какой-то алгоритм хеширования, позволяющий добавлять и исключать элементы динамически, и проверять вхождение элемента в эту цепочку?
Фильтр Блума (Bloom Filter), пожалуй самый эффективный, но возможны ложноположительные срабатывания.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы