hash the strings

[nitin1]

i have an array of strings (2D array). i am taking input of strings and that strings can be same with strings which i have inputted before that string. so i want that i don't enter that string which is already being taken into array. so how can i do this thing in my code ? using linear search is costly in my case. thanks in advance.

[deceptikon]

Hash Tables
Hash Functions

[nitin1]

map<string,int> M is really an awsome thing. learnt today from book which you told me one month back. yipeee.. :-) don't know how map work ? how it hash the keys ? secondly, can i say that it is good to learn C++ for these types of implementaions ? because in C, they are very tuff to do in limited time. thanks in advance.

[deceptikon]

don't know how map work ?

Typically it's some form of balanced binary search tree, with red black trees being the most common implementation.

secondly, can i say that it is good to learn C++ for these types of implementaions ?

Using a library is recommended over rolling your own data structures. Whether that results in using a language where the standard library has what you need or linking with a third party library so that you can continue using C is entirely your decision.

[nitin1]

how does it hash each value to a differnet location ? i hope it will definitely have collision problem. yes! i knoe about red black trees. AVL trees can also be implemented using this ? thanks sir.

[deceptikon]

how does it hash each value to a differnet location ?

It doesn't hash anything, the keys are exact matches. For duplicate keys in C++ you'd either use a multimap<> or store a list of values at the same key:

map<string, vector<T>> m;

In C you'd do something similar, but using a third party library or by writing your own tree.

[nitin1]

ohh... multimap is just an map having second argument as vector , can i say this simply for multimap ? and secondly, in C , this is really going to be a difficiult and time taking task so implement our own tree in time constraint ? thirdly, and sir, the space used in map is the sum of spaces used ny keys + values or does it take more than that ?

[deceptikon]

ohh... multimap is just an map having second argument as vector , can i say this simply for multimap ?

No, not at all. std::multimap is a collection that supports duplicate keys, it's not the same thing at all as a std::map with a collection as the value.

in C , this is really going to be a difficiult and time taking task so implement our own tree in time constraint ?

If you're writing it from scratch and don't have experience with those data structures then yes. However, if you rely on a good tutorial things become drastically simpler.

the space used in map is the sum of spaces used ny keys + values or does it take more than that ?

Assuming we're talking about a red black implementation then it takes more space. Usually equal to the cost of two or three pointers (links) and a boolean (red black state). There might be other extraneous fields as well.