2
$\begingroup$

Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts?

Strings are quite often of the form of prefix + postfix, where both prefix and postfix may repeat.

The mapping should be stable in a sense that if the mapping needs to be extended by a new set of strings, then the new mapping works identically to the old one for "old strings". New prefixes and postfixes can be introduced in the extension. Postfixes and prefixes can be empty, but the string can't be. Two different strings can't point to the same integer, so the mapping is an injection.

Example:

  mapping("prefix1postfix1") -> 1021
  mapping("prefix1postfix2") -> 1031
  mapping("prefix2postfix1") -> 1121

One obvious approach is to just store the mapping, and assign sequential numbers to the new strings, but I wonder if there is some guaranteed way to go without "hash collisions" up to some fraction of the limited integer space without the need to memorize assignments? How it may depend on the numbers of prefixes/postfixes or their ratio?

I suspect there may be some very old research on this topic as well as the result may be negative, but still curious if there is some pleasant surprise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.