Hashing and comparing of arrays

[Ole Nielsby]

How does the GetHashCode() of an array object behave?

Does it combine the GetHashCode() of its elements, or does
it create a sync block for the object?

I want to use readonly arrays as dictionary keys, based on
their content, not their identity. Is this feasible using the
arrays directly, or do I need to wrap them in a struct that
handles GetHashCode and Equal? If so, is such a wrapper
present in the standard class library?

My app will have hundreds or maybe thousands of these
dictionaries, some of which will contain only a single
arraykey-value entry, while others will have thousands
of entries. The number of entries in a particular dictionary
cannot be predicted or estimated reliably in advance. The
values associated with the arrays will be WeakReference
objects, each pointing to an object with a finalizer that will
remove the entry from the containing dictionary.

Would the Dictionary<Some Class[], WeakReference>
generic collection be suitable for this, or do I need to
spice it up?

[Jon Skeet [C# MVP]]

Ole Nielsby <ol*********@sn ailmail.dk> wrote:

How does the GetHashCode() of an array object behave?

Does it combine the GetHashCode() of its elements, or does
it create a sync block for the object?
Neither, as far as I'm aware. I believe it doesn't override GetHashCode
at all, so the implementation in Object is used.
I want to use readonly arrays as dictionary keys, based on
their content, not their identity. Is this feasible using the
arrays directly, or do I need to wrap them in a struct that
handles GetHashCode and Equal? If so, is such a wrapper
present in the standard class library?
You'll need to wrap them, I believe. (Any reason for using a struct
rather than a class though?)
My app will have hundreds or maybe thousands of these
dictionaries, some of which will contain only a single
arraykey-value entry, while others will have thousands
of entries. The number of entries in a particular dictionary
cannot be predicted or estimated reliably in advance. The
values associated with the arrays will be WeakReference
objects, each pointing to an object with a finalizer that will
remove the entry from the containing dictionary.

Would the Dictionary<Some Class[], WeakReference>
generic collection be suitable for this, or do I need to
spice it up?

I'd consider using a HybridDictionar y - it's likely to be much more
efficient for the smaller ones. Unfortunately, however, I don't believe
there's a generic version :(

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Ole Nielsby]

Jon Skeet [C# MVP] <sk***@pobox.co m> wrote:

Ole Nielsby <ol*********@sn ailmail.dk> wrote:

How does the GetHashCode() of an array object behave?

Does it combine the GetHashCode() of its elements, or does
it create a sync block for the object?
Neither, as far as I'm aware. I believe it doesn't override
GetHashCode at all, so the implementation in Object is used.

I may have got this wrong but I think the Object::GetHash Code
implementation will create a sync block if there isn't already
one.

I want to use readonly arrays as dictionary keys, based on
their content, not their identity. Is this feasible using the
arrays directly, or do I need to wrap them in a struct that
handles GetHashCode and Equal? If so, is such a wrapper
present in the standard class library?

You'll need to wrap them, I believe. (Any reason for using a
struct rather than a class though?)

There will be large numbers of these arrays, and wrappers
would be unnecessary memory bloat. A generic collection
used with a struct will, if I understand generics right, be able
to store the array pointers as efficiently as if I used them
directly, while using the overrides defined by my struct when
hashing and comparing.
I'd consider using a HybridDictionar y - it's likely to be much
more efficient for the smaller ones. Unfortunately, however,
I don't believe there's a generic version :(

Well then, I guess I will google up an open source generic
HybridDictionar y-like thing - I'm pretty sure it exists somewhere,
I just hoped I could make do with the standard library.

Regards/Ole N.

[Jon Skeet [C# MVP]]

Ole Nielsby <ol*********@sn ailmail.dk> wrote:

Does it combine the GetHashCode() of its elements, or does
it create a sync block for the object?

Neither, as far as I'm aware. I believe it doesn't override
GetHashCode at all, so the implementation in Object is used.

I may have got this wrong but I think the Object::GetHash Code
implementation will create a sync block if there isn't already
one.

Sync blocks and GetHashCode are unrelated. The first is to do with
locking; the second is to do with hashing. What makes you think they're
related?

You'll need to wrap them, I believe. (Any reason for using a
struct rather than a class though?)

There will be large numbers of these arrays, and wrappers
would be unnecessary memory bloat. A generic collection
used with a struct will, if I understand generics right, be able
to store the array pointers as efficiently as if I used them
directly, while using the overrides defined by my struct when
hashing and comparing.

Yes, if you use generics you should be okay.

I'd consider using a HybridDictionar y - it's likely to be much
more efficient for the smaller ones. Unfortunately, however,
I don't believe there's a generic version :(

Well then, I guess I will google up an open source generic
HybridDictionar y-like thing - I'm pretty sure it exists somewhere,
I just hoped I could make do with the standard library.

It sounds like you do need generics.

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Ole Nielsby <ol*********@sn ailmail.dk> wrote:

Neither, as far as I'm aware. I believe it doesn't override
GetHashCode at all, so the implementation in Object is used.

I may have got this wrong but I think the Object::GetHash Code
implementation will create a sync block if there isn't already
one.

Having just googled this, it appears that under v1.0 and v1.1,
Object.GetHashC ode does indeed create a sync block. It's incidental,
however - and the blog linked below suggests that v2.0 may not behave
in the same way.

http://blogs.msdn.com/brada/archive/.../30/50396.aspx

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Ole Nielsby]

Jon Skeet [C# MVP] <sk***@pobox.co m> wrote:

Having just googled this, it appears that under v1.0 and v1.1,
Object.GetHashC ode does indeed create a sync block. It's incidental,
however - and the blog linked below suggests that v2.0 may not
behave in the same way.

http://blogs.msdn.com/brada/archive/.../30/50396.aspx

I think what the blog suggests is, you cannot assume that different
objects with non-overridden GetHashCode() always return different
hash codes even though this may be the case under v1.x and some
MS developers were caught using it.

I'll bet a beer that Object.GetHashC ode still creates a sync block in v2.
There is really nowhere else to store the hash code, unless they'd take
the trouble of storing it in the sync lock slot in a form distinguishable
from a real sync lock, then, in case a sync block is created later, move
the hash code to a slot in the sync block. This somehow seems bad
style though, and I don't think the clr forgers will (or should) do
this to facilitate some exotic uses of Object.GetHashC ode() which is
supposed to be overridden anyway.

Regards/Ole N.

[Lucian Wischik]

"Ole Nielsby" <ol*********@sn ailmail.dk> wrote:

I want to use readonly arrays as dictionary keys, based on
their content, not their identity. Is this feasible using the
arrays directly, or do I need to wrap them in a struct that
handles GetHashCode and Equal? If so, is such a wrapper
present in the standard class library?

Incidentally, I was also looking to hash a list based on contents
recently. I found "lookup2" by Bob Jenkins, and translated it into C#.
Maybe this will be helpful. (or maybe there already exist better C#
hash implementations elsewhere that I hadn't found...)
/// <summary>
/// Produces a hash out of a list of hash-values.
/// This is a C# implementation of the "lookup2" hash of Bob Jenkins
(1996).
/// Licensing conditions for Lookup2: Bob Jenkins writes, "You may
use this
/// code any way you wish, private, educational, or commercial. It's
free."
/// </summary>
/// <param name="keys">An enumerable list of items; we will
GetHashCode()
/// on each of them</param>
/// <param name="previousH ash">If you call hash more than once, feed
the previous
/// hash result into the next call to hash. Otherwise, if you only
call it once,
/// previousHash can be an arbitrary value.</param>
/// <returns>A 32-bit signed integer hash code.</returns>
private static int lookup2_hash(Sy stem.Collection s.IEnumerable keys,
int previousHash)
{ System.Collecti ons.IEnumerator keyi = keys.GetEnumera tor();
uint a = 0x9e3779b9; uint b=a; uint c = (uint)previousH ash;
uint[] k=new uint[12]; uint length=0; uint sublen=12;
while (true)
{ sublen=0; while (keyi.MoveNext( ) && sublen<12)
{ k[sublen] = (uint)keyi.Curr ent.GetHashCode ();
sublen++; length++;
}
if (sublen==12)
{ a += k[0] +(k[1]<<8) +(k[ 2]<<16) +(k[3]<<24);
b += k[4] +(k[5]<<8) +(k[ 6]<<16) +(k[7]<<24);
c += k[8] +(k[9]<<8) +(k[10]<<16) +(k[11]<<24);

a-=b;a-=c;a^=(c>>13);b-=c;b-=a;b^=(a<<8);c-=a;c-=b;c^=(b>>13);a-=b;a-=c;a^=(c>>12);

b-=c;b-=a;b^=(a<<16);c-=a;c-=b;c^=(b>>5);a-=b;a-=c;a^=(c>>3);b-=c;b-=a;b^=(a<<10);
c-=a;c-=b;c^=(b>>15);
}
else
{ c += length;
if (sublen>=11) c+= (k[10]<<24);
if (sublen>=10) c+= (k[9]<<16);
if (sublen>=9 ) c+= (k[8]<<8);
// the first byte of c is reserved for the sublength
if (sublen>=8) b+= (k[7]<<24);
if (sublen>=7) b+= (k[6]<<16);
if (sublen>=6) b+= (k[5]<<8);
if (sublen>=5) b+= (k[4]);
if (sublen>=4) a+= (k[3]<<24);
if (sublen>=3) a+= (k[2]<<16);
if (sublen>=2) a+= (k[1]<<8);
if (sublen>=1) a+= (k[0]);

a-=b;a-=c;a^=(c>>13);b-=c;b-=a;b^=(a<<8);c-=a;c-=b;c^=(b>>13);a-=b;a-=c;a^=(c>>12);

b-=c;b-=a;b^=(a<<16);c-=a;c-=b;c^=(b>>5);a-=b;a-=c;a^=(c>>3);b-=c;b-=a;b^=(a<<10);
c-=a;c-=b;c^=(b>>15);
return (int)c;
}
}
}

--
Lucian

[Helge Jensen]

Ole Nielsby wrote:

How does the GetHashCode() of an array object behave?
In .NET1 atleast it returns an identity of the array, so:

byte[] b1 = {};
byte[] b2 = {};

b1.GetHashCode( ) != b2.GetHashCode( )
I want to use readonly arrays as dictionary keys, based on
their content, not their identity. Is this feasible using the
arrays directly, or do I need to wrap them in a struct that
handles GetHashCode and Equal? If so, is such a wrapper
present in the standard class library?
I would suggest using an IDictionary with keys something like:

public class ComparableArray <T>:
IEquatable<Comp arableArray<T>> , // if you decide to use hashing
IComparable<Com parableArray<T> >
{
int? hash; // if you decide to do hashing
public readonly T[] Array;
public ComparableArray (T[] array, int? hash) {
this.Array = array;
this.hash = hash;
}
public ComparableArray (T[] array): this(array, null) {}
public static int CalculateHash(T[] array) {
// do your stuff with Knuth, or whatever. perhaps something like:
uint x = 0;
foreach ( T t in array ) {
x ^= (uint)t.GetHash Code(); // combine hashes
// rotate make ordering %32 significant, Knuth can do wonders here
x = (uint)(x >> 1) | (uint)((x & 0x1) << 31);
}
return (int)x;
}
public override GetHashCode() {
if ( hash == null )
hash = CalculateHash(A rray);
return (int)hash;
}
public bool Equals(Comparab leArray<T> other) {
return
Array.Length == other.Array.Len gth
&& GetHashCode() == other.GetHashCo de()
&& compareItemByIt em(Array, other.Array);
}
public int Compare(Compara bleArray<T> other) {
int diff;
T[] a1 = Array, a2 = other.Array;
diff = a2.Length - a1.Length;
IComparer<T> comp = Comparer.Defaul t<T>;
if ( diff != 0 )
return diff;
for ( int i = 0; i < a1.Length; ++i ) {
diff = a2[i] - a1[i];
if ( diff != 0 )
return diff;
}
return 0;
}
public static bool compareItemByIt em(T[] a1, T[] a2) {
if ( a1.Length != a2.Length )
throw new ArgumentExcepti on("Unequal lengths", "a1 and a2");
// you could just compare some small subset of actual valuse
// iff your hash is really good
for ( int i = 0; i < a1.Length; ++i )
if ( !a1[i].Equals(a2[i]) )
return false;
return true;
}
// Make interchanging T[] and ComparableArray <T> easy
public static explicit operator T[](ComparableArra y a)
{ returrn a.Array; }
public static implicit operator ComparableArray (byte[] a)
{ return new ComparableArray (a); }
// decorate with operators == != <, <=, ... as you like
}

And use IDictionary<Com parableArray<T> , V> as the interface for storage.

You can use any implementation of IDictinoary using ComparableArray <T>
as the key-type, since it supports both hashing and alphabetic sorting.

The above Key-type implementation will cache the hashing of keys, so you
won't have to rehash the keys in the dictionary when doing lookup. It's
not that much performance gained, but since you need a wrapper Key-type
for GetHashCode and Equals anyway...

If you choose your hash-function well you might just want to sample a
few items when comparing item-by-item.

The best data-structure for this kind of operation is know as a
dictionary (don't confuse that with the C# Dictionary :) and is related
to prefix-trees. Have a look at those if you are screaming for
performance (they are pretty cute too :)
My app will have hundreds or maybe thousands of these
dictionaries, some of which will contain only a single
arraykey-value entry, while others will have thousands
of entries. The number of entries in a particular dictionary
cannot be predicted or estimated reliably in advance. The
values associated with the arrays will be WeakReference
objects, each pointing to an object with a finalizer that will
remove the entry from the containing dictionary.
Try just using Dictionary<Comp arableArray<T>, WeakReference> or
SortedDictionar y<ComparableArr ay<T>, WeakReference>, it will have pretty
OK performance. You can always complicate things by using the
proxy-pattern to dispatch to different implementations of IDictionary
depending on dictionary-size.
Would the Dictionary<Some Class[], WeakReference>
generic collection be suitable for this, or do I need to
spice it up?

No, SomeClass[].GetHashCode screws it up.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Ole Nielsby]

"Lucian Wischik" <lu***@wischik. com> wrote:

I found "lookup2" by Bob Jenkins, and translated it into C#.

Thanks - this goes into my code snippet collection.

[Ole Nielsby]

Helge Jensen <he**********@s log.dk> wrote:

I would suggest using an IDictionary with keys something like:

public class ComparableArray <T>:
[...]

The above Key-type implementation will cache the hashing of
keys [...]
I'll leave that part out... the arrays will never be hashed more than
once or twice. (They will be hashed and unified on creation). And
I'll do a struct instead of a class if possible, since large amounts of
them will be created.
[...]

Try just using Dictionary<Comp arableArray<T>, WeakReference>
or SortedDictionar y<ComparableArr ay<T>, WeakReference>, it
will have pretty OK performance.

I'll stick with the Dictionary<> then, and change it only if
profiling identifies it as a hot thing.

(The app is an interpreter for a homebrew programming language
that I use for some rather complex tasks, the meanest of which
is as a parser generator system that can produce parsers for
ill-structured languages like VB6. The data model of my language
implies that constant trees must be unified, like intern'ed strings
but deep structures, rather like attribute based XML. This
'cascading unification' doesn't really fit well with .NET,it's much
faster when objects aren't compacted, allowing hash functions
to operate directly on already unified pointers. Anyway, since
I'm doung a .NET port, I might as well go all the way and use
managed objects, interoperabilit y being more important than
raw speed. It's a pity, though, that the framework doesn't have
some support for cascading unification, like a generalized Intern,
perhaps controlled by an interface, like serialization is controlled
by ISerializable.)

Anyway, thanks for clarifying the array hashing issue.