HashTable object
BlitzMax Forums/BlitzMax Programming/HashTable object
| ||
Ok, i figured id share this type/class with the community.. already sent a copy to noel, but no doubt others would like a basic hashtable system too.. this is my first bmax class - perhaps not great, but it does the job...anyway enjoy ;) feel free to credit me if you use it :] ''InsertEntry(name:string,o:object) - add an object to the table, the name is used to '' to generate an index 0-255, selecting the list. '' ''RemoveEntry(name:string) - if you need to remove an object. '' ''GetEntry(name:string) - grab an entry, you must cast is back to its original type, '' myobject=myType(GetEntry(name:string)) '' '' ''Flush() - removes all objects from the hash table '' '' ''all entries should have unique names - you should first getEntry(), if this returns ''null - its safe to insert the new object, if it returns a valid object, you may want ''to return this object back to the user... ''''''''''''''''''''''''''' '' ''HASHTABLE OBJECT '' ''- M.Laurenson/Defoc8 2006 '''''''''''''''''''''''''''' Type gHashTable Field table:TList[] Method New() table=table[..256] For Local n:Int=0 To 255 table[n]=CreateList() Next EndMethod Method genIndex(name$) Local val:Int=0 For Local n:Int=0 To name.length-1 val=val+(name[n]^2) Next val=(val&255) Return val EndMethod Method insertEntry(name:String,obj:Object) Local index:Int=genIndex(name$) Local entry:gHashEntry=New gHashEntry entry.name=name entry.obj=obj entry.link=ListAddLast(table[index],entry) EndMethod Method removeEntry(name:String) Local index:Int=genIndex(name) For Local entry:gHashEntry=EachIn table[index] If(entry.name=name) RemoveLink(entry.link) Return EndIf Next EndMethod Method getEntry:Object(name:String) Local index:Int=genIndex(name) For Local entry:gHashEntry=EachIn table[index] If(entry.name=name) Return(entry.obj) EndIf Next Return Null EndMethod Method flush() For Local n:Int=0 To 255 ClearList(table[n]) Next EndMethod Method getEntryCount(index:Int) Return CountList(table[index]) EndMethod EndType Type gHashEntry Field name:String Field obj:Object Field link:TLink EndType |
| ||
table=table[..256] You should use a prime number as the number of buckets. Like 257. Otherwise it looks like an okay implementation. |
| ||
hmmm...i dont actually see why the number of buckets should be prime - doesnt this depend on the system used to generate the bucket selection? regardless, i have tested the distrubution on multiple data sets & the results have been good - its a simple system, this doesnt mean its bad. Anyway- the code is public, so anyone can modify it.. |
| ||
I figure I may as well share the version I molested... hash.c "If it ain't broke, don't fix it" doesn't really apply to Def's code ;) Then again, I'm rather notorious for fixing that which isn't broken. |
| ||
i dont actually see why the number of buckets Yes. Which should also use primes to reduce the risk of hash collisions. Perhaps you could also distribute your test code, so others could have a go at testing it? Have you tried adding the canonical location of all files on your root drive, for example? I know that dataset in particular took down early Java hashing algorithms (because they where radix based, and thus would generate identical hashes, for nearly identical keys, where as a solid hashing algorithm generates wildly different hashes from similar keys).should be prime - doesnt this depend on the system used to generate the bucket selection? its a simple system, this doesnt mean its bad. I'm not saying it is. |
| ||
Can someone show a mini demo of the hash tables in use please |
| ||
Well, first I have to say : nice thing. but as second I have to ask: Isn't a Hashtable Type already included in BMAX which is called TMap. And what is the advantage of this system in comparison to the TMap type? |
| ||
hey im new to bmax - i jst thought id share stuff :p - and good stuff noel ;) :] |
| ||
Don't get me wrong,Your stuff is very good. I only was thinking about it. So keep up and share more stuff ;) |
| ||
Isn't a Hashtable Type already included in BMAX which is called TMap. No. TMap is a Set implemented as a binary search tree. And what is the advantage of this system in comparison to the TMap type? 'This system' has close to constant look-up times. TMap has Log(n). Also this hashTable implementation doesn't appear to be a Set (that is, the same object can be indexed more than once).It's a trade of between speed and space. |
| ||
Duckstab: Here you go. It's a pseudo-managed resource handler. You request a resource, it's loaded into memory, and then only unloaded when all the banks created with its buffer are deleted (or when you call UnloadResources( )). There are better ways to do this, but this is a rudimentary example. |