Re: Fast hash of NSData?
Re: Fast hash of NSData?
- Subject: Re: Fast hash of NSData?
- From: Graham Cox <email@hidden>
- Date: Fri, 29 Nov 2013 23:19:26 +0100
On 29 Nov 2013, at 10:49 pm, Kyle Sluder <email@hidden> wrote:
> In this scheme, if there is a hash collision, you lose user data. That should be a non-starter. You *must* do a full bytewise comparison in case of collision.
I wouldn’t say a non-starter. In practice, the odds of this are exceedingly small *provided* the hash function is good. My original one was dreadful, so yes, we had some initial problems with images suddenly turning into different ones. Using SHA-1 we’ve never had that issue recur, though in theory it could. According to the discussion on Stack Exchange that Eric pointed out, the fnv1a has very good randomness, and using the 64-bit variant it should mean the odds against a collision should be huge.
> You also have another, damn-quick "hash key" that takes zero disk access to compute: -[NSData length].
Yep, that’s a great idea.
> Use the size as a primary key, then a reasonably low-collision/low-complexity hash algorithm as a secondary key. That seems like a reasonable compromise between runtime efficiency and implementation simplicity.
>
> You could make the keys of your dictionary a custom object:
Good idea, though ideally it would only compute the actual hash lazily if it got as far as needing to (i.e. when the length matched). I’ll give it a go.
—Graham
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden