Изменился ли файл (самый быстрый алгоритм хеширования)?

Не, два раза последний не катит. Я бы сохранял три: начало, середина, конец. Вне зависимости от размера файла. Для середины pos = floor(size / 2), если файл в два байта то сохранять первый, первый, второй. если один, то первый, первый, первый. Ну и fseek наше всё.

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

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

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

Смотри почему первый символ бессмысленно сверять - если это скажем скрипт PHP то первый символ скорее всего будет <, если это bash - то #, у файлов LO - P и так далее. Первый символ (байт) зависит от типа файла и у одного и того же типа файла почти всегда будет одинаковым. А разным типам у нас принято давать разные расширения, т.е. у файлов с одинаковыми именами первый символ с вероятностью близкой к 99% будет одинаковым. Нет никакого смысла его сверять - это не дает никакой информации.

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

Как вот это соотносится с этим:

не сильно критичны коллизии.

?

То что тебе предлагают и есть чексумма. Просто коллизий дофига.

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

Для тебя есть два пути - если у тебя быстрый язык, то «придумай» хэш функцию сам - плясать можно от таких вариантов:
Тупо сумма всех байт
Сумма по модулю, если важен размер хэша, к тому же иногда ее быстрее считать
XOR всех байтов - с большой вероятностью может быть быстрее суммы
Любой из предыдущих вариантов, но четные и нечетные байты отдельно - снижаем количество коллизий

Но все это может оказать медленным очень если у тебя какой-нибудь PHP и будет работать в разы дольше md5. В это случае не будет ничего лучше чем тупо протестировать все функции хэша встроенный в язык и выбрать самые быстрые. Никто тебе не даст ответа что это будет на твоих файлах. Так как вычисление одной функции на 1Гб это одно, а вычисление 1024 функций на 1024 файлах по 1Мб - это другое. Отношения размера файлов к их количеству важны.