Simple Hash algorithm to detect duplicate content

[DotNetNewbie]

Hello,

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);


Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

Ideas?

 

[rossum]

Hello,

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);


Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

Probably not possible with a reasonable sized hash. If the size of
the hash is limited, and thare are more than that possible inputs then
there must be some collisions. How many possible values are there for
the Message string for example?

However it is possible to do something with a reasonably low
probability of a collision, something along the lines of:

int DoHash(string Message, int EmployeeID, int DepartmentID) {
const int multiplier = 29;
const int startValue = 37;
int hash = startValue;
hash = multiplier * hash + Message.GetHashCode();
hash = multiplier * hash + EmployeeID;
hash = multiplier * hash + DepartmentID;
return hash;
}

This relies on Messsage.GetHashCode() returning a suitable value.
Depending on your exact requirement you may need to put in your own
function there.

Remember that collisions are possible, though they should be rare. If
you get matching hash values then you must do a full check for
equality.

rossum

 

[Jon Skeet [C# MVP]]

Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

Ideas?

Could you clarify what you mean by the last part? If the inputs are the
same surely the result would *have* to be the same - otherwise it's
useless.

 

[Arne Vajhøj]

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);

Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

A hash that has to be unique for all input will need to have the same
size as the input meaning that it is useless.

It is really a trade off between risk of collisions with size and
computational effort.

int DoHash(string Message, int EmployeeID, int DepartmentID)
{
return (Message+EmployeeID+DepartmentID).GetHashCode();
}

only has 2^32 possible values.

string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServiceProvider();
return
Convert.ToBase64String(md5.ComputeHash(Encoding.UTF8.GetBytes(Message+EmployeeID+DepartmentID)));
}

has 2^128 possible values.

Arne

 

[Peter Bromberg [C# MVP]]

I am not sure that using a hash computation is the best way to detect
"duplicate content". Are you storing your content in a database? You really
haven't specified much detail. Perhaps you should be looking into a more
robust computation such as CRC32.
-- Peter
Site: http://www.eggheadcafe.com
UnBlog: http://petesbloggerama.blogspot.com
Short Urls & more: http://ittyurl.net

 

[DotNetNewbie]

Could you clarify what you mean by the last part? If the inputs are the
same surely the result would *have* to be the same - otherwise it's
useless.

Sorry I meant "can't duplicate the hash value if the inputs are not
the same".

 

[DotNetNewbie]

I am not sure that using a hash computation is the best way to detect
"duplicate content". Are you storing your content in a database? You really
haven't specified much detail. Perhaps you should be looking into a more
robust computation such as CRC32.
-- Peter
Site:http://www.eggheadcafe.com
UnBlog:http://petesbloggerama.blogspot.com
Short Urls & more:http://ittyurl.net

Peter,

Yes the content is stored in the database, before anyone inserts new
content I need to check if the same user has posted the same content
before, if he has, then don't insert it again.

Same content means: same employee ID, same departmentID and same
Message.

Meaning that the user can insert the same message text, but it has to
be in a different departmentID.

 

[Jon Skeet [C# MVP]]

Sorry I meant "can't duplicate the hash value if the inputs are not
the same".

In that case you really don't want a hash algorithm. The point of a
hash is to give an *indication* of equality in a reasonably cheap (in
storage and computation) manner.

See http://en.wikipedia.org/wiki/Hash_function

 

[Jon Skeet [C# MVP]]

Yes the content is stored in the database, before anyone inserts new
content I need to check if the same user has posted the same content
before, if he has, then don't insert it again.

Same content means: same employee ID, same departmentID and same
Message.

Meaning that the user can insert the same message text, but it has to
be in a different departmentID.

Right. So you ought to store the employee ID, department ID and message
in the database, and do a query for the combination. So long as all the
columns are indexed, it'll be fine.

 

[DotNetNewbie]

A hash that has to be unique for all input will need to have the same
size as the input meaning that it is useless.

It is really a trade off between risk of collisions with size and
computational effort.

int DoHash(string Message, int EmployeeID, int DepartmentID)
{
return (Message+EmployeeID+DepartmentID).GetHashCode();

}

only has 2^32 possible values.

string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServiceProvider();
return
Convert.ToBase64String(md5.ComputeHash(Encoding.UTF8.GetBytes(Message+EmployeeID+DepartmentID)));

}

has 2^128 possible values.

Arne

Arne, that looks like it is good for me (the string version).
Is that always going to be 32 characters in length?

 

[Jon Skeet [C# MVP]]

Arne, that looks like it is good for me (the string version).

It certainly doesn't satisfy your uniqueness constraint. Indeed, we can
even *force* a hash collision without even trying hard.

Consider:

Situation 1:
Message="Hello1"
EmployeeID=2
DepartmentID=3

Situation 2:
Message="Hello"
EmployeeID=12
DepartmentID=3

In both cases you'll be hashing "Hello123".

I still think you'd be better off letting the database work as it's
designed to...

 

[DotNetNewbie]

It certainly doesn't satisfy your uniqueness constraint. Indeed, we can
even *force* a hash collision without even trying hard.

Consider:

Situation 1:
Message="Hello1"
EmployeeID=2
DepartmentID=3

Situation 2:
Message="Hello"
EmployeeID=12
DepartmentID=3

In both cases you'll be hashing "Hello123".

I still think you'd be better off letting the database work as it's
designed to...

I see what your saying, then I could do:

string key = String.Format("eid={0}-did={2}-msg={3}", employeeid,
departmentid, message);
then hash the key.

I'm using this for duplicate content checking, not the Article Title
as before John!

 

[Jon Skeet [C# MVP]]

I see what your saying, then I could do:

string key = String.Format("eid={0}-did={2}-msg={3}", employeeid,
departmentid, message);
then hash the key.

I'm using this for duplicate content checking, not the Article Title
as before John!

Well, you could do that, yes. I still think you should use the database
as it's meant to be used though. You're still not guaranteed to not get
duplicates with this code.

 

[DotNetNewbie]

Well, you could do that, yes. I still think you should use the database
as it's meant to be used though. You're still not guaranteed to not get
duplicates with this code.

Jon, how can I check for duplicates using the database (keeping the
employeid/departmentid/message in mind).

 

[Jon Skeet [C# MVP]]

Jon, how can I check for duplicates using the database (keeping the
employeid/departmentid/message in mind).

Do a query to try to *find* a duplicate - search for an existing record
with the same employeeid/departmentid/message. Alternatively, create a
unique index across the three columns, and just try to insert, knowing
that it'll fail if there's a duplicate.

 

[Rad [Visual C# MVP]]

[26 quoted lines suppressed]

Peter,

Yes the content is stored in the database, before anyone inserts new
content I need to check if the same user has posted the same content
before, if he has, then don't insert it again.

Same content means: same employee ID, same departmentID and same
Message.

Meaning that the user can insert the same message text, but it has to
be in a different departmentID.

You could always create a unique constraint constituting the columns you
want to be unique. If the user tries to insert a duplicate the database
will throw an exception that you can trap

 

[Arne Vajhøj]

Arne, that looks like it is good for me (the string version).
Is that always going to be 32 characters in length?

Yes.

Arne

 

[Christopher Van Kirk]

I'm not a fan of this approach. The message column could be quite
large, and may affect the performance of such an index. Seems like it
would be better to compute a hash of some kind of the message, store
the hashed value in the database, and index on that along with the
other two key fields.

When you want to evaluate whether a particular combo exists, you just
query for the keys and hashed value, then compare your actual message
with the messages you get back from the database.

The weakness of this approach is that if there are millions of
messages for the same employee and department with the same hashed
message value, it could be slow to search through the results of a the
select. It's hard to imagine a scenario in which some employee of some
department could have millions of messages, though.

[26 quoted lines suppressed]

Peter,

Yes the content is stored in the database, before anyone inserts new
content I need to check if the same user has posted the same content
before, if he has, then don't insert it again.

Same content means: same employee ID, same departmentID and same
Message.

Meaning that the user can insert the same message text, but it has to
be in a different departmentID.

You could always create a unique constraint constituting the columns you
want to be unique. If the user tries to insert a duplicate the database
will throw an exception that you can trap

 

[Jon Skeet [C# MVP]]

I'm not a fan of this approach. The message column could be quite
large, and may affect the performance of such an index. Seems like it
would be better to compute a hash of some kind of the message, store
the hashed value in the database, and index on that along with the
other two key fields.

But that's exactly what an indexed unique constraint would do, but in a
more transparent fashion.

I've only ever had to manually store a hash in a database once, and
that was to effectively hash an unknown-until-execution-time number of
Guids when populating a set of sets.

Databases know how to index text columns. I think it's best to let them
do their job.

 

[DotNetNewbie]

But that's exactly what an indexed unique constraint would do, but in a
more transparent fashion.

I've only ever had to manually store a hash in a database once, and
that was to effectively hash an unknown-until-execution-time number of
Guids when populating a set of sets.

Databases know how to index text columns. I think it's best to let them
do their job.

My message column is NTEXT(MAX), and it is going to have articles in
it.
I'll look into this approach....