Хэши

Для дальнейшего понимания работы git, нам нужно рассмотреть довольно важное понятие хэша. Хэш - это особая свёртка большой структуры в маленькую.

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

Если такая задача встаёт перед нами разово, то можно её решить и так. Но если нам нужно выполнять её регулярно или много раз, тогда уже производительность начинает играть важную роль.

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

Полный перебор будет выглядеть так:

Java
C++
Python

public class Example1_1 {
    public static void main(String[] args) {
        // массив строк
        String[] arr = new String[]{
                "geefewf323ggr343f34f43f4creceferegregf34t",
                "geefewf323ggr343fwe3sdqqxreceferegregf34t",
                "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
                "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
                "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswrefe",
                "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
        };
        // искомая строка
        String target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk";
        // запоминаем время старта программы в наносекундах
        long startTime = System.nanoTime();
        // находим длину искомой строки
        int targetLength = target.length();

        // ищем первую строку
        for (int i = 0; i < arr.length; i++) {
            // проверяем совпадает ли рассматриваемая строка с искомой
            // изначально будем считать, что да
            boolean areEqual = true;
            // сравниваем строки поэлементно
            for (int j = 0; j < Math.min(targetLength, arr[i].length()); j++) {
                if (arr[i].charAt(j) != target.charAt(j)) {
                    // запоминаем, что строки не равны
                    areEqual = false;
                    // завершаем цикл сравнения
                    break;
                }
            }
            // если строки совпали
            if (areEqual) {
                // выводим сообщение об этом
                System.out.println("Элемент массива с индексом " + i + " совпадает с искомой строкой");
            }
        }
        // запоминаем время окончания программы в наносекундах
        long endTime = System.nanoTime();
        // выводим результат в миллисекундах
        System.out.printf("Затраченное время: %.2f мс.", (double) (endTime - startTime) / 1e6);
    }
}

#include <iostream>
#include <chrono>
#include <algorithm>

int main() {
    // массив строк
    std::string arr[] = {
        "geefewf323ggr343f34f43f4creceferegregf3t",
    "geefewf323ggr343fwe3sdqqxreceferegregf34t",
    "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
    "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
    "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswre",
    "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
    };
    // искомая строка
    std::string target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk";
    // размер массива
    int size = 6;

    // запоминаем время старта программы в наносекундах
    auto startTime = std::chrono::system_clock::now();

    // находим длину искомой строки
    int targetLength = target.length();

    // ищем первую строку
    for (int i = 0; i < size; i++) {
        // проверяем совпадает ли рассматриваемая строка с искомой
        // изначально будем считать, что да
        bool areEqual = true;
        // сравниваем строки поэлементно
        for (int j = 0; j < std::min((int)arr[i].length(),targetLength); j++) {
            if (arr[i][j] != target[j]) {
                // запоминаем, что строки не равны
                areEqual = false;
                // завершаем цикл сравнения
                break;
            }
        }
        // если строки совпали
        if (areEqual) {
            // выводим сообщение об этом
            std::cout << "Array element with index " << i << " is equal to target string" << std::endl;
        }
    }
    // запоминаем время окончания программы в наносекундах

    auto endTime = std::chrono::system_clock::now();
    // выводим результат в миллисекундах
    std::chrono::duration<double> elapsed_seconds = endTime - startTime;
    // формируем строку с временем вычисления
    char spentTimeBuffer[100];
    sprintf(spentTimeBuffer, "Spent time: %.2f ms.", elapsed_seconds.count()*1e3);
    //  выводим время
    std::cout  << spentTimeBuffer << std::endl;
    return 0;
}

import timeit

# массив строк
arr = [
    "geefewf323ggr343f34f43f4creceferegregf3t",
    "geefewf323ggr343fwe3sdqqxreceferegregf34t",
    "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
    "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
    "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswre",
    "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
]

# искомая строка
target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk"


# запоминаем время старта программы в наносекундах
start = timeit.default_timer()

# ищем первую строку
for i in range(len(arr)):
    # проверяем совпадает ли рассматриваемая строка с искомой
    # изначально будем считать, что да
    areEqual = True
    # сравниваем строки поэлементно
    for j in range(len(arr[i])):
        if arr[i][j] != target[j]:
            # запоминаем, что строки не равны
            areEqual = False
            # завершаем цикл сравнения
            break
            # если строки совпали
    if areEqual:
        # выводим сообщение об этом
        print("Элемент массива с индексом ", i, " совпадает с искомой строкой")

# запоминаем время окончания программы в наносекундах

stop = timeit.default_timer()
execution_time = stop - start

# выводим результат в миллисекундах
print("Затраченное время: %.3f мс." % (execution_time*1e3,))

Получим:

Элемент массива с индексом 2 совпадает с искомой строкой

Время, затраченное на выполнение :

Java: 18,98 мс.
C++: 2.41 мс.
Python: 0.09 мс.

Времени, которое выдаёт python доверять не стоит, там сложные цепоки оптимизации, поэтому даже просто время исполнения одного и того же кода "плавает".

Теперь учтём, что строки разной длины не могут совпасть

Java
C++
Python

public class Example1_2 {
    public static void main(String[] args) {
        // массив строк
        String[] arr = new String[]{
                "geefewf323ggr343f34f43f4creceferegregf34t",
                "geefewf323ggr343fwe3sdqqxreceferegregf34t",
                "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
                "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
                "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswrefe",
                "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
        };
        // искомая строка
        String target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk";

        // запоминаем время старта программы в наносекундах
        long startTime = System.nanoTime();
        // создаём второй массив длин строк
        int[] lengths = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            lengths[i] = arr[i].length();
        }
        // находим длину искомой строки
        int targetLength = target.length();

        // ищем первую строку
        for (int i = 0; i < arr.length; i++) {
            // если длины строк не совпадают, переходим к следующей
            if (lengths[i] != targetLength)
                // переходим к следующей итерации цикла перебора строк в масиве
                continue;
            // проверяем совпадает ли рассматриваемая строка с искомой
            // изначально будем считать, что да
            boolean areEqual = true;
            // сравниваем строки поэлементно
            for (int j = 0; j < lengths[i]; j++) {
                if (arr[i].charAt(j) != target.charAt(j)) {
                    // запоминаем, что строки не равны
                    areEqual = false;
                    // завершаем цикл сравнения
                    break;
                }
            }
            // если строки совпали
            if (areEqual) {
                // выводим сообщение об этом
                System.out.println("Элемент массива с индексом " + i + " совпадает с искомой строкой");
            }
        }
        // запоминаем время окончания программы в наносекундах
        long endTime = System.nanoTime();
        // выводим результат в миллисекундах
        System.out.printf("Затраченное время: %.2f мс.", (double) (endTime - startTime) / 1e6);
    }
}

#include <iostream>
#include <chrono>

int main() {
    // массив строк
    std::string arr[] = {
        "geefewf323ggr343f34f43f4creceferegregf3t",
    "geefewf323ggr343fwe3sdqqxreceferegregf34t",
    "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
    "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
    "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswre",
    "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
    };
    // искомая строка
    std::string target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk";
    // размер массива
    int size = 6;

    // запоминаем время старта программы в наносекундах
    auto startTime = std::chrono::system_clock::now();
    // создаём второй массив длин строк
    int lengths[size];
    for (int i = 0; i < size; i++) {
        lengths[i] = arr[i].length();
    }
    // находим длину искомой строки
    int targetLength = target.length();

    // ищем первую строку
    for (int i = 0; i < size; i++) {
        // если длины строк не совпадают, переходим к следующей
        if (lengths[i] != targetLength)
            // переходим к следующей итерации цикла перебора строк в масиве
            continue;
        // проверяем совпадает ли рассматриваемая строка с искомой
        // изначально будем считать, что да
        bool areEqual = true;
        // сравниваем строки поэлементно
        for (int j = 0; j < lengths[i]; j++) {
            if (arr[i][j] != target[j]) {
                // запоминаем, что строки не равны
                areEqual = false;
                // завершаем цикл сравнения
                break;
            }
        }
        // если строки совпали
        if (areEqual) {
            // выводим сообщение об этом
            std::cout << "Array element with index " << i << " is equal to target string" << std::endl;
        }
    }
    // запоминаем время окончания программы в наносекундах

    auto endTime = std::chrono::system_clock::now();
    // выводим результат в миллисекундах
    std::chrono::duration<double> elapsed_seconds = endTime - startTime;
    // формируем строку с временем вычисления
    char spentTimeBuffer[100];
    sprintf(spentTimeBuffer, "Spent time: %.2f ms.", elapsed_seconds.count()*1e3);
    //  выводим время
    std::cout  << spentTimeBuffer << std::endl;
    return 0;
}

import timeit

# массив строк
arr = [
    "geefewf323ggr343f34f43f4creceferegregf3t",
    "geefewf323ggr343fwe3sdqqxreceferegregf34t",
    "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk",
    "dsc343c432rbdfbdfbvv4ev45c4wef23wr32r23r2",
    "sdvcewwexewfdsdvgfberwevcdsvcsdfsdfswre",
    "trthtrhtrhtrgsdxczsdfrgf4e5g34gftregfsdsg"
]

# искомая строка
target = "sadxsewwewefkjrk34rk3n99km23kr23re23ndxnk"

# запоминаем время старта программы в наносекундах
start = timeit.default_timer()
# создаём второй массив длин строк
lengths = [0] * len(arr)

for i in range(len(arr)):
    lengths[i] = len(arr[i])

# находим длину искомой строки
targetLength = len(target)

# ищем первую строку
for i in range(len(arr)):
    # если длины строк не совпадают, переходим к следующей
    if lengths[i] != targetLength:
        # переходим к следующей итерации цикла перебора строк в масиве
        continue
    # проверяем совпадает ли рассматриваемая строка с искомой
    # изначально будем считать, что да
    areEqual = True
    # сравниваем строки поэлементно
    for j in range(lengths[i]):
        if arr[i][j] != target[j]:
            # запоминаем, что строки не равны
            areEqual = False
            # завершаем цикл сравнения
            break
            # если строки совпали
    if areEqual:
        # выводим сообщение об этом
        print("Элемент массива с индексом ", i, " совпадает с искомой строкой")

# запоминаем время окончания программы в наносекундах

stop = timeit.default_timer()
execution_time = stop - start

# выводим результат в миллисекундах
print("Затраченное время: %.3f мс." % (execution_time*1e3,))

Получим:

Элемент массива с индексом 2 совпадает с искомой строкой

Время, затраченное на выполнение :

Java: 14,83 мс.
C++: 1.42 мс
Python: 0.047 мс.

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

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

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

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

В этой статье рассказывается, как рассчитать хэш для биткоина с помощью бумажки и ручки. Конечно, там показан пример для начальных блоков биткоина, их хэш считать очень просто. А вот каждый последующий вычисляется всё сложнее, потому что хэш считается по всем блокам, которые уже посчитаны, плюс новая неизвестная последовательность кодов.

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

Git тоже считает хэши. Ему они нужны для быстрого поиска файлов и проверки наличия изменений в них. Для этой задачи разработчики выбрали SHA-1.

Заменим теперь в нашей программе длины строк на хэши. В случае SHA-1 хэш имеет размер $160$ бит. Его отображают при помощи $40$ шестнадцатиричных символов. Такое число не влезает в классические переменные, поэтому использовать его в нашем примере уже не будем. Для программистских задач он абсолютно не подходит, а вот для файлов - вполне. Ниже приведён пример формирования SHA-1 хэша для последовательности байт, соответствующей строке Hello, World!.

В C++ нет готовой функции sha-1, поэтому для её работы, нужно установить библиотеку OpenSSL. Чтобы установить openssl на Windows, придётся очень помучиться, на Linux это проще.

Java
C++
Python

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class Example1_3 {

    // преобразовать массив байтов в строку
    public static String byteArrayToHexString(byte[] b) {
        String result = "";
        // каждый байт переводим в красивое представление
        for (int i = 0; i < b.length; i++) {
            result += Integer.toHexString((b[i] & 0xff) + 0x100).substring(1);
        }
        return result;
    }


    public static void main(String[] args) {
        // исходные данные Hello, World!
        byte[] source = new byte[]{'H', 'e', 'l','l','o',',',' ','W','o','r','l','d','!'};
        // переменная для формирования хэша
        MessageDigest md = null;
        try {
            // получаем объект для формирования хэша
            md = MessageDigest.getInstance("SHA-1");
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        // получаем хэш, как массив байтов
        byte[] res = md.digest(source);
        // выводим строковое представление байт
        System.out.println(byteArrayToHexString(res));
    }
}

#include <openssl/sha.h>
#include <iostream>
#include <iomanip>


// преобразовать массив байтов в строку
std::string byteArrayToHexString(unsigned char b[]) {
    std::stringstream stream;

    // каждый байт переводим в красивое представление
    for (int i = 0; i < SHA_DIGEST_LENGTH; i++) {
        stream << std::hex << (b[i] & 0xff) + 0x100;
    }
    std::string result(stream.str());
    return result;
}



int main()
{
    const unsigned char str[] = "Hello, World!";
    unsigned char hash[SHA_DIGEST_LENGTH]; // == 20

    SHA1(str, sizeof(str) - 1, hash);
    std::cout<<hash<<std::endl;

    // do some stuff with the hash

    return 0;
}

import hashlib
hash_object = hashlib.sha1(b'Hello, World!')
pbHash = hash_object.hexdigest()
print(pbHash)

Получим:

0a0a9f2a6772942557ab5355d76af442f8f65e01

За счёт хэшей git может очень быстро работать с довольно большими по объёму данными. Поэтому нет никакой необходимости что-либо удалять из его внутренней структуры. Грубо говоря, после того, как вы сделаете коммит, его будет очень сложно потерять, особенно, если вы регулярно синхронизируете свой локальный репозиторий с каким-нибудь удалённым, например, с GitHub'ом.

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