Best practices for overriding isEqual: and hash

by

Start with

 NSUInteger prime = 31;
 NSUInteger result = 1;

Then for every primitive you do

 result = prime * result + var

For objects you use 0 for nil and otherwise their hashcode.

 result = prime * result + [var hash];

For booleans you use two different values

 result = prime * result + ((var)?1231:1237);

Explanation and Attribution

This is not tcurdt’s work, and comments were asking for more explanation, so I believe an edit for attribution is fair.

This algorithm was popularized in the book “Effective Java”, and the relevant chapter can currently be found online here. That book popularized the algorithm, which is now a default in a number of Java applications (including Eclipse). It derived, however, from an even older implementation which is variously attributed to Dan Bernstein or Chris Torek. That older algorithm originally floated around on Usenet, and certain attribution is difficult. For example, there is some interesting commentary in this Apache code (search for their names) that references the original source.

Bottom line is, this is a very old, simple hashing algorithm. It is not the most performant, and it is not even proven mathematically to be a “good” algorithm. But it is simple, and a lot of people have used it for a long time with good results, so it has a lot of historical support.

More Related Contents:

  1. Implementing -hash / -isEqual: / -isEqualTo…: for Objective-C collections
  2. How dangerous is it to compare floating point values?
  3. “Thread 1: stopped at breakpoint” error when initializing an NSURL object
  4. How do I wait for an asynchronously dispatched block to finish?
  5. Objective-C Static Class Level variables
  6. How to scale a UIImageView proportionally?
  7. Retain cycle on `self` with blocks
  8. Calculating the number of days between two dates in Objective-C
  9. Warning: “format not a string literal and no format arguments”
  10. filtering NSArray into a new NSArray in Objective-C
  11. Reading and writing images to an SQLite DB for iPhone use
  12. Create an array of integers property in Objective-C
  13. Store data in MKAnnotation?
  14. capturing self strongly in this block is likely to lead to a retain cycle
  15. Use regular expression to find/replace substring in NSString
  16. Git – how do I view the change history of a method/function?
  17. ARC – The meaning of __unsafe_unretained?
  18. Creating a selector from a method name with parameters
  19. How is release handled for @synthesized retain properties?
  20. Format string, integer with leading zeros
  21. Getting the visible rect of an UIScrollView’s content
  22. Dismiss modal view form sheet controller on outside tap
  23. How to use single storyboard uiviewcontroller for multiple subclass
  24. Can I pass a block as a @selector with Objective-C?
  25. Use Data From Class Without A New Init
  26. how to remove subviews from scrollview?
  27. How to make a smooth, rounded, volume-like OS X window with NSVisualEffectView?
  28. Objective C: How to create a multi-line UITextField? [duplicate]
  29. Weird error message in Xcode 4.3 with LLDB
  30. What is the difference between a __weak and a __block reference?

Leave a Comment