www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Hash Table

reply Mason <mason.green gmail.com> writes:
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
Mar 21 2007
next sibling parent reply Mason <mason.green gmail.com> writes:
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
Mar 21 2007
parent reply Benji Smith <dlanguage benjismith.net> writes:
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
Mar 21 2007
parent Mason <mason.green gmail.com> writes:
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
Mar 22 2007
prev sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"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..
Mar 21 2007