data structures - in C++, how to handle hash collision in hash map? -

in c++, how handle hash collision in hash map? , how time spend search element if collision occurred?

and, hash function?

there dozens of different ways handle collisions in hash maps depending on system you're using. here few:

1. if use closed addressing, have each item hash linked list of values, of have same hash code, , traverse list looking element in question.
2. if use linear probing, following hash collision start looking @ adjacent buckets until found element looking or empty spot.
3. if use quadratic probing, following hash collision @ elements 1, 3, 6, 10, 15, ..., n(n+1)/2, ... away collision point in search of empty spot or element in question.
4. if use cuckoo hashing, maintain 2 hash tables, displace element collided other table, repeating process until collisions resolved or had rehash.
5. if use dynamic perfect hashing, build perfect hash table elements sharing hash code.

the particular implementation pick you. go whatever simplest. find chained hashing (closed addressing) easiest, if suggestion helps.

as makes hash function, that's dependent on type of data you're storing. hash functions strings different hash codes integers, example. depending on security guarantees want, may want pick cryptographically secure hash sha-256, or simple heuristic linear combination of individual bits. designing hash function quite tricky, , i'd advise doing bit of digging advice on particular structures you're going hashing before coming conclusion.

hope helps!