diff options
Diffstat (limited to 'microkernel/viengoos/projects/new_hash_function.mdwn')
| -rw-r--r-- | microkernel/viengoos/projects/new_hash_function.mdwn | 22 |
1 files changed, 22 insertions, 0 deletions
diff --git a/microkernel/viengoos/projects/new_hash_function.mdwn b/microkernel/viengoos/projects/new_hash_function.mdwn new file mode 100644 index 00000000..d0374720 --- /dev/null +++ b/microkernel/viengoos/projects/new_hash_function.mdwn @@ -0,0 +1,22 @@ +[[!meta copyright="Copyright © 2008, 2009, 2010 Free Software Foundation, +Inc."]] + +[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable +id="license" text="Permission is granted to copy, distribute and/or modify this +document under the terms of the GNU Free Documentation License, Version 1.2 or +any later version published by the Free Software Foundation; with no Invariant +Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license +is included in the section entitled [[GNU Free Documentation +License|/fdl]]."]]"""]] + +[[!tag open_issue_viengoos]] + +The current hash function in libhurd-ihash results in a lot of +collisions when the hash table is 80% full. To overcome this, we keep +hash tables at most 30% full. This represents a fair amount of +overhead. Find a better algorithm. There can either be one that is +appropriate in the general case or one that works well in a relevant, +specific case, e.g., viengoos/object.c uses a hash to find the object +corresponding to a frame, which is keyed on its physical address. + +Note that this applies to the Hurd's [[hurd/libihash]], too. |