Local hash

Seems kinda complicated to be practical

this is my basic take on hash tables.

uniform distribution hash functions can be hard to determine in some cases.

perfect hash functions can be rare, requiring dealing with collisions.

i have yet to come across a lookup table that was too slow and required a hash table.

for large lookup tables, like the 83,000 caves, rockshelters, and huts in caveman, i find that index systems and a simple list work just fine. the index system reduces a search of 83,000 records down to a search of about half a dozen records at most.

i took my first programming class in 1977 as a sophomore in high school. i eventually went on to take software engineering at OSU. and now, 39 years later, i still have yet to use a hash table in a real world app.

Is 32 32-bit masks that are involved in XOR and NAND enough to map any set of 32-bit numbers to any other? Like:

Strictly speaking, no. There are an enormous amount of possible functions that map 32 bits to 32 bits. Think of it in truth table form: let's start with a simpler problem: say we were arbitrarily mapping 32-bit values to 1-bit values: true or false.

You may have had to fill in a truth table before. There is one row for each possible input value. That means we would have 2^32 rows. The output is 1 bit. So, you need 2^32 bits, for each bit of output, to store an arbitrary one of all possible truth tables. You have 32 bits of output, so that's (32 * 2^32) bits, not (32 * 32) bits. Any redundancies in storing the function as a set of masks just reduces the number of functions you can represent further. There's no way to compress all possible functions into a smaller number of bits.

Note: I'm not saying that any particular one of those mappings takes that many bits, depending how you choose to represent them. You could create an awful lot of them if you gave yourself up to a gigabyte of a particular assembly language to work from. But still, there would have to be many possible mappings that would be left out, even with all that space.

Of course, you don't really care about the whole 2^32 input set. You only care about a small subset of keys. Depending on the actual number of items you need to store, I don't know, maybe this could work. But I also wonder whether any of this is necessary.

i took my first programming class in 1977 as a sophomore in high school. i eventually went on to take software engineering at OSU. and now, 39 years later, i still have yet to use a hash table in a real world app.

I tried to make it work. I can now get any single mapping of any bit width and levels. I can get 3 mappings together with up to 4 bit x 8 level masks in 7 ms. It takes too long for anything like 30 mappings for 64x60. 2 levels are needed at most for each additional mapping. n n-bit levels will just feed through the input if set to 0.

It's a kind of neural net too because it learns by back-propagation and learns patterns. You can also tell it to avoid a certain output given certain inputs, or to try some other combination that will satisfy the inputs and outputs.

I found another thing which might be useful, which is, keeping track of numbers that have been tried. For an n-bit number, at most 2*n (+1?) entries with 2 n-bit numbers each are needed. One is a mask for bits that have been tried both ways, and the other is the value that's been tried once. E.g., for a 5-bit number, there will be 11 max entries, because anything else is a 1-bit change away from any of these:

00000

00011

00101

01001

01010

01100

10001

10010

10100

11000

11011

https://dl.dropboxusercontent.com/u/109630018/temp/lm/localmap.h

https://dl.dropboxusercontent.com/u/109630018/temp/lm/localmap.cpp

https://dl.dropboxusercontent.com/u/109630018/temp/lm/localmap.h

https://dl.dropboxusercontent.com/u/109630018/temp/lm/localmap.cpp

Links are already dead and this post is just 2 days old.

This is all but trivial to do, and it is one of those ideas which look totally ingenious at first, but which turn out being really, really bad ideas. Unless you do it for curiosity and practice, I strongly advise against it.

Why am I saying this?

first random hash key maps to slot 0, then 1, etc.

You insert two random key/value pairs and want them placed in adjacent buckets. So, the problem is finding a function that maps these two values to adjacent buckets (more precisely, a function that maps x to 0 and y to 1).

Now, you have those two values in your hash table, and you insert the third random value, which should land in bucket 2. You now have the problem of finding a function that maps three values to exactly three other values. See where this is going? Come back to the problem when you insert the 5,000th key/value pair.

So much for what it costs you to do that, but what do you gain? Well... nothing. Exactly nothing. In theory, you have a perfect distribution, which reduces collisions to the absolute minimum (if the number of buckets is greater than the number of keys, that's zero collisions). In practice, you do a lot of work in order to get a guaranteed cache miss on every access.

This is very much the same story as it was with Cuckoo Hashing. When it came up a decade ago, the approach was just an ingenious idea. Best idea since the invention of the wheel. You not only have the same complexity as in a normal hash table, but you have a guaranteed maximum number of accesses for the worst case. That's awesome.

Except the hash function is twice as much work, and you also have a guaranteed two cache misses for every insert and lookup, and except you have a dysproportionally high number of complete rehashes to do. Which means that regardless how awesome it sounds, in practice you're being much, much slower.

Now, let's say you do not insert random keys, but somewhat ordered or correlated keys, and you want to optimize for the case of looking up many keys with a common prefix or such. Well... don't use a hash table! Use a trie or crit-bit tree, or any similar, related thing.

And for anything "less than thousand", just use a vector anyway. Naive, linear search is not as bad as you think once cache-friendliness comes into play, and if you can afford sorting values after insert, two or at most three steps of a binary search (followed by a naive linear search from that point on) will do wonders. You do not even need to touch memory for those two steps of binary search if you cache the quartiles in the container...

i took my first programming class in 1977 as a sophomore in high school. i eventually went on to take software engineering at OSU. and now, 39 years later, i still have yet to use a hash table in a real world app.

Seriously? I find this bizzare, have you never used a dynamic language like python, ruby, or lua? These use hash tables idiomatically lots.

i took my first programming class in 1977 as a sophomore in high school. i eventually went on to take software engineering at OSU. and now, 39 years later, i still have yet to use a hash table in a real world app.

Seriously? I find this bizzare, have you never used a dynamic language like python, ruby, or lua? These use hash tables idiomatically lots.

I don't find it bizarre. I've been a professional developer since the early 1980s and I have never explicitly used a hash table outside of academic exercises. I've never used Lua or Ruby, and if Python uses hashtables to implement its dictionaries, it's completely invisible and that's OK.

I've used a *lot* of std::map<> in C++. It's usually faster than a hash table for most things I need and has the strict weak ordering property, which I also usually need.

std::unordered_map<> is a hash table

So unless you have been learning programming C++ in the last 5 years, you never encountered it.

std::unordered_map<> is a hash table

And it is very new in C++ terms (C++11, it seems).
So unless you have been learning programming C++ in the last 5 years, you never encountered it.

[EDIT: It's possible that it was Boost that provided hash_map, not gcc. Also, the C++ committee proposed unordered_map in 2005, as part of TR1. The STL also had hash_map, and that has been around since 1994.]

No, you're almost certainly right.

I'm pretty sure I've used it, and I abstain from Boost because it's such an awful big dependency -- so it must be in GCC.

If I recall correctly and am not having Korsakoff's syndrome, I even remember it was some modulo-some-prime based implementation. Which made it slightly slower overall (but not much) but rendered it very resilient to bad hash functions and bad input (you could hardly get it to deteriorate even if you tried hard feeding it with deliberately bad hashes).

Fair enough, I just looked at the standard http://en.cppreference.com/w/cpp/container/unordered_map which says C++11.

I learned C++ in the '90s from Stroustrup "The C++ language 3rd edition", and that's what I always used. I never looked around for more, since it covered all my needs, and only using the standard concepts has the nice property that it works everywhere out of the box. (A lot of my software gets build and used by others than me, adding more dependencies is generally bad.) Even today, I haven't yet used the unorderd map in C++ (not needed so far).

I did use hashtables in Java and Python though. For classes that need my own equivalence notion, the "<" ordering of C++ feels simpler to me than the "equals" + "hash". Inventing a hash function is always a bit of a problem, as it is hard to understand how your choice affects performance.

std::unordered_map<> is a hash table. If you don't need to keep the items in your map sorted by key, it's very likely that you can use unordered_map instead of map, and in many cases the resulting code will be faster (e.g., if you have lots of entries (because hash tables have better asymptotic performance), or if key comparisons are expensive).

With "lots" being "several thousand." A std::map<> with a string key uses simple string comparison, so O(1) on the average length of the string keys (almost always very short) and O(log n) searches on the number of keys. Unless you choose a custom string hash and bucket sizes very carefully, or have a huge data set you're mapping, std::map<> with std::string keys will beat std::unordered_map<> every time, in terms of speed. It will also beat it when trying to debug, because the data is ordered making it easier to find missing or incorrect values (I calculate developer time as the most expensive resource I manage).

If your key is an integral value, std::unordered_map<> is sometimes a better bet because of memory allocation characteristics, but metrics are always your friend there. Fortunately, the standard map classes are almost entirely interchangeable at the code level so switching is easy.

For smaller data sets (on the order of hundreds) a std::vector<> almost always beats any other collection in terms of memory and speed. If it's created once and treated read-only it will always beat a std::map<> for lookup speed, but std::map<> usually still has simpler code for the same functionality.

With "lots" being "several thousand." A std::map<> with a string key uses simple string comparison, so O(1) on the average length of the string keys (almost always very short) and O(log n) searches on the number of keys. Unless you choose a custom string hash and bucket sizes very carefully, or have a huge data set you're mapping, std::map<> with std::string keys will beat std::unordered_map<> every time, in terms of speed. It will also beat it when trying to debug, because the data is ordered making it easier to find missing or incorrect values (I calculate developer time as the most expensive resource I manage).

If your key is an integral value, std::unordered_map<> is sometimes a better bet because of memory allocation characteristics, but metrics are always your friend there. Fortunately, the standard map classes are almost entirely interchangeable at the code level so switching is easy.

If anybody knows of a way to keep track of used integers, I would like to know. My method isn't as efficient as I thought I think. Maybe there's multiple ways to encode the same values with that way. E.g... 0m0 01m 101 = 000 010 010 011 101 = 010 011 101 000 = 01m 101 000... Mmm

Hey I made some progress. I tried setting all the mask bits to 1 and it always leads to all 1's irreversibly. If only 1 of the bits is 1, then it cycles back and forth between different ends of the range but doesn't cover all of it.

Basically you can solve for variables.

110 -> 000
	010 -> 001
	111 -> 010
	001 -> 011

	truth table boolean
	i2	i1	i0		o2	o1	o0
	0	0	0		1	1	1
	...
	0	0	1		0	1	1
	1	1	0		0	0	0
	0	1	0		0	0	1
	1	1	1		0	1	0

	//hash fun
	o = (i << 1) | (i >> 31)
	o = o ^ ~(i & m)
	i = o
	//repeat 32

	o0[0] = i[2] ^ ~( i[0] & m0[0] )
	o0[1] = i[0] ^ ~( i[1] & m0[1] )
	o0[2] = i[1] ^ ~( i[2] & m0[2] )
	o1[0] = o0[2] ^ ~( o0[0] & m1[0] )
	o1[1] = o0[0] ^ ~( o0[1] & m1[1] )
	o1[2] = o0[1] ^ ~( o0[2] & m1[2] )
	o2[0] = o1[2] ^ ~( o1[0] & m2[0] )
	o2[1] = o1[0] ^ ~( o1[1] & m2[1] )
	o2[2] = o1[1] ^ ~( o1[2] & m2[2] )

	truth table t ^ ~(i & m)
	t	i	m			t2
	0	0	0			1
	0	0	1			1
	0	1	0			1
	0	1	1			0
	1	0	0			0
	1	0	1			0
	1	1	0			0
	1	1	1			1

	train for 110 -> 000
	o2[0] = 0
	0 = o1[2] ^ ~( o1[0] & m2[0] )
	so o1[2]=0 and ~( o1[0] & m2[0] )=0
	o1[2]=0
	so o1[0]=1 and m2[0]=1
	so o0[2]=0 and ~( o0[0] & m1[0] )=1
	so o0[2]=0 and o0[0]=0 and m1[0]=0
	or o0[2]=0 and o0[0]=1 and m1[0]=0
	or o0[2]=0 and o0[0]=0 and m1[0]=1
	or o0[2]=1 and ~( o0[0] & m1[0] )=0
	so o0[2]=1 and o0[2]=1 and o0[0]=1 and m1[0]=1
	o0[2]=1  and o0[0]=1
	so o0[2]=1 and i[2]=1 and ~( i[0] & m0[0] )=0
	so o0[2]=1 and i[0]=1 and m0[0]=1
	or o0[2]=1 and i[2]=0 and ~( i[0] & m0[0] )=1
	so o0[2]=1 and i[0]=0 and m0[0]=0
	or o0[2]=1 and i[0]=1 and m0[0]=0
	or o0[2]=1 and i[0]=0 and m0[0]=1
	or o1[2]=1 and ~( o1[0] & m2[0] )=1
	so o1[2]=1 and o1[0]=0 and m2[0]=0
	o1[2]=1 and o1[0]=0
	so o1[2]=1 and o0[2]=1 && ~( o0[0] & m1[0] )=1
	or o1[2]=1 and o0[2]=0 && ~( o0[0] & m1[0] )=0
	or o1[2]=1 and o1[0]=1 and m2[0]=0
	o1[2]=1 and o1[0]=1
	so 
	or o1[2]=1 and o1[0]=0 and m2[0]=1
	o1[2]=1 and o1[0]=0
	so o1[2]=1 and o0[2]=1 && ~( o0[0] & m1[0] )=1
	or o1[2]=1 and o0[2]=0 && ~( o0[0] & m1[0] )=0
	etc.

	just pick first one given restrictions, then pick for second applying the new restrictions, 
	and if it doesn't work, back up the last step and try different, and so on

	truth table t ^ ~(i & m)
	t	i	m			t2
	0	0	0			1
	0	0	1			1
	0	1	0			1
	0	1	1			0
	1	0	0			0
	1	0	1			0
	1	1	0			0
	1	1	1			1

			o0[0] = i[2] ^ ~( i[0] & m0[0] )
			o0[1] = i[0] ^ ~( i[1] & m0[1] )
			o0[2] = i[1] ^ ~( i[2] & m0[2] )
			o1[0] = o0[2] ^ ~( o0[0] & m1[0] )
			o1[1] = o0[0] ^ ~( o0[1] & m1[1] )
			o1[2] = o0[1] ^ ~( o0[2] & m1[2] )
			o2[0] = o1[2] ^ ~( o1[0] & m2[0] )
			o2[1] = o1[0] ^ ~( o1[1] & m2[1] )
			o2[2] = o1[1] ^ ~( o1[2] & m2[2] )

			therefore
			o2[0] = o1[2] ^ ~( o1[0] & m2[0] )
			o2[1] = o1[0] ^ ~( o1[1] & m2[1] )
			o2[2] = o1[1] ^ ~( o1[2] & m2[2] )

			therefore
			o2[0] = ( o0[1] ^ ~( o0[2] & m1[2] ) ) ^ ~( o1[0] & m2[0] )
			o2[1] = ( o0[1] ^ ~( o0[2] & m1[2] ) ) ^ ~( o1[1] & m2[1] )
			o2[2] = ( o0[0] ^ ~( o0[1] & m1[1] ) ) ^ ~( o1[2] & m2[2] )

			therefore
			o2[0] = ( o0[1] ^ ~( o0[2] & m1[2] ) ) ^ ~( ( o0[2] ^ ~( o0[0] & m1[0] ) ) & m2[0] )
			o2[1] = ( o0[1] ^ ~( o0[2] & m1[2] ) ) ^ ~( ( o0[0] ^ ~( o0[1] & m1[1] ) ) & m2[1] )
			o2[2] = ( o0[0] ^ ~( o0[1] & m1[1] ) ) ^ ~( ( o0[1] ^ ~( o0[2] & m1[2] ) ) & m2[2] )

			therefore
			o2[0] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( o0[2] & m1[2] ) ) ^ ~( ( o0[2] ^ ~( o0[0] & m1[0] ) ) & m2[0] )
			o2[1] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( o0[2] & m1[2] ) ) ^ ~( ( o0[0] ^ ~( o0[1] & m1[1] ) ) & m2[1] )
			o2[2] = ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( o0[1] & m1[1] ) ) ^ ~( ( o0[1] ^ ~( o0[2] & m1[2] ) ) & m2[2] )

			therefore
			o2[0] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( o0[2] ^ ~( o0[0] & m1[0] ) ) & m2[0] )
			o2[1] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( o0[0] ^ ~( o0[1] & m1[1] ) ) & m2[1] )
			o2[2] = ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) ^ ~( ( o0[1] ^ ~( o0[2] & m1[2] ) ) & m2[2] )

			therefore
			o2[0] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[1] ^ ~( i[2] & m0[2] ) ) ^ ~( o0[0] & m1[0] ) ) & m2[0] )
			o2[1] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( o0[1] & m1[1] ) ) & m2[1] )
			o2[2] = ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) ^ ~( ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( o0[2] & m1[2] ) ) & m2[2] )

			therefore
			o2[0] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[1] ^ ~( i[2] & m0[2] ) ) ^ ~( ( i[2] ^ ~( i[0] & m0[0] ) ) & m1[0] ) ) & m2[0] )
			o2[1] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) & m2[1] )
			o2[2] = ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) ^ ~( ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) & m2[2] )

			and
			o[0] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[1] ^ ~( i[2] & m0[2] ) ) ^ ~( ( i[2] ^ ~( i[0] & m0[0] ) ) & m1[0] ) ) & m2[0] )
			o[1] = ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) ^ ~( ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) & m2[1] )
			o[2] = ( ( i[2] ^ ~( i[0] & m0[0] ) ) ^ ~( ( i[0] ^ ~( i[1] & m0[1] ) ) & m1[1] ) ) ^ ~( ( ( i[0] ^ ~( i[1] & m0[1] ) ) ^ ~( ( i[1] ^ ~( i[2] & m0[2] ) ) & m1[2] ) ) & m2[2] )

A, who cares...