Хэш-деревом называют представление данных в виде дерева с корнем, ветвями и листьями.
Построение дерева:
- Каждый лист дерева именуется результатом хэш-функции над блоком данных этого листа;
- Каждая ветвь и корень дерева именуется результатами хэш-функции над списком всех имён прямых потомков и блоком связанных данных при наличии таковых.
Хэш-деревья являются обобщённым видом для хэш-списков и хэш-цепочек. Хэш-деревья предоставляют эффективный и безопасный метод проверки структур данных большого размера. Проверка достоверности и принадлежности листа дерева требует обработки данных пропорционально логарифму количества узлов дерева, для хэш-списков необходимо обработать все узлы списка.
Прочие названия и применение хэш-деревьев:
- Деревья Меркле, названы по имени Ральфа Меркле, запатентовавшего идею хэш-деревьев в 1979;
- TTH (Tiger Tree Hashing), алгоритм проверки целостности данных файлов в сетях DC++, Gnutella.
