Re: Hash Code
On Tue, 20 May 2008 21:17:19 +0100, j1mb0jay wrote:
Would it make sense to only use the secure hash when the table size
exceeds the max value for an integer (2^32) and then at that point
rather than using an array use a specially implemented doubly linked
list. Although after a point you would have to start using B-Trees as it
would not all fit in memory at anyone time.
Probably not. Secure hashes are slow. You could use some kind of
checksum and get better performance. You probably don't really need a
checksum either. It really depends on the data.
Would this allow fast search access for huge amounts of data, or would
it be slow and nasty because of the expensiveness of Hash and the
greater time complexity required access time for each element in the
list (compared to the array).
You would no longer have the O(1) performance of a hash table. You would
probably want to look at some other algorithm. On the other hand, you
could use an array of arrays and get the O(1) performance that you are
missing using a list. I'm not looking at the interface now, but you may
find that the Collections interface just doesn't fit well for a larger
collection than it already handles. There have been other threads
recently discussing the problems with this.
Are you really going to be dealing with more than 2 billion entries in
your map?
I currently have a the hash table implemented and will add the logging
as requested. Although i do already know that after inserting 6 million
unique words into a hash table with a size of 10 million the longest
link list contained 13 items. Which means that the time complexity for a
search was O(13) from 6 million items.
That really isn't too bad. Look at the average case. BTW, O(13) and O
(1) are the same. This isn't really O(13) either. When we say that a
hash table is O(1) what we are assuming is that their are no collisions.
Everyone knows this isn't true, but if the number of collisions is low,
it is a reasonable simplification.
I understand that for the hash tables with a size of less that 2^32 that
the normal 32bit hash value is more than enough, i was just wondering
for hash tables that are larger.
Use a larger hash value then, but probably not a secure hash. Secure
hashes are expensive. You don't need them.
--
Kenneth P. Turvey <kt-usenet@squeakydolphin.com>