Strings in C++ Switch/Case statements

January 10, 2017

Something that used to bug me—used to, because I am so accustomed to work around it that I rarely notice the problem—is that in neither C nor C++ you can use strings (const char * or std::string) in switch/case statement. Indeed, the switch/case statement works only on integral values (an enum, an integral type such as char and int, or an object type with implicit cast to an integral type). But strings aren’t of integral types!

In pure C, we’re pretty much done for. The C preprocessor is too weak to help us built compile-time expression out of strings (or, more exactly, const char *), and there’sn’t much else in the language to help us. However, things are a bit different in C++.

Read the rest of this entry »


Making a good random table

April 5, 2016

I am still experimenting with hash functions, and I was toying with the Zobrist hash function[1] that is best known for its use in chess engines. The hash function is conceptually simple: you need a large table of random numbers, indexed, in a chess application, by the position on the board of the piece and by the piece itself. To compute a hash for a whole board configuration, you simply xor all the random numbers together. The hard part is choosing the random numbers.

IMG_0405-small

Read the rest of this entry »


…And a Good One (Hash functions, part VI)

November 17, 2015

In the previous entries, we learned that a good hash function for look-ups should disperse bits as much as possible as well as being unpredictable, that is, behave more or less like a pseudo-random number generator. We had a few failed attempts, a few promising ones, and now, a good one.

Read the rest of this entry »


Three (somewhat) Better Functions (Hash functions, part V)

October 27, 2015

Last week’s hash functions—the check-sum, Knuth’s, and gray—produced less than optimal results. A function based only on addition, such as the check-sum, cannot possibly produce very large numbers, and therefore fails to distribute item over a very large table. That’s why there’s a confusion step following the combination step, to spread the bits around the (machine-sized) word.

So the confusion step must explicitly shuffle the bits around (although, not necessarily a permutation) and make sure that the most- and least-significant bits gets thrown around. Let’s try a couple of things!

Read the rest of this entry »


Testing Hash functions (Hash functions, part III)

October 13, 2015

So, this week, let’s have a look at how we will test hash functions. Testing is necessary since it’s not because your hash function looks random that it is sufficiently random to be used for look-up.

stethoscope-small

Read the rest of this entry »


The anatomy of hash functions (Hash functions, part II)

October 6, 2015

Before we go on exploring hash functions for look-up, let’s discuss their basic anatomy. This will give us some vocabulary as well as help us identify what are the important characteristics of good hash functions.

the-anatomy-lesson-small

Read the rest of this entry »


Hash Functions (Part I)

September 29, 2015

Hash tables are a great way of ensuring O(1) access to your data. Well, it does, but as long as the hash function is good.

7e4156dfac4d82e9a5cab4987ecc3a15

But what exactly makes a hash function a good hash function?

Read the rest of this entry »