хэш карты что это

Хэш-карта с закрытой адресацией

Ассоциативный массив. Введение

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

1. Пусть нам необходим массив, который состоит из большого числа элементов. Массив имеет размер порядка 2 128 элементов, но хранятся в нём всего около 2 10 – 2 20 штук. Проблема в том, что нужные элементы в массиве располагаются не обособленно, а размазаны по всему массиву, так что выделить подмассив достаточно малого размера и работать с ним не получится. Создать массив размера 2 128 мы тоже не можем.

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

Решение задачи

Пусть нужно хранить 3 значения, с индексами 1001883726, 4524352321524 и 77656433109. Для этого создадим массив A размером в N раз больше, чем элементов. Как находить это число N не известно пока. Возьмём массив размером 10 элементов.

После этого, вместо индекса будем брать остаток от деления на размер массива (в нашем случае 10). Тогда, первый элемент будет иметь индекс 6, и мы поместим его в массив A[6]. Второй элемент в массив под номером 4, третий под номером 9.

Очевидно, что могут появиться элементы с одинаковым индексом. Пусть теперь мы добавляем элемент с индексом 3776. Элемент A[6] же занят, поэтому мы создаём на месте элемента 6 односвязный список и привязываем новое значение к старому.

Когда элементов станет очень много, мы получим маленький массив длинных односвязных списков. Время доступа снизится до O(n). Чтобы этого избежать, когда массив будет заполнен на X процентов, нужно будет пересобрать массив, увеличив его размер в M раз. Тогда, при хорошем распределении, среднее время доступа будет порядка 1, а длинна каждого односвязного списка будет примерно единицей.

Вы успели заметить, что в таком описании очень много условностей. Начнём разбираться с неизвестными X, M и N.

Начальный размер массива, в принципе, может быть любым, хоть единицей. Нам больше важен коэффициент заполнения X, при котором будет происходить пересборка. Это значение называют load factor. В языке C# это значение равно 0.72, а в Java 0.75. Эти значения получены после анализ большого количества кода и считаются для данных языков оптимальными. Анализ мы проводить не будем, а просто возьмём на веру значение 0.72.

Пересборку будем осуществлять следующим образом: создадим новую карту нового размера, поместим в неё элементы из старого массива, удалим старую карту.

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

В качестве структуры для хранения элементов (её ещё называют корзиной) может быть использован не только односвязный список, но, например, красно-чёрное дерево, или список с пропусками. Тогда в плохом случае сложность опустится всего до log(n).

Описанная нами структура называется ассоциативным массивом с закрытой адресацией. Также существует ассоциативный массив с открытой адресацией. В нём вместо создания односвязного списка, по определённому алгоритму мы ищем пустую ячейку в текущем массиве. Рассмотрим его позднее.

Вторая задача

Мы хотим реализовать структуру, подобную массиву, но в качестве индекса хотим использовать строку. То есть, обращаться к массиву как a[“Pupkin”], а не a[1772634]. Очевидно, что если бы мы могли каждой строке поставить в соответствие число, то тогда можно было бы свести вторую задачу к первой.

Третья задача

Для решения второй и третьей задачи воспользуемся хэшированием.

Как говорит Википедия, Хеширование (иногда «хэшировани», англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).

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

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

Фактически мы производим отображение из почти бесконечного пространства строк (оно ограничено размерами оперативной памяти) в пространство длинных чисел (оно обычно ограничено 64 или 128 битами). Так как мощность множества строк гораздо больше, то отображение будет суръективное, то есть для многих строк хэш-код будет один и тот же. Эта ситуация называется коллизией. Именно поэтому в карте мы будем хранить не хэш-код, а всё значение ключа.

Из этого следует, что ключ должен поддерживать операцию равенства. К счастью, почти все объекты поддерживают эту операцию (исключение, например, это значение NaN, для которого не поддерживается свойство рефлексии a == a).

Хэш-карта. Реализация.

Объявим набор констант. Это значения по умолчанию для нашей хэш-карты.

Структура Entry – пара

Далее, структура для реализации односвязного списка

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

Теперь, собственно, сама структура «хэш-карта».

Для упрощение работы введено ещё одно значение limit. Это целочисленное значение количества элементов, при превышении которого произойдёт пересборка.

Функция создания карты

Здесь мы защищаем пользователя от ввода «плохих» по нашему мнению значений. То есть, минимальное значение элементов массива не может быть меньше INITIAL_SIZE и т.д.

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

Вспомогательная функция rehashUp. Создаём новую карту с новыми размерами, проходим все значения и вставляем их в новую карту.

Поиск элемента. Возвращаем только значение пары

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

Функция, которая проходит по всей карте и применяет функцию f ко всем парам.

Удаление всей карты будем проводить совместно с удалением всех пар. Именно для этого мы создавали freeEntry

Основные преимущества хэш-карты это постоянство скорости вставки, удаления и поиска в среднем случае. Кроме того, ключ в карте не требует реализации операции «больше-меньше», требуется наличие операции равенства и хэш-функции. Из-за этого возникают и свои проблемы. Так как значения хранятся неупорядоченно, то поиск максимума и минимума будут порядка O(n), так как придётся просмотреть все элементы. А если хэш-функция «плохая» и даёт много одинаковых кодов, то скорость сильно снизится.

Источник

Структуры данных в картинках. HashMap

Приветствую вас, хабрачитатели!

Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.

Создание объекта

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).

Добавление элементов

Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).

В моем случае, для ключа со значением »0» метод hashCode() вернул значение 48, в итоге:

При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Для того чтобы продемонстрировать, как заполняется HashMap, добавим еще несколько элементов.

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Footprint
Object size: 376 bytes

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Footprint
Object size: 496 bytes

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Resize и Transfer

Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.

Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.

Если в исходный hashmap добавить, скажем, еще 15 элементов, то в результате размер будет увеличен и распределение элементов изменится.

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Удаление элементов

У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — «А может оно и не надо?«).

Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.

Теперь удалим те же 150 элементов, и снова замерим.

Как видно, размер даже близко не вернулся к исходному. Если есть желание/потребность исправить ситуацию, можно, например, воспользоваться конструктором HashMap(Map).

Итераторы

HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:

Стоит помнить, что если в ходе работы итератора HashMap был изменен (без использования собственным методов итератора), то результат перебора элементов будет непредсказуемым.

Итоги

— Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
— Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);
— Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
— Не синхронизирован.

Ссылки

Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).

Источник

Внутренняя работа HashMap в Java

В этой статье мы увидим, как изнутри работают методы get и put в коллекции HashMap. Какие операции выполняются. Как происходит хеширование. Как значение извлекается по ключу. Как хранятся пары ключ-значение.

Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:

Теперь мы увидим, как все это работает. Для начала мы рассмотрим процесс хеширования.

Хэширование

Здесь я использую свой собственный класс Key и таким образом могу переопределить метод hashCode() для демонстрации различных сценариев. Мой класс Key:

Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.

Этот код создан исключительно для демонстрации. Поскольку HashCode допускает ключ типа null, хэш код null всегда будет равен 0.

Метод hashCode()

Метод equals()

Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.

Корзины (Buckets)

Вычисление индекса в HashMap

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

где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.

HashMap:
хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Вычислить значение ключа <"vishal">. Оно будет сгенерированно, как 118.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

Теперь HashMap выглядит примерно так:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Вычислить значение ключа <"sachin">. Оно будет сгенерированно, как 115.

Создать объект node.

Поместить объект в позицию с индексом 3, если место свободно.

Теперь HashMap выглядит примерно так:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

Вычислить значение ключа <"vaibhav">. Оно будет сгенерированно, как 118.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

В данном случае в позиции с индексом 6 уже существует другой объект, этот случай называется коллизией.

В таком случае проверям с помощью методов hashCode() и equals(), что оба ключа одинаковы.

Если ключи одинаковы, заменить текущее значение новым.

Иначе связать новый и старый объекты с помощью структуры данных «связанный список», указав ссылку на следующий объект в текущем и сохранить оба под индексом 6.

Теперь HashMap выглядит примерно так:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.

Вычислить хэш код объекта <“sachin”>. Он был сгенерирован, как 115.

В нашем случае элемент найден и возвращаемое значение равно 30.

Вычислить хэш код объекта <"vaibhav">. Он был сгенерирован, как 118.

В данном случае он не найден и следующий объект node не равен null.

Если следующий объект node равен null, возвращаем null.

Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.

Изменения в Java 8

Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

Источник

Что такое Хэширование? Под капотом блокчейна

Так что же такое хэширование?

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

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
Input- вводимые данные, hash- хэш

Посмотрим, как работает процесс хэширования. Мы собираемся внести определенные данные. Для этого, мы будем использовать SHA-256 (безопасный алгоритм хэширования из семейства SHA-2, размером 256 бит).

Как видите, в случае SHA-256, независимо от того, насколько объёмные ваши вводимые данные (input), вывод всегда будет иметь фиксированную 256-битную длину. Это крайне необходимо, когда вы имеете дело с огромным количеством данных и транзакций. Таким образом, вместо того, чтобы помнить вводимые данные, которые могут быть огромными, вы можете просто запомнить хэш и отслеживать его. Прежде чем продолжать, необходимо познакомиться с различными свойствами функций хэширования и тем, как они реализуются в блокчейн.

Криптографические хэш-функции

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

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

Свойство 2: Быстрое вычисление
Хэш-функция должна быть способна быстро возвращать хэш-вход. Если процесс не достаточно быстрый, система просто не будет эффективна.

Свойство 3: Сложность обратного вычисления
Сложность обратного вычисления означает, что с учетом H (A) невозможно определить A, где A – вводимые данные и H(А) – хэш. Обратите внимание на использование слова “невозможно” вместо слова “неосуществимо”. Мы уже знаем, что определить исходные данные по их хэш-значению можно. Возьмем пример.

Предположим, вы играете в кости, а итоговое число — это хэш числа, которое появляется из кости. Как вы сможете определить, что такое исходный номер? Просто все, что вам нужно сделать, — это найти хэши всех чисел от 1 до 6 и сравнить. Поскольку хэш-функции детерминированы, хэш конкретного номера всегда будет одним и тем же, поэтому вы можете просто сравнить хэши и узнать исходный номер.

Но это работает только тогда, когда данный объем данных очень мал. Что происходит, когда у вас есть огромный объем данных? Предположим, вы имеете дело с 128-битным хэшем. Единственный метод, с помощью которого вы должны найти исходные данные, — это метод «грубой силы». Метод «грубой силы» означает, что вам нужно выбрать случайный ввод, хэшировать его, а затем сравнить результат с исследуемым хэшем и повторить, пока не найдете совпадение.

Итак, что произойдет, если вы используете этот метод?

Свойство 4: Небольшие изменения в вводимых данных изменяют хэш
Даже если вы внесете небольшие изменения в исходные данные, изменения, которые будут отражены в хэше, будут огромными. Давайте проверим с помощью SHA-256:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

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

Свойство 5: Коллизионная устойчивость
Учитывая два разных типа исходных данных A и B, где H (A) и H (B) являются их соответствующими хэшами, для H (A) не может быть равен H (B). Это означает, что, по большей части, каждый вход будет иметь свой собственный уникальный хэш. Почему мы сказали «по большей части»? Давайте поговорим об интересной концепции под названием «Парадокс дня рождения».

Что такое парадокс дня рождения?
Если вы случайно встречаете незнакомца на улице, шанс, что у вас совпадут даты дней рождений, очень мал. Фактически, если предположить, что все дни года имеют такую же вероятность дня рождения, шансы другого человека, разделяющего ваш день рождения, составляют 1/365 или 0,27%. Другими словами, он действительно низкий.

Однако, к примеру, если собрать 20-30 человек в одной комнате, шансы двух людей, разделяющих тот же день, резко вырастает. На самом деле, шанс для 2 человек 50-50, разделяющих тот же день рождения при таком раскладе.

Как это применяется в хэшировании?
Предположим, у вас есть 128-битный хэш, который имеет 2 ^ 128 различных вероятностей. Используя парадокс дня рождения, у вас есть 50% шанс разбить коллизионную устойчивость sqrt (2 ^ 128) = 2 ^ 64.

Как вы заметили, намного легче разрушить коллизионную устойчивость, нежели найти обратное вычисление хэша. Для этого обычно требуется много времени. Итак, если вы используете такую функцию, как SHA-256, можно с уверенностью предположить, что если H (A) = H (B), то A = B.

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

Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вводные данные x такие, что H (k | x) = Y.

Вероятно, это, выше вашего понимания! Но все в порядке, давайте теперь разберемся с этим определением.

В чем смысл «высокой мин-энтропии»?
Это означает, что распределение, из которого выбрано значение, рассредоточено так, что мы выбираем случайное значение, имеющее незначительную вероятность. В принципе, если вам сказали выбрать число от 1 до 5, это низкое распределение мин-энтропии. Однако, если бы вы выбрали число от 1 до бесконечности, это — высокое распределение мин-энтропии.

Что значит «к|х»?
«|» обозначает конкатенацию. Конкатенация означает объединение двух строк. Например. Если бы я объединила «голубое» и «небо», то результатом было бы «голубоенебо».
Итак, давайте вернемся к определению.

Предположим, у вас есть выходное значение «Y». Если вы выбираете случайное значение «К», невозможно найти значение X, такое, что хэш конкатенации из K и X, выдаст в результате Y.

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

Примеры криптографических хэш-функций:

1. Указатели
2. Связанные списки

Указатели
В программировании указатели — это переменные, в которых хранится адрес другой переменной, независимо от используемого языка программирования.

Например, запись int a = 10 означает, что существует некая переменная «a», хранящая в себе целочисленное значение равное 10. Так выглядит стандартная переменная.

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

Связанные списки
Связанный список является одним из наиболее важных элементов в структурах данных. Структура связанного списка выглядит следующим образом:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
*Head – заголовок; Data – данные; Pointer – указатель; Record – запись; Null – ноль

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

Важно отметить, что указатель внутри каждого блока содержит адрес предыдущего. Так формируется цепочка. Возникает вопрос, что это значит для первого блока в списке и где находится его указатель?

Первый блок называется «блоком генезиса», а его указатель находится в самой системе. Выглядит это следующим образом:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
*H ( ) – Хэшированные указатели изображаются таким образом

Если вам интересно, что означает «хэш-указатель», то мы с радостью поясним.
Как вы уже поняли, именно на этом основана структура блокчейна. Цепочка блоков представляет собой связанный список. Рассмотрим, как устроена структура блокчейна:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
* Hash of previous block header – хэш предыдущего заголовка блока; Merkle Root – Корень Меркла; Transactions – транзакции; Simplified Bitcoin Blockchain – Упрощенный блокчейн Биткоина.

Блокчейн представляет собой связанный список, содержащий данные, а так же указатель хэширования, указывающий на предыдущий блок, создавая таким образов связную цепочку. Что такое хэш-указатель? Он похож на обычный указатель, но вместо того, чтобы просто содержать адрес предыдущего блока, он также содержит хэш данных, находящихся внутри предыдущего блока. Именно эта небольшая настройка делает блокчейн настолько надежным. Представим на секунду, что хакер атакует блок 3 и пытается изменить данные. Из-за свойств хэш-функций даже небольшое изменение в данных сильно изменит хэш. Это означает, что любые незначительные изменения, произведенные в блоке 3, изменят хэш, хранящийся в блоке 2, что, в свою очередь, изменит данные и хэш блока 2, а это приведет к изменениям в блоке 1 и так далее. Цепочка будет полностью изменена, а это невозможно. Но как же выглядит заголовок блока?

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
* Prev_Hash – предыдущий хэш; Tx – транзакция; Tx_Root – корень транзакции; Timestamp – временная отметка; Nonce – уникальный символ.

Заголовок блока состоит из следующих компонентов:

· Версия: номер версии блока
· Время: текущая временная метка
· Текущая сложная цель (См. ниже)
· Хэш предыдущего блока
· Уникальный символ (См. ниже)
· Хэш корня Меркла

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

Что такое Дерево Меркла?

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
Источник: Wikipedia

На приведенной выше диаграмме показано, как выглядит дерево Меркла. В дереве Меркла каждый нелистовой узел является хэшем значений их дочерних узлов.

Листовой узел: Листовые узлы являются узлами в самом нижнем ярусе дерева. Поэтому, следуя приведенной выше схеме, листовыми будут считаться узлы L1, L2, L3 и L4.

Дочерние узлы: Для узла все узлы, находящиеся ниже его уровня и которые входят в него, являются его дочерними узлами. На диаграмме узлы с надписью «Hash 0-0» и «Hash 0-1» являются дочерними узлами узла с надписью «Hash 0».

Корневой узел: единственный узел, находящийся на самом высоком уровне, с надписью «Top Hash» является корневым.

Так какое же отношение Дерево Меркла имеет к блокчейну?
Каждый блок содержит большое количество транзакций. Будет очень неэффективно хранить все данные внутри каждого блока в виде серии. Это сделает поиск какой-либо конкретной операции крайне громоздким и займет много времени. Но время, необходимое для выяснения, на принадлежность конкретной транзакции к этому блоку или нет, значительно сокращается, если Вы используете дерево Меркла.

Давайте посмотрим на пример на следующем Хэш-дереве:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
Изображение предоставлено проектом: Coursera

Теперь предположим, я хочу узнать, принадлежат ли эти данные блоку или нет:

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это

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

хэш карты что это. Смотреть фото хэш карты что это. Смотреть картинку хэш карты что это. Картинка про хэш карты что это. Фото хэш карты что это
Это значительно сокращает время.

Хэширование в майнинге: крипто-головоломки.
Когда мы говорим «майнинг», в основном, это означает поиск нового блока, который будет добавлен в блокчейн. Майнеры всего мира постоянно работают над тем, чтобы убедиться, что цепочка продолжает расти. Раньше людям было проще работать, используя для майнинга лишь свои ноутбуки, но со временем они начали формировать «пулы», объединяя при этом мощность компьютеров и майнеров, что может стать проблемой. Существуют ограничения для каждой криптовалюты, например, для биткоина они составляют 21 миллион. Между созданием каждого блока должен быть определенный временной интервал заданный протоколом. Для биткоина время между созданием блока занимает всего 10 минут. Если бы блокам было разрешено создаваться быстрее, это привело бы к:

Процесс Майнинга

Примечание: в этом разделе мы будем говорить о выработке биткоинов.
Когда протокол Биткоина хочет добавить новый блок в цепочку, майнинг – это процедура, которой он следует. Всякий раз, когда появляется новый блок, все их содержимое сначала хэшируется. Если подобранный хэш больше или равен, установленному протоколом уровню сложности, он добавляется в блокчейн, а все в сообществе признают новый блок.

Однако, это не так просто. Вам должно очень повезти, чтобы получить новый блок таким образом. Так как, именно здесь присваивается уникальный символ. Уникальный символ (nonce) — это одноразовый код, который объединен с хэшем блока. Затем эта строка вновь меняется и сравнивается с уровнем сложности. Если она соответствует уровню сложности, то случайный код изменяется. Это повторяется миллион раз до тех пор, пока требования не будут наконец выполнены. Когда же это происходит, то блок добавляется в цепочку блоков.

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

Помните номер свойства 6 хэш-функций? Удобство использования задачи?
Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вход x таким образом, H (k | x) = Y.

Так что, когда дело доходит до майнинга биткоинов:

• К = Уникальный символ
• x = хэш блока
• Y = цель проблемы

Весь процесс абсолютно случайный, основанный на генерации случайных чисел, следующий протоколу Proof Of Work и означающий:

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *