Merge branch 'master' of flubber:~hurd-web/hurd-web

1 files changed, 19 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..1747511d
--- /dev/null
+++ b/microkernel/viengoos/projects/new_hash_function.mdwn
@@ -0,0 +1,19 @@
+[[!meta copyright="Copyright © 2008, 2009 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.