tags:

views:

50

answers:

1
Q: 

Collision-free fixed-size hash table

With 1 good hash function, how can I create a static hash table for N distinct keys that is collision free? I know the keys in advance, so the hash table doesn't have to be resized (hence it is static).

Related question: will it always be possible to find a hash table with no collisions?

+1  A: 

With a static set, why would you need hashing at all? An indexed array should do just fine and you don't have to make it bigger than N.. For example, if you can have an incrementing ID for the objects and use that as the hash key, you get no collisions and effectively the structure you've created is an array and the lookup is at least as fast as with a hashtable.

Mikko Wilkman  2010-09-09 08:37:55
I know the set of keys stored in the hash table ahead of time, but I don't know what keys the user will supply at runtime. The user may enter an invalid key that would cause the lookup to fail.
Matt Fichman  2010-09-09 12:36:16
Ok then I guess you'd anyway need some mapping from the key to the array index so it might not work anyway. I'd just make sure the hashcode algorightm of the key is good and keep the table big enough to minimize collisions. Is it really critical to be 100% sure there's no collisions?
Mikko Wilkman  2010-09-10 10:12:41

related questions

C++ - static variables initialisation order
Performance of using static methods vs instantiating the class containing the methods
Unresolved external symbol on static class members
Are static class instances unique to a request or a server in ASP.NET?
Asp.Net Static method to refresh page
Problem with static library in C++
Best Static Website Generator
Initializing static objects - Code design question
Order of static constructors/initializers in C#
Alternative to libraries of static classes
What is data area?
Alternatives to static methods in Java
Tool to optimize C# using statements?
Refactoring global to local. Should they be static or not?
Php Check If a Static Class is Declared
Variable declarations in header files - static or not?
Why would a static inner interface be used in Java?
Static class variables in Python
When should a method be static?
Long-term Static Page Caching
using too much static bad or good ?
ASP.Net: Using System.Web.UI.Control.ResolveUrl() in a shared/static function
Why can't I declare static methods in an interface?
Generics in c# & accessing the static members of T
How do you create a static class in C++?