• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
3
Question by Brian-Kehrer · Jan 10, 2010 at 08:52 PM · optimizationstructhash

What are the properties of a good key hash?

I'm attempting to create a key hash for a custom struct with two integer values, x and y - for use in a hashtable.

I only really care about values between -10000 to +10000, and 90% of the time it will likely be operating between -100 and +100. I don't care at all about security.

From some basic research, I've learned that an optimal performing hash has very few or no collisions. I believe I can achieve this across the relevant set by treating x and y as 16 bit values.

Also it is beneficial to have adjacent input values create non-adjacent, and preferably very different output values.

How important is the non-adjacency in performance? And are there any other major considerations? Would one want to allow some collisions in favor of non-adjacency? I am using this not for security, but rather as a key value in a hashtable, so lookup speed is important. (I'm also caching the hashcode in a readonly variable at initialization, so don't worry about that).

public override int GetHashCode() { //A very simple unique hash, but values are adjacent //hash = (x<<16) +y; **EDIT: This is the function to use** hash = (x<<16) +y +32768;

 /*A mildly complicated hash from the internets, 
   non adjacent values, caused some collisions.  
   (checking from -250 to +250 in x and y required 90s
   Checking 20000 would take a very long time)*/
 //hash -= (hash&lt;&lt;6);
 //hash ^= (hash&gt;&gt;17);
 //hash -= (hash&lt;&lt;9);
 //hash ^= (hash&lt;&lt;4);
 //hash -= (hash&lt;&lt;3);
 //hash ^= (hash&lt;&lt;10);
 //hash ^= (hash&gt;&gt;15);

}

Comment
Add comment
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

1 Reply

· Add your reply
  • Sort: 
avatar image
6
Best Answer

Answer by Brian-Kehrer · Jan 10, 2010 at 09:54 PM

From some basic testing, it seems as though the benefit of any superior hashing algorithm in spacing and adjacency is far outweighed by the cost of actually calculating the hashcode, particularly in structs where they are frequently recalculated.

Simple hashcodes would appear to be superior.

That said, collisions do appear to have a very significant impact on performance.

One recommended hash algorithm on MSDN for such a problem, was 100x slower than my short sample code above for lookup, and nearly froze my computer for hashtable generation - most likely due to lots of collisions in the data set.

int x;
int y;
//hash = x^y; //DO NOT USE THIS, QUITE TERRIBLE

Whereas this simple computation is very fast

//hash = (x<<16) +y;  //does not use full 16 bits
hash = (x<<16) +y +32768;  //need the offset

From this it would seem if you are interested in generating key values, avoiding collisions should be the number 1 concern, and a fast hashcode algorithm number 2.

The result looks like this

public Point(int x, int y){ this.x = Mathf.Clamp(x, -32768, 32767); this.y = Mathf.Clamp(y, -32768, 32767);

 hash = (this.x&lt;&lt;16) +this.y +32768;


}

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.



Follow this Question

Answers Answers and Comments

1 Person is following this question.

avatar image

Related Questions

Optimization on list handling 2 Answers

How do I change GUI elements from outside of the OnGUI function? 3 Answers

Optimizations in scripts 1 Answer

Tagging Alternatives 2 Answers

Array Allocations, references or whole objects 1 Answer


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges