TransWikia.com

How can we customize our own hash function for C++ unordered set to gain a specific order?

Stack Overflow Asked by salazar_12 on November 27, 2021

In competitive coding we face many question where we have to provide the output in an order of input. So, we need to make own hash function. Any idea how could I write my own hash function?

3 Answers

Since implementations of unordered containers use hash tables (they are pretty much required to by the Standard) with separate chaining with linked lists, if you ensure that the number of buckets exceeds the range of your hash function (using reserve()) then it is reasonably likely - though not guaranteed - that elements will be stored in order of their hash value and for elements with the same hash value in insertion order.

I reiterate that this is not guaranted but in a coding competition where know you the implementation you may get away with it.

Also, this is of course inefficient since you will either need to reserve a huge number of buckets, requiring high memory usage, or restrict the range of your hash function resulting in collisions. You would be much better off using the ordered containers.

Answered by ecatmur on November 27, 2021

... you can't. An unordered_set is unordered. Writing your own hash function will not change that. A particular standard library implementation may hold an order for a particular hash function and a particular set of data stored in that unordered_set. But such code will not just not be portable, the order can change simply by adding more stuff to that set.

If you need to provide some output in the order of the input, then you should use a container that preserves the order you give it, like a vector.

Answered by Nicol Bolas on November 27, 2021

How can we customize our own hash function for C++ unordered set to gain a specific order?

You cannot reliably do what you want.

But why don't you use std::set (or std::map) for such a purpose? Look into this C++ reference, and read a good C++ programming book (and the C++11 standard n3337), for more.

We don't know what is your actual use case, but I might suggest making your own class, following the C++ rule of five, and having both a std::map and a std::hash_map for the same mathematical relation.

 class YourClass {
    // incomplete, should follow the rule of five
 private:
    std::map<std::string, long> mapstr;
    std::unordered_map<std::string, long> hashstr;
 public:
    void put(const std::string&str, long n) { 
         mapstr.insert({str,n});
         hashstr.insert({str,n});
    }
 /// etc...
 }; 

Of course, if you are coding a multi-threaded program you'll need to have some std::mutex field in the class above to serialize access using std::lock_guard....

Any idea how could I write my own hash function?

Writing a good enough hash function is generally easy.

Writing a very efficient hash function could still give you a PhD, and you'll find many papers in ACM sponsored conferences on that topic.

Here is a simple and naive hash function on strings:

std::size_t naive_string_hash(const std::string&str) {
   constexpr unsigned k1 = 78139; // a prime number
   constexpr unsigned k2 = 98129; // another prime number
   std::size_t h = 38197; // yet another prime number
   for (char c: str) 
     h = (k1 * h) ^ (k2 * (unsigned)c);
   return h;
}

You might replace the bitwise exclusive or ^ with a + and read about Bézout's identity.

Recommendation: study existing open source code

I strong recommend looking, for inspiration, into the existing open source code in C++ (including the code of GCC and Clang, both being C++ compilers; or of FLTK or Qt) available on websites like github or gitlab. You could need to ask permission to your manager to study such code.

Recommendation : read documentation

I invite you to read the documentation of your C++ compiler (perhaps GCC or Clang), of your linker (perhaps binutils), of your source code editor (I like GNU emacs), of your version control system (e.g. git). If you are allowed to do so, I suggest using a GNU/Linux system (e.g. Debian or Ubuntu) on your computer (because Linux is mostly made of open source components, whose source code you can download and study).

See also http://linuxfromscratch.org/ and https://norvig.com/21-days.html

Answered by Basile Starynkevitch on November 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP