Hacker News Reader

Comment by Sharlin | Hacker News Reader

  def hash(str):
    len(str)

O(1), baby!

View on HN

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.

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.

Re: missing return keyword

Actually, in Python, None is a valid key...

(I'm so sorry. JavaScript has ruined me.)

Any `return c` for some constant is a valid and correct hash function. It just has a lot of collisions and degenerates hash-maps to terrible performance. That was in fact my first thought when I read "simplest hash functions".

That's why I said "probably".

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.

I like that Rust, just like Lisp and Haskell et al also allow any block to return a value, not just functions. So if-then-else and loops etc can do that. It be nice if Python could do that.

Perhaps I should hack up Python to allow that. Would be an interesting little project.

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.

I don't think there are any reasonable use cases for a non-constant-length hash.

Reply on news.ycombinator.com