473,731 Members | 2,530 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

valid types for Keys (Hashtable, Dictionary)

Why can't I use an int[] for a key? Doing so evidently doesn't result in
unique IDs being generated. I can convert the array into a delimited string,
which works fine, but then I have a good deal of overhead parsing/casting the
ints back.
I'd obviously use a (jagged)multidi mensional array of my Value type instead
of a key:value setup, but the int[] sets aren't tightly grouped, so I'd have
a lot (maybe 85%) of empty slots in the array. Still, speed is my priority,
so maybe it'd be best to just eat the memory cost? A full array would contain
~4 million items.
Dec 9 '05 #1
4 3019
Ok. I just put the ints into a struct and used that as a key. Problem solved.
Why didn't I think of that earlier?
Dec 9 '05 #2
Depending upon what you are doing, that may have been the wrong
solution. structs have very specific applications in .NET, and using
them without due consideration can lead to grief.

The reason that your int[]s didn't generate unique hash keys is that
Array uses the default GetHashCode() method inherited from Object,
which is documented as being no good for hashing. From the
documentation:

"The default implementation of GetHashCode does not guarantee
uniqueness or consistency; therefore, it must not be used as a unique
object identifier for hashing purposes."

The point is that there was no way for the .NET team to come up with a
one-size-fits all hash function, so they provided merely the signature
and left it up to individual classes to decide how to generate hash
keys.

So, the solution to your original problem is to create your own _class_
(probably not struct) to hold whatever it is you need to hold. That
class should then override GetHashCode() (and Equals()... they go hand
in hand) so that it can be used as a hash key.

Dec 9 '05 #3
> Depending upon what you are doing, that may have been the wrong
solution. structs have very specific applications in .NET, and using
them without due consideration can lead to grief.
So what is the specific utility of structs? I assumed that they were chiefly
a handy way to group value types, like Point and Vector3 do. It seemed
wasteful to me to make a class for three ints. I just assumed that object
creation is slower, but I guess that everything in .NET is an object anyway.
"The default implementation of GetHashCode does not guarantee
uniqueness or consistency; therefore, it must not be used as a unique
object identifier for hashing purposes."
Aha. I never came across that in my MS Press C# book. Most of the things
I've read about Hashtables stop short of explaining the nuts and bolts.
They're just some magical search tree to me.
So, the solution to your original problem is to create your own _class_
(probably not struct) to hold whatever it is you need to hold. That
class should then override GetHashCode() (and Equals()... they go hand
in hand) so that it can be used as a hash key.


In my particular situation, I'm primarily interested in being able to look
up a given object with a specific 3 int location, without having to create
throwaway object intermediaries for comparisons.
Perhaps for my purposes, since I know that none of the ints will be larger
than, say, X, I could create a unique number from my int[a,b,c] that is
a + (b*(X+1)) + (c*(X+1)*(X+1))
and use this in the overrides you mentioned.
I wish I knew exactly how .NET generated the default hash codes.

Thanks for the feedback.

Dec 9 '05 #4

Joseph Bergevin wrote:
Depending upon what you are doing, that may have been the wrong
solution. structs have very specific applications in .NET, and using
them without due consideration can lead to grief.
So what is the specific utility of structs? I assumed that they were chiefly
a handy way to group value types, like Point and Vector3 do. It seemed
wasteful to me to make a class for three ints. I just assumed that object
creation is slower, but I guess that everything in .NET is an object anyway.


When you declare a struct, you create a _value_ type. That means that
it acts like an int or a double. Whenever you assign it:

MyValudType b = new MyValueType(... );
MyValueType a = b;

it is copied, just like an int or a double. Whenever you put it in a
collection (such as an ArrayList or a Hashtable) it is boxed. In
particular, if you make your value type mutable (not recommended) then
you have to be very, very careful that you understand the exact
semantics so that when you change the value you know that it changes
and you know exactly where it changes and where it doesn't. (Using the
example above, if you were allowed to say a.MyProperty = 5 then b would
not change, because the contents of b were copied into a on
assignment.)

If in your case your three ints are spacial coordinates (x, y, z) and
they were immutable (that is, you couldn't say coord.X = 5), then a
struct would probably be the right way to go. If you make them mutable
(coord.X = 5 is legal) then you could use a struct, but you would have
to be very careful. (Search this newsgroup to see the kind of confusion
that the behaviour of System.Drawing. Point causes.)

The bottom line is that in .NET structs come with important semantic
considerations: value semantics versus reference semantics. As such,
they shouldn't be used in an offhand manner as a sort of "classes lite"
because they introduce major changes in behaviour.
In my particular situation, I'm primarily interested in being able to look
up a given object with a specific 3 int location, without having to create
throwaway object intermediaries for comparisons.
Well, keep in mind that the only thing you really save by using structs
is memory management costs of allocating space for an object and then
garbage collecting it later. That is, unless your structs are being
boxed (as they would be if you used them in a Hashtable either as keys
or values). In that case you don't save anything.

Microsoft made System.Drawing. Point a struct because (IMHO) they do a
lot of mathematics with points, and didn't want to create a gazillion
Point objects as a result of intermediate calculation results and then
have to garbage collect them all later. If it's just a question of the
Hashtable, then I would say that it's a non-issue: your decision as to
whether to use struct or class should rest with higher-level conceptual
issues, not with fine points of efficiency.
Perhaps for my purposes, since I know that none of the ints will be larger
than, say, X, I could create a unique number from my int[a,b,c] that is
a + (b*(X+1)) + (c*(X+1)*(X+1))
and use this in the overrides you mentioned.
Yes... that would probably be a good strategy, so long as X never
changes during a particular run of your program. Another way is to
leverage off of the existing GetHashCode method in int:

public override int GetHashCode()
{
return a.GetHashCode() + b.GetHashCode() + c.GetHashCode() ;
}

or even

public override int GetHashCode()
{
return a + b + c;
}

Remember... you're not after a unique value, just a value that will
provide a nice, even distribution across all ints.
I wish I knew exactly how .NET generated the default hash codes.


Well, the default for Object probably just returns zero or something,
or maybe a fixed value for each object type. Each of the Framework
classes that overrides GetHashCode has its own algorithm. I tend to
assume that those are good, and leverage off of them when I can. For
example, if my class needs to hash on two key string fields, I just say

return string1.GetHash Code() + string2.GetHash Code();

assuming that Microsoft pays math wizards big bucks to come up with
good hash functions for strings. :-)

Dec 9 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
1754
by: Steve D. Perkins | last post by:
Hello all - I'm a Java and C++ developer, looking to pick up some Python and wxPython skills for prototyping and quick projects. I've been developing for about 15 years, and am very familiar with the wxWindows framework (I wrote one of the early Java bindings for it), but I've only been exposed to Python for a few days. I like to learn by doing, so I decided to just dive in with a small project I have a need for... a Spanish-English...
7
2683
by: Torsten Mohr | last post by:
Hi, reading the documentation (and also from a hint from this NG) i know now that there are some types that are not mutable. But why is it this way? From an overhead point of view i think it is not optimal, for example for a large string it could be much faster to have it changed in place, not generating a new one for
8
6310
by: xmail123 | last post by:
Hi, As was pointed out whatever you return from a WebMethod needs to be serializable to SOAP. An ArrayList is not serializable. I will be needing to return other data types from web methods. Is there a document, or can some one list those types that are not serializable and the syntax for converting them? Thanks
2
15949
by: ESPNSTI | last post by:
Hi, I'm trying to use a generics dictionary with a key class that implements and needs IComparable<>. However when I attempt to use the dictionary, it doesn't appear to use the IComparable<> to find the key. In the example below, accessing the dictionary by using the exact key object that was used to add to the dictionary works. (see code comment 1). However, if I attempt to access the dictionary by using a key object that
5
1761
by: Sky | last post by:
What makes something a valid DataSource? What methods/iterators/etc? Why do I ask? I do understand that a DataSet is based on an XML structure...but it's too table structured for what I am thinking... Can one read in a an xml file that has various embedded nodes (ie: records that have children records as XML does best) -- possibly not all the same length (ie, dif 'column count' for certain 'rows') and try to shove that into a...
11
2766
by: Crirus | last post by:
Easyest and fastest way... :) -- Ceers, Crirus ------------------------------ If work were a good thing, the boss would take it all from you ------------------------------
4
2486
by: techiepundit | last post by:
I'm a Python newbie who just started learning the language a few weeks ago. So these are beginner questions. I have a list of sockets that I use for select.select calls like this: ReadList,WriteList,EventList = select.select(self.SocketList,,,3) In parallel with that list of sockets I want something that is like a list of socket,PacketFragment pairs. I need this because I could do recv and get part of a sent packet. I want to loop...
11
7806
by: garyhoran | last post by:
Hi Guys, I have a collection that contains various attributes (stuff like strings, DateTime and Timespan) . I would like to access the collection in various orders at different points in the application ie sometimes I want to cycle through the values in the collection in DateTime order while at other times in TimeSpan order. Ideally I would like multiple keys - such as Timespan within DateTime order but maybe that is asking too much.
8
2594
by: Guy | last post by:
Is there a better way to search identical elements in a sorted array list than the following: iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count, aSearchedObject ); aFoundObject= m_Array; m_ResultArray.Add ( aFoundObject);
0
8943
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8770
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9442
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9301
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9229
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8184
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
6030
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4801
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
2175
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.