Mercurial stores commits as diffs, and still manages to identify commits by hashes.
The storage format keeps the current text, with reverse deltas in the history, but periodically it stores the text of some revisions so the decoding doesn’t get too slow. Mercurial’s data structures seemed to me to be more elegant than Git’s, but Git mostly won, so that’s what I use nowadays.
There’s a paper describing the storage format in detail, but I don’t have a handy link to it right now.
Behind the scenes from Mercurial: The Definitive Guide seems comprehensive. I submitted it.