GNOME Bugzilla – Bug 380426
GHashTable: finding a key by value.
Last modified: 2011-06-04 03:10:09 UTC
The attached patch provides g_hash_table_find_by_value, which returns the first key that is associated with a certain value. A patch for similar functionality was proposed in 2004, but that function used a callback, which is unnecessary for doing reverse lookups. Refer to http://mail.gnome.org/archives/gtk-devel-list/2004-June/msg00109.html Best regards, Bastiaan Veelo.
Created attachment 77331 [details] [review] Provides g_hash_table_find_by_value().
Patch looks good to me but I am not in the position to commit it.
(In reply to comment #2) > Patch looks good to me but I am not in the position to commit it. Thanks! Let's hope that someone in that position spots this then.
A reverse lookup of a random hash key by value doesn't sound very useful to me. If you need this you should probably think about your application's way of organizing its data. Moreover, the return value would really be some random key, from a functional point of view it makes more sense to have a function that returns *all* keys for a given value.
Btw, all the above comment actually means: "What is the use case?"
my use case: string to uint hash table, where the common case is 1:1 but there's the possibility of a N:1 reverse case. the common case warrants a hash table for fast look-up, but the reverse case makes searching for a key desirable so that you don't have to implement weird hash tables with composite values. this would be a use-case for GRelation, if GRelation wasn't so utterly limited (it's basically useless for anything that's not an integer because it lacks API to compare and free values).
given that there are at least 2 different variants you could want find_by_value() to operate in (find first, find all) and that O(n) find operations really are something that hash tables intentionally are *NOT* optimized for, and also given that we support linear find operations already with g_hash_table_find() (albeit callback based), i don't think adding another two variants find_all_values and g_hash_table_find_by_value() is a very good idea. i've documented the performance pitfalls with hash table reverse lookups with the find and foreach functions now: http://svn.gnome.org/viewcvs/glib/trunk/glib/ghash.c?r1=5444&r2=5587&pathrev=5587 and if possible, i'd like to keep it at that when it comes to slow no-designed-for APIs. however, for convenince -just like we provide g_direct_hash() and friends-, two GHRFunc callback implementations could be provided that implement find_first and find_all behavior and can be used with g_hash_table_find() (the mild inconvenience of specfying a particular callback for behavior instead of having two fresh new API calls for it should really be ok for a function that should normally should not be called anyways).
I agree with this assessment; thanks for putting it into words, Tim.