[fpc-pascal] Hashmap for integers

[Andreas Schneider]

On Sun, 22 Aug 2010 18:36:23 +0300, "Juha Manninen (gmail)"
<juha.manninen62 at gmail.com> wrote:
> My prog has a big amount of integers, thats why an integer list is not
> enough. 
> A binary search from a sorted list is pretty fast but the problem is
that
> I am adding items to the list and it must be sorted after every
addition.
> 
> My experience from string hashmaps says that the speed difference can be
> huge, compared to any list implementation.

Afaik, inserting items into a sorted List is done via InsertSort, which is
the fastest way (O(n))to go (IMHO), so you do /not/ have to resort the
list. I am not really sure, how else you would implement a hash map ...
internally you always have to have some list like structure, be it an array
or a linked list. A tree wouldn't be really fast for lots of inserts, since
rebalancing a tree isn't that cheap either.
Ok, sure, you could have a huge array of buckets that are either assigned
or not, but IMHO that would waste too much memory or would have too much
overlapping items/hashes.

Also I think "map" is the right term for what the TFPGMap does, even if it
inherits from a list. A mapping is simply a relation from some key to some
data, and thats exactly what TFPGMap does.