10
\$\begingroup\$

I need to store serialized objects in a database and I want to avoid duplicates. In order to be able to tell wheter an object is already stored, I have to compare them somehow. My idea was to calculate a hash for some of its properties that I consider as equatable and store it in a separate column.


The algorithm is very simple: I implemented it with a builder that allows me to define a hash function and how each property should be formatted. E.g. strings may be case insensitive, floats may be rounded or date-time may be stripped of its millisecond part etc. This transformation is done by each expression. It then serializes each value into bytes and adds them to the buffer. Finally the hash-function calculates the hash-value. Sorting the expressions by member-name should prevent bugs caused by simply changing their order.

public class FingerprintBuilder<T>
{
    private readonly List<(string MemberName, Func<T, object> Fingerprint)> _fingerprints;

    public FingerprintBuilder()
    {
        _fingerprints = new List<(string Expression, Func<T, object> Fingerprint)>();
    }

    public static FingerprintBuilder<T> Empty => new FingerprintBuilder<T>();

    public FingerprintBuilder<T> For<TProperty>(Expression<Func<T, TProperty>> memberExpression, Expression<Func<TProperty, TProperty>> fingerprint)
    {
        var getProperty = memberExpression.Compile();
        var getFingerprint = fingerprint.Compile();
        _fingerprints.Add((
            ((MemberExpression)memberExpression.Body).Member.Name, 
            (Func<T, object>)(obj => getFingerprint(getProperty(obj)))
        ));
        return this;
    }

    public Func<T, byte[]> Build(Func<byte[], byte[]> computeHash)
    {
        return obj =>
        {
            var buffer = new List<byte>();

            var binaryFormatter = new BinaryFormatter();
            foreach (var t in _fingerprints.OrderBy(e => e.MemberName, StringComparer.OrdinalIgnoreCase))
            {
                var fingerprint = t.Fingerprint(obj);
                using (var memory = new MemoryStream())
                {
                    binaryFormatter.Serialize(memory, fingerprint);
                    buffer.AddRange(memory.ToArray());
                }
            }

            return computeHash(buffer.ToArray());
        };
    }
}

In this example I also use two helper extensions. One for calculating the hash and the other one to get its string representation:

public static byte[] ComputeSHA1(this byte[] source)
{
    if (source == null) throw new ArgumentNullException(nameof(source));

    using (var sha1 = new SHA1Managed())
    {
        return sha1.ComputeHash(source);
    }
}

public static string ToHexString(this byte[] source)
{
    if (source == null) throw new ArgumentNullException(nameof(source));

    return
        source
            .Aggregate(new StringBuilder(), (current, next) => current.Append(next.ToString("X2")))
            .ToString();
}

Example

Testing it with these examples:

var p1 = new Person { FirstName = "John", LastName = "Doe", Age = 20 };
var p2 = new Person { FirstName = "John", LastName = "DOE", Age = 30 };
var p3 = new Person { FirstName = "Johny", LastName = "DOE", Age = 30 };

var personFingerprint = 
    FingerprintBuilder<Person>.Empty
        .For(p => p.LastName, x => x.ToUpperInvariant().Trim())
        .For(p => p.FirstName, x => x.ToUpperInvariant().Trim())
        .Build(SHA1.ComputeSHA1);

personFingerprint(p1).ToHexString().Dump();
personFingerprint(p2).ToHexString().Dump();
personFingerprint(p3).ToHexString().Dump();

produces these three results:

D46E5C869CDBA5775D7F8C9AF6BC497D5EEA76C4
D46E5C869CDBA5775D7F8C9AF6BC497D5EEA76C4
F450C1CE6B1A2041D8D7D0FEAA31AF7C5C214D81

What do you think of this algorithm? Does it have any weaknesses or can anything else be improved?

\$\endgroup\$
  • \$\begingroup\$ The latest version is here, in my repository. \$\endgroup\$ – t3chb0t Apr 20 at 10:14
6
\$\begingroup\$

It looks alright to me, although it seems odd having a young man of age 20 to equal an "elderly" man of age 30 :-).

I have 3 minor things:

1) One MemoryStream can be used to serialize all expressions:

  public Func<T, byte[]> Build(Func<byte[], byte[]> computeHash)
  {
    return obj =>
    {
      var binaryFormatter = new BinaryFormatter();
      using (var memory = new MemoryStream())
      {
        foreach (var t in _fingerprints.OrderBy(e => e.MemberName, StringComparer.OrdinalIgnoreCase))
        {
          var fingerprint = t.Fingerprint(obj);
          {
            binaryFormatter.Serialize(memory, fingerprint);
          }
        }

        return computeHash(memory.ToArray());
      }
    };
  }

2) The ToHexString() can be simplified like this:

  public static string ToHexString(this byte[] source)
  {
    if (source == null) throw new ArgumentNullException(nameof(source));

    return string.Join("", source.Select(ch => ch.ToString("X2")));
  }

3) FingerprintBuilder.Empty is an strange name. I would call it Builder or avoid the static instantiater.

\$\endgroup\$
  • 1
    \$\begingroup\$ I like the trick without the buffer-list! ;-) I didn't know I can write to the MemoryStream multiple times. \$\endgroup\$ – t3chb0t Feb 28 '18 at 15:03
  • 1
    \$\begingroup\$ The two Johns are clones, they have the same DNA so they are basically equal ;-] \$\endgroup\$ – t3chb0t Feb 28 '18 at 15:09
4
\$\begingroup\$

Apart from the improvements suggested by Henrik Hansen and a couple of null checks I changed the list with tuples into SortedDictionary to avoid repetitive OrderBy and added a null check before calling getFingerprint for a property.

This is the updated builder:

public class FingerprintBuilder<T>
{
    private readonly Func<byte[], byte[]> _computeHash;

    private readonly SortedDictionary<string, Func<T, object>> _fingerprints;

    public FingerprintBuilder(Func<byte[], byte[]> computeHash)
    {
        _computeHash = computeHash ?? throw new ArgumentNullException(nameof(computeHash));
        _fingerprints = new SortedDictionary<string, Func<T, object>>(StringComparer.OrdinalIgnoreCase);    
    }

    public static FingerprintBuilder<T> Create(Func<byte[], byte[]> computeHash)
    {
        return new FingerprintBuilder<T>(computeHash);
    }

    public FingerprintBuilder<T> For<TProperty>(Expression<Func<T, TProperty>> expression, Expression<Func<TProperty, TProperty>> fingerprint)
    {
        if (!(expression.Body is MemberExpression memberExpression))
        {
            throw new ArgumentException("Expression must be a member expression");
        }

        if (_fingerprints.ContainsKey(memberExpression.Member.Name))
        {
            throw new ArgumentException($"Member {memberExpression.Member.Name} has already been added.");
        }

        var getValue = expression.Compile();
        var getFingerprint = fingerprint.Compile();

        _fingerprints[memberExpression.Member.Name] = (Func<T, object>)(obj =>
        {
            var value = getValue(obj);
            return value == null ? default(TProperty) : getFingerprint(getValue(obj));
        });

        return this;
    }

    public Func<T, byte[]> Build()
    {
        var binaryFormatter = new BinaryFormatter();

        return obj =>
        {
            using (var memory = new MemoryStream())
            {
                foreach (var item in _fingerprints)
                {
                    binaryFormatter.Serialize(memory, item.Value(obj));
                }
                return _computeHash(memory.ToArray());
            }
        };
    }
}

For anonymous objects I added a non-generic class:

public class FingerprintBuilder
{
    public static FingerprintBuilder<T> Create<T>(Func<byte[], byte[]> computeHash, T obj)
    {
        return new FingerprintBuilder<T>(computeHash);
    }
}

It can be used like that:

var anonymousFingerprint = FingerprintBuilder
    .Create(SHA1.ComputeSHA1, new { FirstName = default(string), LastName = default(string) })
    .For(p => p.FirstName, ignoreCase: true, ignoreWhiteSpace: true)
    .For(p => p.LastName, ignoreCase: true, ignoreWhiteSpace: true)
    .Build();

anonymousFingerprint(new { FirstName = "John", LastName = "Doe" }).ToHexString().Dump();

This is supported by convenience extensions:

public static class FingerprintBuilderExtensions
{
    public static FingerprintBuilder<T> For<T, TProperty>(this FingerprintBuilder<T> builder, Expression<Func<T, TProperty>> expression)
    {
        return builder.For(expression, _ => _);
    }

    public static FingerprintBuilder<T> For<T>(this FingerprintBuilder<T> builder, Expression<Func<T, string>> expression, bool ignoreCase, bool ignoreWhiteSpace)
    {
        var format = (Func<string, string>)(input =>
        {
            if (ignoreCase)
            {
                input = input.ToUpperInvariant();
            }
            if (ignoreWhiteSpace)
            {
                input = input.Trim();
            }
            return input;
        });

        return builder.For(expression, input => format(input));
    }
}
\$\endgroup\$
3
\$\begingroup\$

Because I'm delightfully (or annoyingly) pedantic, I rather like having interfaces so that I can mock them for testing purposes. I also changed the constructor to be internal since I don't think outside assembly callers need to be calling it except through the .Create() API:

IFingerprintBuilder.cs

public interface IFingerprintBuilder<T>
{
    IFingerprintBuilder<T> For<TProperty>(
        Expression<Func<T, TProperty>> expression,
        Expression<Func<TProperty, TProperty>> fingerprint);

    Func<T, byte[]> Build();
}

FingerprintBuilder.cs (generic type version)

public sealed class FingerprintBuilder<T> : IFingerprintBuilder<T>
{
    private readonly Func<byte[], byte[]> _computeHash;

    private readonly IDictionary<string, Func<T, object>> _fingerprints;

    internal FingerprintBuilder(Func<byte[], byte[]> computeHash)
    {
        this._computeHash = computeHash ?? throw new ArgumentNullException(nameof(computeHash));
        this._fingerprints = new SortedDictionary<string, Func<T, object>>(StringComparer.OrdinalIgnoreCase);
    }

    public static IFingerprintBuilder<T> Create(Func<byte[], byte[]> computeHash) =>
        new FingerprintBuilder<T>(computeHash);

    public IFingerprintBuilder<T> For<TProperty>(
        Expression<Func<T, TProperty>> expression,
        Expression<Func<TProperty, TProperty>> fingerprint)
    {
        if (!(expression.Body is MemberExpression memberExpression))
        {
            throw new ArgumentException("Expression must be a member expression");
        }

        if (this._fingerprints.ContainsKey(memberExpression.Member.Name))
        {
            throw new ArgumentException($"Member {memberExpression.Member.Name} has already been added.");
        }

        var getValue = expression.Compile();
        var getFingerprint = fingerprint.Compile();

        this._fingerprints[memberExpression.Member.Name] = obj =>
        {
            var value = getValue(obj);

            return value == null ? default(TProperty) : getFingerprint(getValue(obj));
        };

        return this;
    }

    public Func<T, byte[]> Build()
    {
        var binaryFormatter = new BinaryFormatter();

        return obj =>
        {
            using (var memory = new MemoryStream())
            {
                foreach (var item in this._fingerprints)
                {
                    binaryFormatter.Serialize(memory, item.Value(obj));
                }

                return this._computeHash(memory.ToArray());
            }
        };
    }
}

FingerprintBuilder.cs (anonymous type version)

public static class FingerprintBuilder
{
    public static IFingerprintBuilder<T> Create<T>(Func<byte[], byte[]> computeHash, T obj) =>
        new FingerprintBuilder<T>(computeHash);
}

FingerprintBuilderExtensions.cs

public static class FingerprintBuilderExtensions
{
    public static IFingerprintBuilder<T> For<T, TProperty>(
        this IFingerprintBuilder<T> builder,
        Expression<Func<T, TProperty>> expression) => builder.For(expression, _ => _);

    public static IFingerprintBuilder<T> For<T>(
        this IFingerprintBuilder<T> builder,
        Expression<Func<T, string>> expression,
        bool ignoreCase,
        bool ignoreWhiteSpace)
    {
        Func<string, string> format = input =>
        {
            if (ignoreCase)
            {
                input = input.ToUpperInvariant();
            }

            if (ignoreWhiteSpace)
            {
                input = input.Trim();
            }

            return input;
        };

        return builder.For(expression, input => format(input));
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Also, because I hate typing, I might recommend a using HashFunc = System.Func<byte[], byte[]>; at the top of the source file so you don't have to repeat that wordy generic in parameter lists. \$\endgroup\$ – Jesse C. Slicer Oct 4 '18 at 22:10
  • 1
    \$\begingroup\$ The idea with the interface is good... I also interfacezie nearly everything, however I think I'll take it one step further and will create a dedicated delegate for the Func that the builder creates and use this for DI. \$\endgroup\$ – t3chb0t Oct 5 '18 at 6:00
2
\$\begingroup\$

Great implementation, I would just suggest allowing the definition without passing the formatting expression, just in case it's not necessary:

public FingerprintBuilder<T> For<TProperty>(Expression<Func<T, TProperty>> memberExpression, Expression<Func<TProperty, TProperty>> formatExpression = null) {
    if (!(memberExpression.Body is MemberExpression)) {
        throw new ArgumentException("Expression must be a member expression");
    }

    string memberName = ((MemberExpression)memberExpression.Body).Member.Name;
    if (_fingerprints.ContainsKey(memberName)) {
        throw new ArgumentException($"Member {memberName} has already been added.");
    }

    var getValue = memberExpression.Compile();

    if (formatExpression != null) {
        var getFingerprint = formatExpression.Compile();

        _fingerprints[memberName] = (Func<T, object>)(obj => {
            var value = getValue(obj);
            return value == null ? default(TProperty) : getFingerprint(getValue(obj));
        });
    } else {
        _fingerprints[memberName] = (Func<T, object>)(obj => {
            var value = getValue(obj);
            return value == null ? default(TProperty) : value;
        });
    }

    return this;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks ;-) yeah, this is a good idea however I would create an extension that passes an empty expression - don't like nulls ;-P this means the else part I'd put in another method, preferabely an extension. \$\endgroup\$ – t3chb0t Oct 4 '18 at 19:19
  • 1
    \$\begingroup\$ @t3chb0t you already have an extension method that works for that: public static FingerprintBuilder<T> For<T, TProperty>(this FingerprintBuilder<T> builder, Expression<Func<T, TProperty>> expression). It works for the generic and non-generic versions alike. \$\endgroup\$ – Jesse C. Slicer Oct 4 '18 at 21:53
  • \$\begingroup\$ @JesseC.Slicer oh, crappy-crap - totaly forgot about this one - implemented, used and removed from the brain-cache ;-) \$\endgroup\$ – t3chb0t Oct 5 '18 at 5:58
1
\$\begingroup\$

This is supported by convenience extensions:

public static FingerprintBuilder<T> For<T>(
         this FingerprintBuilder<T> builder, 
         Expression<Func<T, string>> expression, StringOptions options)
     {
         Func<string, string> format = input =>
     {
        if (ignoreCase)
        {
            input = input.ToUpperInvariant();
        }

        if (ignoreWhiteSpace)
        {
            input = input.Trim();
        }

        return input;
    };

    return builder.For(expression, input => format(input));
}

Not convenient enough for extended unicode and combining characters. Unless you only work with 16-bit characters ;-)

[Flags]
public enum StringOptions : uint
{
    None = 0,
    IgnoreCase = 1 << 0,
    IgnoreWhiteSpace = 1 << 1,
    PrimaryForm = 1 << 2,
    CompatabilityForm = 1 << 3,
    NormalisationFormMask = PrimaryForm | CompatabilityForm
}

public static FingerprintBuilder<T> For<T>(
        this FingerprintBuilder<T> builder, 
        Expression<Func<T, string>> expression, StringOptions options)
    {
        var format = (Func<string, string>)(input =>
        {
            if (options.HasFlag(StringOptions.NormalisationFormMask)) {
                var form = default(NormalizationForm);
                var isPrimary = options.HasFlag(StringOptions.PrimaryForm);
                var isCompatible = options.HasFlag(StringOptions.CompatabilityForm);
                // yes, could be written more elegantly
                if (isPrimary) {
                    if (isCompatible) {
                        form = NormalizationForm.FormKC;
                    }
                    else {
                        form = NormalizationForm.FormC;
                    }
                }
                else {
                    if (isCompatible) {
                        form = NormalizationForm.FormKD;
                    }
                    else {
                        form = NormalizationForm.FormD;
                    }
                }
                input = input.Normalize(form);
            }

            if (options.HasFlag(StringOptions.IgnoreCase)) {
                input = input.ToUpperInvariant();
            }
            if (options.HasFlag(StringOptions.IgnoreWhiteSpace)) {
                input = input.Trim();
            }
            return input;
        });

        return builder.For(expression, input => format(input));
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ I see I should study string formats too... \$\endgroup\$ – t3chb0t May 26 at 7:12
0
\$\begingroup\$

Any hash is a probability of having a kind of data. So each object should have a hash and an index to the correct data. Once you calculate the hash you have to compare the data. If different data with the same hash, you add the new data with the index+1

\$\endgroup\$
  • \$\begingroup\$ I guess you mean a hash for an entire object, right? This wouldn't work in my case because I have some properties that are only for informational purposes, e.g. CreatedOn, I don't want it to be part of the equality-hash because objects with same data but created at different times should still be considered the same. \$\endgroup\$ – t3chb0t Feb 28 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.