[2005] Collection, ArrayList or Hashtable?

[eyeRmonkey]

I am trying to decide which type of collection/array I should use for my current situation. I have a key (which would be an integer, but I don't mind storing it as a string) that is a numer (453278 lets say). And I need to find a corrosponding string (album name) for that number. I am basically trying to cross reference a number to an album name so I can find that number in another collection easily.

Here is what I have considered:
Array - Wouldn't work unless I did a 2-D array because I have 2 values I need to compare, and because the second dimension of the array would only be only have length of 0 which seems pointless. Also, I don't want to have to loop to find things
ArrayList - Might work because I can use IndexOf() to find things. But might not work because I would again have to do a 2-D array to find things. Making a structure wouldn't help because I could no longer use IndexOf since I would only know 1 of the peices of information (the number).
Collection - Would work because I have a key and a value, but seems too big for this problem.
HashTable - Don't know anything about them.

If I didn't explain this well enough please let me know.

[jmcilhinney]

Don't use a Collection under any circumstances. It is a VB6 hold-over, and we know you don't like that. Take a look at its help topic and you'll see it belongs to the Microsoft.VisualBasic namespace.

ArrayLists are the most general collection. They behave much like an array of Object that can be dynamically resized.

A Hashtable is a keyed, unsorted collection that allows you to retrieve an item by name efficiently.

A SortedList is similar to a Hashtable but is always sorted by key.

There are other types of collections too, and classes specifically designed as bases for your own collection classes. .NET 2.0 also has Generic collections. For instance, a Generic.List is like an ArrayList except that you specify the types of objects it can store. I strongly suggest that you take a look at the help/MSDN topics for the System.Collections and System.Collections.Generic namespaces to see what classes are available and read the description of each one to see what they are for. In your case I would go with:

Dim albums As New Generic.Dictionary(Of Integer, String)

That way the keys are strongly typed to Integer and the values are strongly typed to String. You might also want to use a Generic.SortedDictionary or Generic.SortedList if you want to be able to enumerate the items and have them ordered by key.

[eyeRmonkey]

Don't use a Collection under any circumstances. It is a VB6 hold-over, and we know you don't like that. Take a look at its help topic and you'll see it belongs to the Microsoft.VisualBasic namespace.

I had no idea Collections were "old code" (kidding ). Thanks. I'll add that to the table I made.

Dictionary sounds like just what I need. And I will look into the namespaces you mentioned. I have a question about the code you gave for declaring a dictionary. Could that be compared to a 2-D array or a 1-D array of a structure (whose parts are an Integer and String)?

Also, I had been meaning to reasearch what the Of T meant in a lot of the functions that I had encountered, but now it makes total sense: "Make a dictionary of type [type]".

[jmcilhinney]

I have a question about the code you gave for declaring a dictionary. Could that be compared to a 2-D array or a 1-D array of a structure (whose parts are an Integer and String)?

In a way, as there is an association between the two objects, but the use of a key allows efficient retrieval via hash codes rather than iterative searching. Also, all keys must be unique.

[eyeRmonkey]

Okay I have another question, but let me explain my situation first: I am trying to work with music files (via iTunes) and I want to be able to access and find songs two ways: Either by their unique databse ID number or by their album name. Basically I need a dictionary with two keys. There will be multiple database ID numbers per album, but every album name will be unique.

I will also need to update my the dictionary as the iTunes library changes. I will need to add and move items around the collection. I'm not sure if a hash table or dictionary will allow me to do what I need to, but I was wondering if you (JM) or anyone else had any suggestions about how to structure this.

I looked into hash tables, but it will take a while for me to absorb all 15 overloads of the contructor.

[jmcilhinney]

You say that you want to be able to search by ID or name, but what objects will you be getting back? If it's the name as a String then a Dictionary has a ContainsValue method that would tell you whether an album name exists. There's no need to retrieve the name if you've already got it. If you actually have Album objects that you want to retrieve by ID or Name then you might want to build a container class that maintains two collections; one keyed on ID and the other on Name. I guess the alternative is to just use a DataTable, where you have Rows.Find and Select to get records on primary key or any other selection criteria. You could also create a container class that uses a DataTable internally.

[eyeRmonkey]

Sorry, I forgot to mention that. Here is what I need:
Key: Album Name
Key: Database ID
Value: IITTrack Class

IITTrack has many properties and object so I don't really want to to create 2 dictionaries of it (1 for each of the 2 keys). The reason I am doing all of this is because I need to be able to easily find the songs grouped by their album name, and iTunes doesn't provide an easy way to do this, so I am basically storing most of their database inside my program (and updating it as necessary) so I can easily find an entire album.

Since I will be updating my dictionary as the song information changes in iTunes I need to access tracks VIA their databaseID number so I don't have to loop through things (which I could do, but would rather avoid).

First I was thinking of cross referencing things, but I was wondering if there was a good way to have 2 keys and 1 value. I think might just go back to that idea, though:

Private AlbumCol As New Dictionary(Of String, IITTrack) ' (Album Name, Track Object)
    Private CrossRefTracks As New Dictionary(Of Integer, String) ' (Database ID, Album Name)

One way I was thinking about doing the 2-Key approach (but that still wouldn't work that well) was to do this:

Private AlbumCol As New Dictionary(Of String, Dictionary(Of Integer, IITTrack))
    Private CrossRefTracks As New Dictionary(Of Integer, String)

Any thoughts of any of this?

[jmcilhinney]

I think you should use two Dictionaries; one (Of Integer, IITTrack) and the other (Of String, IITTrack). The ways you have proposed would require two lookups in some circumstances while this way only requires one in all situations. Also, your IITTrack is a reference type so it's not like you're creating two instances of each one. The values in each collection are just references to the objects, so each collection will refer to all the same objects. To build the two collections you would just do something like this:

Dim albumsByName As New Generic.Dictionary(Of String, IITTrack)
Dim albumsByID As New Generic.Dictionary(Of Integer, IITTrack)
 
'Pseudocode
For Each album
    albumsByName.Add(album name, album)
    albumsByID.Add(album ID, album)
Next

If you have these two collections contained in a class you can provide an overloaded Item property that will then retrieve the corresponding Item property of the appropriate collection.

[eyeRmonkey]

I realized that I wasn't explaining things right again because I hadn't taken the time to fully analyze what I needed to do. Sorry for asking the same question 4 times, but lets try this again. Here is a diagram of what I need:

Dict  -> Dict   -> Value
Album -> Tracks -> Track
                   Track
                   Track
Album -> Tracks -> Track
                   Track
                   Track

This is the reason I was talking about cross referencing and such, because I needed to access information that was 2 layers deep without searching in a loop. If I had a cross reference I could simply search DatabaseID and get the proper album name, then I could search that album for the proper track.

I can't simply have one dictionary (instead of 1 dictionary nested within another) because I couldn't hold all the tracks the way I need to because then the keys wouldn't be unique. What I mean is that if I only used 1 dictionary I would essentially be trying to do this:

'Pseudocode
MyDict.Add(album as key, track 1 as value)
MyDict.Add(album as key, track 2 as value)
MyDict.Add(album as key, track 3 as value)
...

That wouldn't work because the keys need to be unique.

What I really need to do is this:

MyDict.Item(album key).Add(trackID as key, track 1 as value)
MyDict.Item(album key).Add(trackID as key, track 2 as value)
MyDict.Item(album key).Add(trackID as key, track 3 as value)
...

Where Item(album) would return the second dictionary, which I would then add to.

The purpose of the cross reference array was so I could find which album contained the track without looping through all the albums and performing a search on each collection (second dimension collection that is).

Does that make sense?

Now, I am still open to any suggestion you have about restructuring this, but it took me a while to realize what my question was. Sorry for how complicated this is getting, but I appreciate the help (as always ).

[jmcilhinney]

OK, now I see what you're getting at (I think). Yeah, it seems like what you want is a Generic.Dictionary(Of String, Generic.Dictionary(Of Integer, IITTrack)). Again, I'd say that hiding it inside a class would be a good idea. Then you could provide a an Item property something like this:

Private tracksByAlbum As New Generic.Dictionary(Of String, Generic.Dictionary(Of Integer, IITTrack))
 
Public Property Item(ByVal albumName As String, ByVal trackID As Integer) As IITTrack
    Get
        Dim tracksByID As Generic.Dictionary(Of Integer, IITTrack) = Me.tracksByAlbum(albumName)
 
        If tracksByID Is Nothing Then
            Return Nothing
        Else
            Return tracksByID(trackID)
        End If
    End Get
    Set(ByVal value As IITTrack)
         Dim tracksByID As Generic.Dictionary(Of Integer, IITTrack) = Me.tracksByAlbum(albumName)
 
        If tracksByID Is Nothing Then
            tracksByID = New Generic.Dictionary(Of Integer, IITTrack)
            Me.tracksByAlbum.Add(albumName, tracksByID)
        End If
 
        tracksByID(trackID) = value
    End Set
End Property

[eyeRmonkey]

Wow. That is exactly what I need. I started making a class, but couldn't seem to wrap my head around my objective and what I needed to do to get there. I was basically trying to find a simplier way of doing things so I didn't have to reference two dictionaries (nested in one another) every time I needed to find something. Wrapping everything in a class is perfect.

I wish I saved my reps for you for when you really really desereved it, because I can't rep you until I spread it around some more. I think I might have to fight the other person that gave you a marriage proposal, because I think I want to marry you now.

Thanks again for everything.

EDIT: I think I should still have the cross reference (inside the class) so that I can easily find a track only by knowing it's TrackID number. And I will also need to make a method that returns the entire album incase I need to work with that (which was the original goal of enumerating the entire iTunes library). Do you agree or can you see a better way to find a track given only it's TrackID number?

[jmcilhinney]

OK, if every track ID is globally unique and not just unique within an album then the nested collection is not the way to go. You'd go to two seperate collections; one keyed on album name and containing collections (Generic.List(Of Integer) or maybe just arrays of Integer) of track IDs, the other keyed on track ID and containing the tracks themselves. That way you can get a list of track IDs from an album name and a track from a track ID. It really comes down to what you need to uniquely identify a track from every other track. If it's just the track ID then you should use two separate collections. If it's album name and track ID then you'd need to use nested collections.

[eyeRmonkey]

I have another question. You mentioned above that the collection only holds references to the objects (tracks) instead of the object itself. I knew this, but had forgotten it. I was curious how much space the collection would take up since it is only a list of pointers (which point to the actual track). I assume it would be relatively small, correct?

The reason I am asking is because I might see a use for a second cross reference (because album names of a track might change) and I want to know if I will be wasting lots of memory by doing this.

[jmcilhinney]

Every collection, like every object of every type, has a certain amount of memory it occupies. Each time you add an object to the collection you simply add another reference, so regardless of how big the objects are the collection only needs basically 32 bits of memory for each one.

[eyeRmonkey]

Every collection, like every object of every type, has a certain amount of memory it occupies. Each time you add an object to the collection you simply add another reference, so regardless of how big the objects are the collection only needs basically 32 bits of memory for each one.

Okay, I guess this is my question: Without knowing how big and IITTrack object is, can you tell me the size differnece between this:

Private TrackCol As New Dictionary(Of Integer, IITTrack)

And this:

Private TrackCol1 As New Dictionary(Of Integer, IITTrack)
Private TrackCol2 As New Dictionary(Of Integer, IITTrack)

Assume all of the collections hold the same number of IITTrack objects and theat they all point to the same tracks. Would the difference of size be large because I made 2 dictionaries or would it be relatively small since it would contain pointers pointing to the same objects.

Okay, here is what I came up with last night for the problem (which voids my earlier question, because I found a new way to do what I needed to):

Public Class CiTunesTrack
 
    Public Track As iTunesLib.IITTrack
    Public InternalAlbum As String
 
End Class
 
Public Class CiTunesAlbum
    Private AlbumCol As New Dictionary(Of String, List(Of Integer))
    Private TrackCol As New Dictionary(Of Integer, CiTunesTrack)
 
    ...
End Class

The reason I made the CiTunesTrack collection was so I could store my own value for "album" within the program. That value will always match the key for AlbumCol. The reason that needs to be done is because if the album name changes in iTunes then I have no way to find the track within AlbumCol because I don't know its old album name.

If that didn't make sense don't worry about it, because I think I have it figured out now. I am currently in the process of making CiTunesAlbum and adding all the methods that I need.

[jmcilhinney]

If you need two Dictionaries then use two Dictionaries. The overhead will be twice the size but the size of the objects being stored makes next to no difference. It's just the size of the actual collection object itself, and the hash buckets it creates and so on. Basically, the memory footprint is not going to be an issue so just go ahead and use them.