Breaking a Toy Hash Function

http://twistedoakstudios.com/blog/Post4706_breaking-a-toy-hash-function

by pizza • 13 years ago

213 20 13 years ago

GuiA• 13 years ago

Brilliant. OP, thanks for writing; submitter, thanks for posting.

pcwalton• 13 years ago

"On the other hand, the equivalent imperative code is stupidly hard to get right because you end up mixing everything together in a big jumble. (I spent my time doing other things while the computer did the tedious work.)"

The PL geek in me really likes this nice demonstration of the power of higher order functions, as opposed to C-style for loops, when it comes to getting things done.

tomp• 13 years ago

Wow! I've never before seen C# LINQ in action. I must say, it's amazing! I hope more languages would adopt this.

tehwalrus• 13 years ago

I vaguely remember LINQ from when I had a real job, but this is way cooler. I just remembered it as chained function calls on a database query return (you could do your filtering in C# instead of in the SQL) but this just looks like SQL (or better - python) in C#.

lucian19002• 13 years ago

The syntax in the article desugars to the method calls you remember (which are the common HOFs). Since the calls are lazy, they can also generate SQL when asked to execute.

WickyNilliams• 13 years ago

LINQ comes in many flavours e.g. LINQ to XML, LINQ to Objects. You're talking about LINQ to SQL. The chained function calls are equivalent to the more SQL-style LINQ, it's a matter of personal preference and which sits better given the context. Personally I always prefer the chained methods with lambdas.

However don't let the seemingly chained methods fool you! The great thing about LINQ is that is defers execution, by building an expression tree [1], meaning the code is lazily executed only when needed. And the expression tree means that everything (filtering, projection etc) is done in a single for loop [2]. e.g.

    var results = collection.Select(item => item.Foo).Where(foo => foo < 3);

This builds an expression tree, but no work has been undertaken on our collection. When we attempt to enumerate the results, the expression tree is converted to code (again, as a single for loop, not multiple iterations as the code might seem):

    results.ToList();

It's extremely cool to work with and highly expressive. One of my favourite features of C#

[1] http://blogs.msdn.com/b/charlie/archive/2007/12/09/deferred-...

[2] http://stackoverflow.com/questions/7324033/what-are-the-bene...

zeckalpha• 13 years ago

The Power of Monads!

thecoffman• 13 years ago

I generally program on the Linux platform and use Ruby, Java, a bit of Perl and occasionally C++. In one previous job however, I did Windows development in C#. Whenever I tell people that C# is a seriously awesome language they look at me like I'm crazy; but its true. In many ways Java is still years and years behind C# for a general purpose OO language. It is really a shame that (outside of Mono), C# is trapped over in Windows land.

LINQ is incredibly awesome, expressive, and powerful. I generally prefer the lambda syntax to the more verbal syntax the author has used here, but both are really great and miles ahead of what's available in other, similar languages.

tel• 13 years ago

LINQ exists, to some degree, in the list comprehensions of Python and to a large degree in the for-comprehensions of Scala and many of the Monads of Haskell.

The monadic interfaces can get much more powerful, such as the Logic Monad in Haskell which embeds Prolog-like search.

gklitt• 13 years ago

Fascinating writeup! I enjoy it when a writer thoroughly details an entire thought process like this, instead of just focusing on the end result. This is precisely the type of content that belongs on the HN front page.

jordan0day• 13 years ago

This is also one of the first articles I've seen on hn in a while that had a decent number of comments, all of which were fairly positive and/or insightful.

girvo• 13 years ago

Seriously impressive write-up! I love it, and really want to have a go at doing something like this myself. Where's the best place to start? I know a _tiny_ bit about hashing functions, enough to know not to ever write one myself... ;)

Strilanc3• 13 years ago

You might like the Matasano Crypto Challenge [1], or maybe just a coursera course on crypto [2].

1: http://www.matasano.com/articles/crypto-challenges/ 2: https://www.coursera.org/course/crypto

lccarrasco• 13 years ago

This was really interesting to read, it also made me somewhat nostalgic since I started programming "seriously" thanks to JASS, reading obfuscated JASS code from DotA maps to answer questions in the official forums helped me make many great friends, get a moderator position and collaborating in beta-testing, great experience for my young years :).

tptacek• 13 years ago

This is an excellent writeup. Break a crappy RNG next!

Strilanc3• 13 years ago

http://xkcd.com/221/

- Can't be seeded.

- Fails to use all possible outputs in range.

- Causes philosophical thoughts.

FreakLegion• 13 years ago

Never expected to run into anyone else from wc3c on HN. Salut!

Breaking a Toy Hash Function

Related Stories