So I'd change that, so that key string/numbers (and PMCs) don't have the actual string/number/PMC inside, but the constant table index of the item. This avoids the linear search for the index.
This also means, that key_new_cstring (and _number, if one needs that) generates a constant table entry and that key_string returns the item from the constant table[1]. Now to avoid many duplicates it would be best to cache these entries and do a hash lookup first.
This all is also related with the discussion of constant PMCs/STRINGs, we had some time ago "[RfC] constant PMCs and classes" and with the lack of "get_string_keyed_str" and friends for hash lookup.
E.g. pmc_register() currently generates 3 (three) intermediate key PMCs for hash lookup in the classname_hash(). The class and object code has such lookup all over the place and it will be more in the long run.
Comments welcome, leo
[1] in combination with the PObj_constant_FLAG - a really dynamic variant would work like now, albeit by far the most usage of such keys is truely constant.