fork download
copy 
  1. # Generate perfect hash table.
  2.  
  3. def hasher(key, displacement, shift):
  4.     KNUTH_CONSTANT = 0x9E3779B1
  5.     return (((key ^ displacement) * KNUTH_CONSTANT) & 0xFFFFFFFF) >> shift
  6.  
  7. def build_perfect_hash(keys):
  8.     keys_size = len(keys)
  9.     # Round up lookup size to nearest power of two.
  10.     lg2 = (keys_size-1).bit_length() if keys_size > 0 else 0
  11.     lookup_size = 2**lg2
  12.     shift = 32 - lg2
  13.  
  14.     lookup_slots = {}
  15.     displacement_table = [0] * lookup_size
  16.     displacement_limit = 10000
  17.  
  18.     # Hash keys into buckets (displacement=0).
  19.     buckets = {}
  20.     for key in keys:
  21.         displacement_slot = hasher(key, 0, shift)
  22.         buckets.setdefault(displacement_slot, []).append(key)
  23.  
  24.     # Order buckets largest to smallest.
  25.     buckets_items = sorted(buckets.items(), key=lambda item: len(item[1]), reverse=True)
  26.  
  27.     for displacement_slot, bucket in buckets_items:
  28.         bucket_size = len(bucket)
  29.         displacement = 1
  30.         while True:
  31.             bucket_slots = {}
  32.             # Hash keys at current displacement and check for collisions.
  33.             for key in bucket:
  34.                 slot = hasher(key, displacement, shift)
  35.                 if slot in lookup_slots or slot in bucket_slots:
  36.                     break
  37.                 bucket_slots[slot] = key
  38.  
  39.             # If no collisions, update lookup and record displacement.
  40.             if len(bucket_slots) == bucket_size:
  41.                 lookup_slots.update(bucket_slots)
  42.                 displacement_table[displacement_slot] = displacement
  43.                 break
  44.  
  45.             displacement += 1
  46.             if displacement >= displacement_limit:
  47.                 raise RuntimeError("Unable to build perfect hash")
  48.  
  49.     # Map slots dictionary to table array.
  50.     lookup_table = [None] * lookup_size
  51.     for slot, key in lookup_slots.items():
  52.         lookup_table[slot] = key
  53.  
  54.     return lookup_table, displacement_table, shift
  55.  
  56. # Main.
  57.  
  58. from random import sample
  59.  
  60. keys = list(sample(range(10000), k=8))
  61. lookup_table, displacement_table, shift = build_perfect_hash(keys)
  62. lookup_size = len(lookup_table)
  63.  
  64. print(keys)
  65. # print(lookup_size)
  66. # print(displacement_table)
  67. # print(shift)
  68.  
  69. def perfect_hash(key):
  70.     displacement_slot = hasher(key, 0, shift)
  71.     slot = hasher(key, displacement_table[displacement_slot], shift)
  72.     return slot
  73.  
  74. def perfect_lookup(key):
  75.     return lookup_table[perfect_hash(key)]
  76.  
  77. for i, displacement in enumerate(displacement_table):
  78.     if displacement != 0:
  79.         print(f"Slot: {i} -> Displacement {displacement}")
  80. for key in keys:
  81.     slot = perfect_hash(key)
  82.     print(f"Key: {key} -> To unique slot {slot} (Stored {lookup_table[slot]})")
Success #stdin #stdout 0.1s 14164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[8456, 2497, 3964, 8240, 8609, 3052, 4528, 4688]
Slot: 0 -> Displacement 1
Slot: 1 -> Displacement 1
Slot: 2 -> Displacement 5
Slot: 3 -> Displacement 3
Slot: 4 -> Displacement 1
Slot: 5 -> Displacement 2
Slot: 7 -> Displacement 2
Key: 8456 -> To unique slot 5 (Stored 8456)
Key: 2497 -> To unique slot 4 (Stored 2497)
Key: 3964 -> To unique slot 0 (Stored 3964)
Key: 8240 -> To unique slot 1 (Stored 8240)
Key: 8609 -> To unique slot 7 (Stored 8609)
Key: 3052 -> To unique slot 6 (Stored 3052)
Key: 4528 -> To unique slot 2 (Stored 4528)
Key: 4688 -> To unique slot 3 (Stored 4688)
https://ideone.com/PJtHik
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!