Minimal perfect hash function that retains mapping of existing keys on expansion - Stack Overflow

admin管理员组

文章数量:1122846

I have a set of N integers in the range 0 to 255 which must be mapped using a minimally perfect hash function to the range [0, N-1]. However, this set of integers can grow dynamically. In the case where the set grows, is there a way to implement a minimal perfect hash function that retains the mapping of the existing elements when new elements are added to a set?

For e.g. consider this mapping:

11 -> 0
27 -> 1

When a new element 17 is added, I want it to be mapped to index 2 so that the new mapping is like this:

11 -> 0
27 -> 1
17 -> 2

This is because I want to avoid having to rehash all the elements when my set of integers expand. Is this theoretically possible?

I have a set of N integers in the range 0 to 255 which must be mapped using a minimally perfect hash function to the range [0, N-1]. However, this set of integers can grow dynamically. In the case where the set grows, is there a way to implement a minimal perfect hash function that retains the mapping of the existing elements when new elements are added to a set?

For e.g. consider this mapping:

11 -> 0
27 -> 1

When a new element 17 is added, I want it to be mapped to index 2 so that the new mapping is like this:

11 -> 0
27 -> 1
17 -> 2

This is because I want to avoid having to rehash all the elements when my set of integers expand. Is this theoretically possible?

• hash
• perfect-hash

Share Improve this question Follow asked Nov 22, 2024 at 12:46 jeffreyveonjeffreyveon 13.8k1818 gold badges8585 silver badges139139 bronze badges 4

• 2 This is probably better suited at cs.stackoverflow.com or math.stackoverflow.com – derpirscher Commented Nov 22, 2024 at 12:55
• Can we use like this? 1. create an empty list 2. Everytime you get a new element you add it to the list and index of that element becomes its hash. I think it fulfils all your requirement. Infact I will dare and post it as an answer – Anubhav Sharma Commented Nov 22, 2024 at 13:46
• Mathematically speaking Anubhav’s solution is the only possible way to do this. Consider that the elements can be added in any order: therefore, your mapping function needs to somehow store enough information to reconstruct an arbitrary insertion ordering. That is by definition a list of the elements by insertion order. There won’t be a simpler solution. – nneonneo Commented Nov 22, 2024 at 14:10
• Dynamic perfect hashing won't do it? – Jim Mischel Commented Nov 23, 2024 at 6:40

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 2

Consider the hashing algorithm which is defined as:

list = [];
hash(x){
    if(x not in list){
        list.add(x);
    }
    return list.indexOf(x);
};

Since all your numbers are in range [0,255], number of elements in list will never go beyond 256. Even if you increase the range, it works as long as your range is finite.

Also, indexOf operation preserves the previous hash values and ensures one to one mapping for value-hash pair.

A slight update to Anubhav's solution which is a bit more performant (Python syntax, using the dict hashmap type):

phf = {}
def phf_hash(k):
    """
    Hash a key with the perfect hashing function.
    Expand the PHF if the key has not been seen yet.
    """
    if k not in phf:
        phf[k] = len(phf)
    return phf[k]

Example usage:

>>> phf_hash(11)
0
>>> phf_hash(27)
1
>>> phf_hash(17)
2
>>> phf_hash(27)
1
>>> phf_hash(11)
0

本文标签： Minimal perfect hash function that retains mapping of existing keys on expansionStack Overflow