Stack Overflow
Stack Overflow

Questions tagged [perfect-hash]

A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.

60 questions
21
votes
7 answers

perfect hash function

I'm attempting to hash the values 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 I need a function that will map them to an array that has a size of 13 without causing any collisions. I've spent several hours thinking this over and googling and can't…
gregghz
  • 3,925
  • 7
  • 40
  • 69
19
votes
8 answers

Is there a way to make this hash lookup any faster?

I have a requirement to (very) quickly process strings of a limited range, tallying their values. The input file is of the form: January 7 March 22 September 87 March 36 and so forth. Because the line widths are identical, I can simply…
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
16
votes
2 answers

Minimal perfect hash function

I have many integers in range [0; 2^63-1]. There is only 10^8 integers, however. There is no duplicates. Full list is known at compile-time but it is just unique random numbers. These numbers never changes. To store one integer explicitly, 8 bytes…
tin_coder
  • 163
  • 1
  • 4
16
votes
8 answers

Fastest possible string key lookup for known set of keys

Consider a lookup function with the following signature, which needs to return an integer for a given string key: int GetValue(string key) { ... } Consider furthermore that the key-value mappings, numbering N, are known in advance when the source…
Pavel Minaev
  • 99,783
  • 25
  • 219
  • 289
16
votes
2 answers

Is it possible to create a Minimal Perfect Hash function without a separate lookup table for a small (<64) set of keys?

I recently read this article Throw away the keys: Easy, Minimal Perfect Hashing about generating a minimal perfect hash table for a known set of keys. The article seems to assume that you need an intermediate table. Is there any other, simpler way…
Anton Lahti
  • 410
  • 3
  • 10
8
votes
3 answers

Convert a string to number and back to string?

I would like to know how I can convert a short ASCII string to a number (int, float, or numeric string). I saw a couple of posts here mentioned perfect hashes which seems like it might be what I need. However, I'm not quite understanding the math…
Xeoncross
  • 55,620
  • 80
  • 262
  • 364
8
votes
4 answers

Is it possible to make a minimal perfect hash function in this situation?

I want to create a Hash Map (or another structure, if you have any suggestions) to store key value pairs. The keys will all be inserted at once at the same time as the map is created, but I don't know what the keys will be (arbitrary length strings)…
Paul
  • 139,544
  • 27
  • 275
  • 264
8
votes
5 answers

Compile time generated function dispatcher with minimal overhead

I'm trying to implement a fast function dispatcher using compile time generated arrays to being able to use it at runtime in O(1). Some lines of code just to clarify: template void f() { // do stuff } // specialized for every managed…
svoltron
  • 365
  • 1
  • 10
8
votes
9 answers

signed to positive near-perfect hash

I have an integer type, say long, whose values are between Long.MIN_VALUE = 0x80...0 (-2^63) and Long.MAX_VALUE = 0x7f...f (2^63 - 1). I want to hash it with ~50% collision to a positive integer of the same type (i.e. between 1 and Long.MAX_VALUE)…
eold
  • 5,972
  • 11
  • 56
  • 75
7
votes
2 answers

Perfect hash function?

While reading the pigeonhole principle on Wikipedia, I come across - "collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid…
user138645
  • 772
  • 1
  • 7
  • 18
6
votes
3 answers

Hash Table lookup - with perfect hash, in C

I have a C-language app where I need to do table lookups. The entries are strings, All are known at the start of runtime. The table is initialized once, and then looked up many times. The table can change, but it's basically as if the app starts…
Cheeso
  • 189,189
  • 101
  • 473
  • 713
6
votes
1 answer

Perfect hash function generator for functions

I have a set of C++ functions. I want to map this functions in an hash table, something like: unordered_map , SomethingElse>, where SomethingElse is not relevant for this question. This set of functions is previously…
justHelloWorld
  • 6,478
  • 8
  • 58
  • 138
6
votes
1 answer

near perfect or perfect hash of memory addresses in c

I have a list of memory addresses from 0xc0003000 to 0xc04a0144 there are many gaps and < 4096 entries in the list. It is known at compile time and I want to make a perfect hash for it. However looking up perfect hashing online gives me…
Digital Powers
  • 460
  • 6
  • 23
5
votes
2 answers

Ultra fast lookup in small sized container of 64-bit integer values using dynamic perfect hashing

I have input keys that can cheaply be converted to a uint64_t (ie, the input contains less than or equal to 64 bits). Each unique key (not yet in the map) will be assigned some data (a pointer to an object). Much like a std::map…
Carlo Wood
  • 5,648
  • 2
  • 35
  • 47
4
votes
2 answers

Perfect Hash Function for Perl (like gperf)?

I'm going to be using a key:value store and would like to create non-collidable hashes in Perl. Is there a Perl module, or function that I can use to generate a non-collidable hash function or table (maybe something like gperf)? I already know my…
EhevuTov
  • 20,205
  • 16
  • 66
  • 71
1
2 3 4