[[!meta copyright="Copyright © 2009, 2010, 2011, 2012, 2013, 2014 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_hurd]]

  * Hurd libihash

      * old

      * new

  * hurd-l4 libhurd-ihash


# Open Issues

## Collisions

Viengoos: [[microkernel/viengoos/projects/new_hash_function]].


### IRC, freenode, #hurd, 2008/2009

    <neal> so, we need a new ihash implementation
    <neal> marcusb: When 80% full, the collision rate is very high.
    <neal> marcusb: I tested using 512mb / 4096 entries
    <neal> marcusb: Changing the load factor to 30% resulted in my program
      running more than an order of magnitude faster.
    <marcusb> yeah, it shouldn't get so full
    <marcusb> don't we do an exponential back-off in the array size?
    <marcusb> of course it's clear we can do much better
    <marcusb> the ihash algo is very simple
    <marcusb> I'm not even sure it makes much sense to have a generic
      library


## Reader-Writer Locks

### IRC, freenode, #hurd, 2013-12-09

    <teythoon> btw, why don't we use rwlocks for serializing access to our
      hash tables ?
    <braunr> teythoon: we definitely could
    <teythoon> ok
    <braunr> teythoon: we definitely could use rcu *whistles*
    <teythoon> should we ?
    <braunr> i don't know
    <teythoon> yeah, ofc
    <braunr> rwlocks have some overhead compared to mutexes
    <braunr> and our mutexes are already quite expensive
    <braunr> our condition variables are also not optimized


# [[community/gsoc/project_ideas/Object_Lookups]]


# Alternatives?

  * glibc

      * include/inline-hashtab.h

      * locale/programs/simple-hash.h

      * misc/hsearch_r.c

      * NNS; cf. f46f0abfee5a2b34451708f2462a1c3b1701facd

  * libstdc++: `unordered_map`, `tr1/unordered_map`, `ext/hash_map`

  * libiberty: `hashtab.c`

  * <http://cmph.sourceforge.net/>

  * <http://libhashish.sourceforge.net/>

  * <http://www.azillionmonkeys.com/qed/hash.html>

  * CCAN's htable, idtree

  * Not actually use a hashing data structure; see [[libports]], *Open Issues*,
    *IRC, freenode, #hurd, 2013-11-14*.