map Vs simple array

[Sukhbir]

Hi All,

If i have choice to either use simple array(char a[]) or map.
Which one i shall use, whether array or map.
i need to know wich technique will give better performance.
As per my requirement i will insert the element in array/map, find the element based
on index.
I would appreciate your effort if you people could help me by telling as per performace
wise which is better if i have index of each element.

Thanks in Advance

[Alex Edwards]

Hi All,

If i have choice to either use simple array(char a[]) or map.
Which one i shall use, whether array or map.
i need to know wich technique will give better performance.
As per my requirement i will insert the element in array/map, find the element based
on index.
I would appreciate your effort if you people could help me by telling as per performace
wise which is better if i have index of each element.

Thanks in Advance

Arrays are Random Access, which is fairly fast searching.

However, that's only if you know which indice the element is located at. Otherwise you'll have to do a linear search through like-elements to find what you're looking for.

Your best bet would be a map, and the type of map that you use would depend on how you're doing the search.

If you're looking for objects via comparison then I'd use a TreeMap (a map that holds information by key then searches for the element(s) you're looking for by comparing your key with other keys in a tree-like fashion).

You could also use a HashMap which is built for indexing, but I cannot explain that well enough to give a valid example.

[dougy83]

Hi All,
which is better if i have index of each element.

if you have the index, using a standard array is faster in all cases where you can fit the whole array in memory.

Maps are good for associated arrays (e.g. where the index is a string), for sparse arrays (where only a few elements are used, but the index range is large), etc.

Using maps for sparse arrays generally uses (much) less memory than a normal array.

[n1337]

You could also use a HashMap which is built for indexing, but I cannot explain that well enough to give a valid example.

A Hashmap is basically a combination of an array and a list:

Suppose you had a whole bunch of keys. The way a hashmap works is basically, you reduce the keys mod some fairly large prime number (say n). The prime number is essentially the "verticle" size of the hashmap (this is the way I picture it). What I mean by verticle is that, you create an array of size n, and this array has n indices.

So now you have this n element array, where the indices hold elements placed according to their keys mod n. As a (simple) example, let element A have key = 1, and element B have key = 2. Let n = 3. Reducing 1 and 2 (mod 3), we obtain 1 and 2, respectively. So element A will be stored at array index 1, and element B at inex 2. Fairly straight forward.

But what happens when two keys mod n have the same result? For example, suppose element A has key = 5 and element B has key = 8, and n = 3 (just as an example, the keys/n will generally be larger). Then 5 ~ 2 (mod 3) and 8 ~ 2 (mod 3) ("~" means congruent, I don't know how to do a triple-bar equal sign). So we have a collision. That is, to store element A and B, we reduce them mod 3, but in both cases we get a result of 2. So technically both A and B need to be stored at the array index 2. This is a collision. What to do?

This is where lists come in. Basically, the hashmap array is an "array of lists". Thus, index 2 of the array is a list. So element A is added into the list at index 2 of the array, and element B is added onto the same list at index 2 of the array. So index 2 of the hashmap array has the list '(8 5) (in actual fact, it would probably be a list of structures, where each structure contains the element key, as well as certain data, like name, age, student numbers, whatever data you are storing). Hopefully thats not too confusing...

So basically, the hashmap structure is like this verticle array, with horizontal lists (thats how I picture it). You can see that it combines advantages of both arrays and lists. That is, the constant time search in the array allows you to search for a key (mod n) with relative ease. And the constant time resizing of a list allows you to easily add keys. Of course, in the case of an array index having more than one element in the list, you would have to do a search through the list at that index -- but this would still be much more efficient than say, if you used one list containing all the elements.

When the horizontal lists start getting large, you "rehash" the structure (i.e. recreate the hashmap, changing the array size to some larger prime number, and remodding the keys, thus reducing the number of collisions and therefore the horizontal list sizes). This would take some overhead, but it does not need to be done often, so I suppose you could "ammortize" the cost of rehashing (i.e. we don't really need to concern ourselves with this). Plus, likely for your purposes, you can just choose a large prime number and never have to worry about rehashing.

Hope that makes sense!

Cheers

[Alex Edwards]

A Hashmap is basically a combination of an array and a list:

Suppose you had a whole bunch of keys. The way a hashmap works is basically, you reduce the keys mod some fairly large prime number (say n). The prime number is essentially the "verticle" size of the hashmap (this is the way I picture it). What I mean by verticle is that, you create an array of size n, and this array has n indices.

So now you have this n element array, where the indices hold elements placed according to their keys mod n. As a (simple) example, let element A have key = 1, and element B have key = 2. Let n = 3. Reducing 1 and 2 (mod 3), we obtain 1 and 2, respectively. So element A will be stored at array index 1, and element B at inex 2. Fairly straight forward.

But what happens when two keys mod n have the same result? For example, suppose element A has key = 5 and element B has key = 8, and n = 3 (just as an example, the keys/n will generally be larger). Then 5 ~ 2 (mod 3) and 8 ~ 2 (mod 3) ("~" means congruent, I don't know how to do a triple-bar equal sign). So we have a collision. That is, to store element A and B, we reduce them mod 3, but in both cases we get a result of 2. So technically both A and B need to be stored at the array index 2. This is a collision. What to do?

This is where lists come in. Basically, the hashmap array is an "array of lists". Thus, index 2 of the array is a list. So element A is added into the list at index 2 of the array, and element B is added onto the same list at index 2 of the array. So index 2 of the hashmap array has the list '(8 5) (in actual fact, it would probably be a list of structures, where each structure contains the element key, as well as certain data, like name, age, student numbers, whatever data you are storing). Hopefully thats not too confusing...

So basically, the hashmap structure is like this verticle array, with horizontal lists (thats how I picture it). You can see that it combines advantages of both arrays and lists. That is, the constant time search in the array allows you to search for a key (mod n) with relative ease. And the constant time resizing of a list allows you to easily add keys. Of course, in the case of an array index having more than one element in the list, you would have to do a search through the list at that index -- but this would still be much more efficient than say, if you used one list containing all the elements.

When the horizontal lists start getting large, you "rehash" the structure (i.e. recreate the hashmap, changing the array size to some larger prime number, and remodding the keys, thus reducing the number of collisions and therefore the horizontal list sizes). This would take some overhead, but it does not need to be done often, so I suppose you could "ammortize" the cost of rehashing (i.e. we don't really need to concern ourselves with this). Plus, likely for your purposes, you can just choose a large prime number and never have to worry about rehashing.

Hope that makes sense!

Cheers

Hmm... so a HashMap is like an algorithm based map that will combine values of a particular modded number?

For example... it would be someone equivalent to...

Map<int, vector<string> > fakeHashMap = //...

and the inner map would be mapped based on the integer key (or a character-array key in the same way)?