Hello,

I need to create a Hash Table for a particular Hash Function in my program. I need to be able to place multiple integers in the same bucket, which will obviously cause collision issues.

What is the fastest way to go about this? Should I use a dynamic array, associative array, linked list, etc?

I'm going to be using the Tango Library, and have though about using the HashMap, but it seems like overkill for what I want to do? I'm willing to trade memory for speed (quick lookups and iterating through the buckets).

Any ideas? If you need more info I can always present the particular application I'm trying to create.....

Thanks,
Mason

Ok, I think I may have found a solution.

I'm going to create my Hash Table using the Tango HashSet container. I'm sure I could have used another container, but since my primary interest is speed I'll go with the HashSet.

I'll initialize the Hast Table like so:

        alias HashSet!(int) objectSet;
	objectSet[GRID_SIZE] hashTable;

	for(int i = 0; i < GRID_SIZE; i++)
		hashTable[i] = new objectSet;

The hashTable[] array represents the entire Hash Table. Each individual bucket in the table is created with a HashSet container, and I'll use a Hash Function to determine which bucket I place my object index into.

Is this a sound method or foolish? My primary goal is speed; I need my Hash Table to be as efficient as possible.

Comments?

Thanks, Mason

"Mason" <mason.green@gmail.com> wrote in message news:etrmpj$1347$1@digitalmars.com...
> Hello,
>
> I need to create a Hash Table for a particular Hash Function in my program. I need to be able to place multiple integers in the same bucket, which will obviously cause collision issues.

Don't AAs do everything you need already?  They're a hash table with separate chaining implemented with binary trees, and ints already have a hash function for them..

Mason wrote:
> Ok, I think I may have found a solution.
> 
> I'm going to create my Hash Table using the Tango HashSet container. I'm sure I could have used another container, but since my primary interest is speed I'll go with the HashSet.
> 
> I'll initialize the Hast Table like so:
> 
>         alias HashSet!(int) objectSet;
> 	objectSet[GRID_SIZE] hashTable;
> 
> 	for(int i = 0; i < GRID_SIZE; i++)
> 		hashTable[i] = new objectSet;
> 
> The hashTable[] array represents the entire Hash Table. Each individual bucket in the table is created with a HashSet container, and I'll use a Hash Function to determine which bucket I place my object index into.
> 
> Is this a sound method or foolish? My primary goal is speed; I need my Hash Table to be as efficient as possible.
> 
> Comments?
> 
> Thanks, Mason 

Hmmmmmm. Sounds like a bad idea to me. Why not just use an associative array? That's what they're there for.

I can't think of a good reason for creating an array of HashSets. Though in the past I've used this code as a MultiMap approximation:

  HashMap!(KeyType, HashSet!(ValueType))

Describe your application, and I think we can describe a better way of implementing it than what you're currently doing.

--benji

Benji Smith Wrote:

> Hmmmmmm. Sounds like a bad idea to me. Why not just use an associative  array? That's what they're there for.

Thanks for the help. I need to create a Hash Table that I will be using to implement the following research paper:

http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip

It basically uses a unique hash function and hash table for rigid body collision detection. Page 2 shows a good diagram.

Will an AA allow me to index objects into the same "bucket" using my own hash function? Since I need to potentially index multiple objects into the same "bucket" I created the Hash Table as a 1D array with a dynamic list (HashSet) of objects in each cell.....

Thanks,
Mason