def hash(str): len(str) O(1), baby!
If you use the identity function as your hashing function then is it O(0) because you are done before you start?
For an arbitrarily long input, you still have to compress it to constant size somehow.
Simplest Hash Functions
51–60 of 62 posts
Re: Simplest Hash Functions
#52def hash(str): len(str) O(1), baby!
You'd probably want 'return len(str)', if this is Python? In any case, for some applications this is indeed a great hash function. Programs like rmlint use it as part of their checks for duplicate files: if files have different lengths, they can't have the same content after all.
Yes, too much Rust :D Eliding the `return` becomes so intuitive after a while that you sort of forget that most other languages require it.
Re: Simplest Hash Functions
#53def hash(str): len(str) O(1), baby!
O(1) only if you're working in a language with length-stored strings (like Pascal[0]), right? In something like C with its generic strings[1], it would surely have to be O(n) since you have to scan the entire string to calculate its length? (I have always been terrible at big-O, mind.) [0] There's probably more of them by now. [1] ie. not a specific length-stored string type.
Yes. But that's a known misfeature of C and no other language does it like that. Plus I kind of meant arbitrary byte strings where you can have embedded zeroes and thus have to know the length.
Re: Simplest Hash Functions
#54Earlier quoted context omitted.
You'd probably want 'return len(str)', if this is Python? In any case, for some applications this is indeed a great hash function. Programs like rmlint use it as part of their checks for duplicate files: if files have different lengths, they can't have the same content after all.
Yes, too much Rust :D Eliding the `return` becomes so intuitive after a while that you sort of forget that most other languages require it.
Haskell and the Lisps also work like this.
Re: Simplest Hash Functions
#55Earlier quoted context omitted.
https://github.com/sahib/rmlint is the one I had in mind. > Those use a rather expensive hash function (you really want to avoid hash collisions), [...] Then we are clearly not thinking of the same kind of software. > but (at least some ten years ago) memory, not processing speed, was the limiting factor. In what I described, IO is the limiting factor. You want to avoid having to read the whole file, if you can. I th…
> https://github.com/sahib/rmlint is the one I had in mind. Ah, right, thanks. I now dimly recall some old project realizing fs-snapshots using hard links, which one could consider some sort of deduplication as well. > I think you are thinking of block level online deduplicators that are integrated into the file system? Indeed, I was.
> Ah, right, thanks. I now dimly recall some old project realizing fs-snapshots using hard links, which one could consider some sort of deduplication as well.
Most modern CoW filesystems also allow you to mark two files as duplicates, but without sharing subsequent mutations between them. Rmlint supports that, too.
Btw, I'm working on adding deduplication to Bcachefs, and because it's extent-based and not blockbased, the logic will look a lot more like rmlint than what you described.
Re: Simplest Hash Functions
#56Earlier quoted context omitted.
It's very very unlikely to get collisions there, but still not impossible. Whenever you map data of arbitrary length (infinite possibilities) to a limited length collisions are possible.
Doesn't even have to be arbitrary length. Whenever you map into a smaller space, you get collisions. The bigger space doesn't have to be infinite.
with a password you may be mapping into a smaller space or a bigger space, because what you want is to get them all same length, but yeah you may in some cases be mapping into a smaller space, hadn't thought of that, although I sort of also think it is unlikely.
But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory.
Re: Simplest Hash Functions
#57Earlier quoted context omitted.
If you use the identity function as your hashing function then is it O(0) because you are done before you start?
For an arbitrarily long input, you still have to compress it to constant size somehow.
Or pad all entries with 0s to an arbitrarily long size. The 0s can be assumed, and not actually stored. Therefore arbitrarily long entries need not be shortened.
Re: Simplest Hash Functions
#58Earlier quoted context omitted.
Doesn't even have to be arbitrary length. Whenever you map into a smaller space, you get collisions. The bigger space doesn't have to be infinite.
with a password you may be mapping into a smaller space or a bigger space, because what you want is to get them all same length, but yeah you may in some cases be mapping into a smaller space, hadn't thought of that, although I sort of also think it is unlikely. But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide e…
For passwords: the input _space_ is bigger. That doesn't say anything about the length of any particular password.
> But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory.
For passowrds, you are not worried so much about two users accidentally getting the same hash, you are worried about people finding a pre-image that hashes to the same output as your user's password.
Re: Simplest Hash Functions
#59Earlier quoted context omitted.
Yes, too much Rust :D Eliding the `return` becomes so intuitive after a while that you sort of forget that most other languages require it.
Haskell and the Lisps also work like this.
Yes, I know, it's the natural way to do it in functional programming. Honestly I doubt there are any FP languages that don't do it like that.
Re: Simplest Hash Functions
#60Earlier quoted context omitted.
For an arbitrarily long input, you still have to compress it to constant size somehow.
Or pad all entries with 0s to an arbitrarily long size. The 0s can be assumed, and not actually stored. Therefore arbitrarily long entries need not be shortened.
I don't think there are any reasonable use cases for a non-constant-length hash.