www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - is Associative Arrays good for integer type as key?

reply %u <newbie dd.com> writes:
such as

int[short] hashtable;

where KeyType = short, and ValueType = int?

will this work? and as optimized (memory-wise, and CPU-wise)?

Thanks in advance for your conmments.
Nov 14 2006
next sibling parent reply %u <newbie dd.com> writes:
And what's the internal implementation of Associative Arrays for things like:

int[short] hashtable;

Is it a tree, or raw array with linked-list?
Nov 14 2006
parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"%u" <newbie dd.com> wrote in message news:ejdukb$otl$1 digitaldaemon.com...
 And what's the internal implementation of Associative Arrays for things 
 like:

 int[short] hashtable;

 Is it a tree, or raw array with linked-list?

All associative arrays in D, no matter the key or value types, are implemented as a closed-addressed hash table with binary trees at each hash table location to resolve collisions (as opposed to the more common linked-list at each location). If you'd like, you can see how AAs are implemented in /dmd/src/phobos/internal/aaA.d, and you can see how all the hashes are computed for the various types in the phobos/typeinfo directory. For shorts, the hash is simply the value itself.
Nov 14 2006
prev sibling next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
%u wrote:
 such as
 
 int[short] hashtable;
 
 where KeyType = short, and ValueType = int?
 
 will this work?

Have you tried it? Does it work?
 and as optimized (memory-wise, and CPU-wise)?

Depends on how you're using it. Stewart. -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/M d- s:- C++ a->--- UB P+ L E W++ N+++ o K- w++ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y ------END GEEK CODE BLOCK------ My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Nov 17 2006
prev sibling parent Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Wed, 15 Nov 2006 02:36:58 +0000 (UTC), %u <newbie dd.com> wrote:

such as

int[short] hashtable;

where KeyType = short, and ValueType = int?

will this work? and as optimized (memory-wise, and CPU-wise)?

Thanks in advance for your conmments.

Associative arrays are sometimes called sparse arrays. They can be good with integer indexes, if those indexes tend to be widely distributed, with lots of unused indexes in between. -- Remove 'wants' and 'nospam' from e-mail.
Nov 26 2006