PureBasic Forums - English

PB 4.40b1

Can someone please help me understand this?

Why would someone use maps instead of linklists and arrays? What are the advantages?

X wrote:Can someone please help me understand this?

Why would someone use maps instead of linklists and arrays? What are the advantages?

Linked lists allows quick insertion but slow search.
Arrays allow quick search (provided they are sorted) but slow insertion (also provided they are sorted).

A hash list (map) allows both quick insertion and search (although not quite as fast as list insertion or sorted array search).

although not quite as fast as list insertion or sorted array search

I agree with you on the list insertion, but I can't on the sorted array search. A hashmap employs a large array, much larger than the total number of expected elements, and chooses a slot in the array for a prospective element by computing a hash on the element's contents. So retrieval is as fast as ArrayName(Hash(<searchedvalue>)). This is about as fast as a search can get and speed doesn't degrade as the number of elements rises. Sorted array searches, on the other hand, require a binary search. If you have one million elements, up to 20 read/compares will be necessary to retrieve the searched element. As the number of elements rises, search times get slower.

netmaestro wrote:. So retrieval is as fast as ArrayName(Hash(<searchedvalue>)). This is about as fast as a search can get and speed doesn't degrade as the number of elements rises. Sorted array searches

That's not quite accurate, hash tables mostly have an O(1) look up but a loaded table or poorly hashed table will eventually degrade toward an O(N) linear search time in the absolute worst case.

In some circumstances a binary search of a sorted array or binary tree will out perform a hashtable, this in mostly dependent upon the size of the table, how loaded the table is and the hidden cost of calculating the hash. So for 10,000 elements a binary search is often faster but compared to 1,000,000 elements there's no comparison.

Yes a hash table need not utilise a large array at all (though most will!), but what it does need to do is employ some mechanism for handling 'collisions' - those instances whereby two or more elements generate the same hash. In PB's map case, a linear search is employed through those elements which generated the hash in question. In the case of my own library, for example, a binary search is employed etc. though at the cost of having to use more memory. All swings and roundabouts!

A hash table is usually an excellent solution in situations where data is being indexed on a text based key etc.

Is it possible to sort a NewMap / hasmap?

If not, is this by design (= standard) or is it "just" missing commands in PB?

I ask this, because I can imagine to use the new HashMaps instead of linked lists, but I need the possibility to sort it by its structured elements....

Thanks!

Yes, it is by design, you can't sort an hashmap (at least not the one used by PureBasic). For temporary sort, if time is not critical, you can create a list from the hashmap and then sort it.

I would say that physically sorting a hash map is out of the question because the hash really defines the ordering of the elements. Start moving elements around and the hash will no longer allow you to look up individual elements.

The internal ordering of the elements will usually bear no relation to the order that you actually added the elements etc.

If you need a separate ordering then you should probably keep a separate list of the keys and order them or keep a list of pointers etc.

**EDIT : too slow!

I haven't had time to look at the new map functions yet.

If it returns the key on insertion then that would make it easy enough to maintain a sorted list.

keyIndex = additem(MyMap(),item)

Though for more flexibility if you could supply your own hash function in a callback that could really help

size = CreateMap(@cbHashFunc(),number of items)

I think the addition of hash tables is a great feature though you generally need the ability to specify the hash function and table size to get any efficiency out of them.

It is possible to merge a hash map and a linked list (not PB native) by making sure that the structured variable that you place in the hash map has a linked list header (*prev and *next pointers). You must manage these pointers manually. But that way, you can look up values either in order (by the list) or by key (with the hash map) without storing the values twice.

idle and netmaestro, I posted an answer to your posts in a new topic: http://www.purebasic.fr/english/viewtop ... 990#297990