PennMUSH Community

Ticket #7321 (closed suggested feature: fixed)

Opened 2 years ago

Last modified 1 year ago

perfect hashing

Reported by: raevnos Assigned to: devteam
Priority: trivial Milestone: 1.8.3p4
Keywords: Cc:
Visibility: Public

Description

Perfect hashing is a way to generate a hash function that guarantees a single index into an array to find an element with no collisions. The downside is that the set of possible keys has to be known ahead of time so a program (Like gperf) can create the appropriate function. Consider using this approach for the hash tables in Penn that are pretty static - HTML elements and builtin functions.

On a more serious note, looking at the Players htab on M*U*S*H, we either need to change the hash function or the resizing checks.... and then there's Obj Data...

Change History

05/08/07 19:48:57 changed by raevnos

It turns out to be pretty easy to use gperf for this. Also consider doing so for comman d switch lookup (Or a ptab might be better for that, since we do exact and first matching prefix lookup at various times.)

06/14/07 22:16:02 changed by raevnos

I merged in gperf-generated lmath and allowed-html-tags perfect hash tables tonight (To devel from my experimental branch), and reduced the starting size of the objdata hashtable. It really doesn't need to be the size of the database, given how little it's actually used right now.

08/24/07 15:01:24 changed by raevnos

  • status changed from new to closed.
  • resolution set to fixed.
  • milestone set to 1.8.3p4.