Is it possible to map string to int faster than using hashmap?

by

A hashtable[1] is in principle the fastest way.

You could however compile a Perfect Hash Function given the fact that you know the full domain ahead of time.

With a perfect hash, there need not be a collision, so you can store the hash table in a linear array!

With proper tweaking you can then

  • fit all of the hash elements in a limited space, making direct addressing a potential option
  • have a reverse lookup in O(1)

The ‘old-school’ tool for generating Perfect Hash functions would be gperf(1). The wikipedia lists more resources on the subject.

Because of all the debate I ran a demo:

Downloading NASDAQ ticker symbols and getting 100 random samples from that set, applying gperf as follows:

gperf -e ' \015' -L C++ -7 -C -E -k '*,1,$' -m 100 selection > perfhash.cpp

Results in a hash-value MAX_HASH_VALUE of 157 and a direct string lookup table of as many items. Here’s just the hash function for demonstration purposes:

inline unsigned int Perfect_Hash::hash (register const char *str, register unsigned int len) {
  static const unsigned char asso_values[] = {
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156,  64,  40,   1,  62,   1,
       41,  18,  47,   0,   1,  11,  10,  57,  21,   7,
       14,  13,  24,   3,  33,  89,  11,   0,  19,   5,
       12,   0, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156
    };
  register int hval = len;

  switch (hval) {
      default: hval += asso_values[(unsigned char)str[4]];   /*FALLTHROUGH*/
      case 4:  hval += asso_values[(unsigned char)str[3]];   /*FALLTHROUGH*/
      case 3:  hval += asso_values[(unsigned char)str[2]+1]; /*FALLTHROUGH*/
      case 2:  hval += asso_values[(unsigned char)str[1]];   /*FALLTHROUGH*/
      case 1:  hval += asso_values[(unsigned char)str[0]];   break;
  }
  return hval;
}

It really doesn’t get much more efficient. Do have a look at the full source at github: https://gist.github.com/sehe/5433535

Mind you, this is a perfect hash, too, so there will be no collisions

Q. […] it’s obviosly “DELL”. Such lookup must be significantly faster than “hashmap lookup”.

A: If you use a simple std::map the net effect is prefix search (because lexicographical string comparison shortcuts on the first character mismatch). The same thing goes for binary search in a sorted container.

[1] PS. For 100 strings, a sorted array of string with std::search or std::lower_bound would potentially be as fast/faster due to the improved Locality of Reference. Consult your profile results to see whether this applies.

More Related Contents:

  1. What is the efficient way to count set bits at a position or lower?
  2. Generating m distinct random numbers in the range [0..n-1]
  3. Fastest way to get the integer part of sqrt(n)?
  4. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  5. Which is the fastest algorithm to find prime numbers?
  6. Is there any advantage of using map over unordered_map in case of trivial keys?
  7. Static linking vs dynamic linking
  8. Rounding up to the nearest multiple of a number
  9. Magic number in boost::hash_combine
  10. Efficient string concatenation in C++
  11. Creating all possible k combinations of n items in C++
  12. How do I calculate the week number given a date?
  13. Using scanf() in C++ programs is faster than using cin?
  14. Efficient implementation of log2(__m256d) in AVX2
  15. Matrix multiplication: Small difference in matrix size, large difference in timings
  16. Where can I get a “useful” C++ binary search algorithm?
  17. Relative performance of std::vector vs. std::list vs. std::slist?
  18. Is hash_map part of the STL?
  19. Efficient Cartesian Product algorithm
  20. Printing prime numbers from 1 through 100
  21. Performance of dynamic_cast?
  22. What is the best way to use a HashMap in C++?
  23. Fastest algorithm for primality test [closed]
  24. C++ cout printing slowly
  25. Performance Tradeoff – When is MATLAB better/slower than C/C++
  26. Cut set of a graph, Boost Graph Library
  27. Simple for() loop benchmark takes the same time with any loop bound
  28. New (std::nothrow) vs. New within a try/catch block
  29. C++ most efficient way to convert string to int (faster than atoi)
  30. Finding square root without using sqrt function?

Leave a Comment