How to calculate a hash code for a collection of strings (0..5000 elements)

Question

I have a web page which allows to select geographical areas. I expect than not more than 5000 areas are selected.

Each area has a code (9 characters long).

I want to load a collection of areas from DB and let the user edit it.

If a user has made any changes, I want to show the 'unsaved changes' message somewhere. In order to do it, I want to compare the original and the current version of the collection.

Is it possible to calculate a hash code of this collection and compare just hash codes? Order of elements is not important and should be ignored.

The collection is currently implemented in this way

function AreaHashTable(areaIdentifiers) {

    //properties
    this.hash = {};

    this.addKeys(areaIdentifiers); }

AreaHashTable.prototype.getKeys = function () {
    return this.hash; };

AreaHashTable.prototype.hasKey = function (key) {
    if (this.getKeys().hasOwnProperty(key)) {
        return true;
    }
    return false; };

AreaHashTable.prototype.addKey = function (gssCode) {
    this.hash[gssCode] = gssCode;
     };

AreaHashTable.prototype.addKeys = function (areaIdentifiers) {
    var i;
    for (i = 0; i < areaIdentifiers.length; i++) {
        this.addKey(areaIdentifiers[i]);
    }     };


... etc

}

Order of elements may affect the generated hash code value though — vogomatix
– vogomatix, Commented Nov 22, 2013 at 16:33
@vogomatix: Half the point in the question is generating an order independent hash code. You are right that order may make a difference in a hash code but if such an algorithm were provided it wouldn't satisfy the criteria of the question. — Chris
– Chris, Commented Nov 22, 2013 at 16:52
I may have misinterpreted your question, but order independent hash codes are normally just some form of checksum and much weaker — vogomatix
– vogomatix, Commented Nov 22, 2013 at 16:59

fast · Accepted Answer · 2013-11-22 17:02:49Z

2

You can iterate over your string collection, generating a 9 character hash, by x-oring the characters of each string with the respective hash string character. This way, you receive an order independent hash value for your string collection.

something like:

var hash = [0,0,0,0,0,0,0,0,0];

for (var strg in strings) {
    for(var i=0; i<9; i++) {
        hash[i] ^= strg.charAt(i);
    }
}

However, maybe encapsulating the data and maintaining a "changed" flag, would be another solution for the underlying problem.

edited Nov 22, 2013 at 17:02

answered Nov 22, 2013 at 16:49

fast

8857 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Chris Over a year ago

A changed flag is usually my preferred way though it is not always perfect since undoing the changes manually (ie change "a" to "b" and then back to "a" again will generally leave it as flagged as "dirty". This may mean resaving data that hasn't in fact changed. Whether this is a problem or not is likely to depend on your usage.

will.ogden Over a year ago

I prefer the changed flag as well. On the setter you can always check if the incoming value is the same as the original, and if so remove the "dirty" flag.

fast Over a year ago

@Chris: agree, that with the flag it'd be difficult to track back a series of changes leading to the initial state.. however, with the hash, one can not be shure, that an actual change is really noticed - so, loosing the real change might be the worse..

Collectives™ on Stack Overflow

How to calculate a hash code for a collection of strings (0..5000 elements)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related