2
\$\begingroup\$

Here's a constexpr hash function, that will pack a string into the largest unsigned integral type available. So, what do you think?

#include <climits>

#include <cstdint>

#include <utility>

#include <iostream>

namespace detail
{

template <typename T, std::size_t ...I>
constexpr T hash(char const* const s, std::size_t const N,
  std::index_sequence<I...>) noexcept
{
  return ((T(s[I < N ? I : 0]) << ((I < N ? I : 0) * CHAR_BIT)) | ...);
}

}

template <typename T = std::uintmax_t>
constexpr T hash(char const* const s, std::size_t const N) noexcept
{
  return detail::hash<T>(s, N, std::make_index_sequence<sizeof(T)>());
}

template <typename T = std::uintmax_t, std::size_t N>
constexpr T hash(char const(&s)[N]) noexcept
{
  return hash<T>(s, N - 1);
}

int main()
{
  std::cout << (hash("a") == 'a') << std::endl;

  return 0;
}

https://wandbox.org/permlink/KbPiWJc434xYLL3q

\$\endgroup\$
3
\$\begingroup\$

Your code is too complex. With C++17, you can write more complex constexpr functions, so you don't need the variadic template tricks:

template <typename T = std::uintmax_t, std::size_t N>
constexpr T hash(char const(&s)[N]) noexcept
{
  T val{};

  for (size_t i = 0; i < N; ++i)
    val |= s[i] << (i * CHAR_BIT);

  return val;
}

Apart from that, this is a terrible hash function! The output is highly correlated to the input. It will also only hash up to sizeof(T) characters, so long strings with a common prefix might all get the same hash value.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ take one more look at the code, what does std::make_index_sequence<sizeof(T)>() do? \$\endgroup\$ – user1095108 Sep 1 at 19:01
  • \$\begingroup\$ Ah, missed that! \$\endgroup\$ – G. Sliepen Sep 1 at 19:19
  • \$\begingroup\$ The whole idea was to implement a perfect hash for small strings. We are going 128-bit, so it might not be such a bad idea. Even now, it's possible to enable a 128-bit uint by using -std=gnu++17 That's 16 chars. \$\endgroup\$ – user1095108 Sep 1 at 19:26
  • 1
    \$\begingroup\$ Can you clarify in your question what the use case is of this hash function? Because I don't see the point in what basically is a memcpy() from a string into a suitably large int. I wouldn't call it hashing. \$\endgroup\$ – G. Sliepen Sep 1 at 20:26
  • 2
    \$\begingroup\$ How oes this help you avoid a chain of if-comparisons? Please give a concrete example of how you intend to use this hash function. \$\endgroup\$ – G. Sliepen Sep 1 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.