tessl/pypi-preshed

Cython hash table that trusts the keys are pre-hashed

—

Pending

Overview

Eval results

Files

Hash Maps

Name: tessl/pypi-preshed
Author: tessl

High-performance hash table implementation that maps pre-hashed uint64_t keys to uint64_t values. Uses open addressing with linear probing for efficient memory usage and cache performance.

Capabilities

PreshMap Class

Hash map optimized for pre-hashed keys with dictionary-like interface and high performance.

class PreshMap:
    """
    Hash map that assumes keys come pre-hashed. Maps uint64_t → uint64_t.
    Uses open addressing with linear probing.
    """
    def __init__(self, initial_size: int = 8):
        """
        Create a new hash map.
        
        Parameters:
        - initial_size: Initial capacity (must be power of 2, defaults to 8)
        """
        
    def __getitem__(self, key: int) -> int | None:
        """
        Get value for key.
        
        Parameters:
        - key: 64-bit unsigned integer key
        
        Returns:
        - Value associated with key, or None if key not found
        """
        
    def __setitem__(self, key: int, value: int) -> None:
        """
        Set value for key.
        
        Parameters:
        - key: 64-bit unsigned integer key
        - value: 64-bit unsigned integer value
        """
        
    def __delitem__(self, key: int) -> None:
        """
        Delete key from map.
        
        Parameters:
        - key: 64-bit unsigned integer key
        
        Raises:
        - KeyError: If key not found
        """
        
    def __len__(self) -> int:
        """
        Get number of key-value pairs in map.
        
        Returns:
        - Number of inserted keys
        """
        
    def __contains__(self, key: int) -> bool:
        """
        Check if key exists in map.
        
        Parameters:
        - key: 64-bit unsigned integer key
        
        Returns:
        - True if key exists, False otherwise
        """
        
    def __iter__(self) -> Iterator[int]:
        """
        Iterate over keys in map.
        
        Returns:
        - Iterator over keys
        """

Dictionary-like Methods

Standard dictionary operations for convenient usage.

def pop(self, key: int, default=None) -> int | None:
    """
    Remove key and return its value.
    
    Parameters:
    - key: 64-bit unsigned integer key
    - default: Value to return if key not found
    
    Returns:
    - Value associated with key, or default if key not found
    """
    
def items(self) -> Iterator[tuple[int, int]]:
    """
    Iterate over (key, value) pairs.
    
    Returns:
    - Iterator yielding (key, value) tuples
    """
    
def keys(self) -> Iterator[int]:
    """
    Iterate over keys.
    
    Returns:
    - Iterator over keys
    """
    
def values(self) -> Iterator[int]:
    """
    Iterate over values.
    
    Returns:
    - Iterator over values
    """

Properties

@property
def capacity(self) -> int:
    """
    Get current capacity of the hash map.
    
    Returns:
    - Current capacity (always power of 2)
    """

Usage Examples

Basic Operations

from preshed.maps import PreshMap

# Create a hash map
hash_map = PreshMap()

# Set values (keys should be pre-hashed)
hash_map[12345] = 67890
hash_map[54321] = 98765

# Get values
print(hash_map[12345])  # 67890
print(hash_map[99999])  # None (key not found)

# Check membership
print(12345 in hash_map)  # True
print(99999 in hash_map)  # False

# Get size
print(len(hash_map))  # 2

Iteration

from preshed.maps import PreshMap

hash_map = PreshMap()
hash_map[1] = 100
hash_map[2] = 200
hash_map[3] = 300

# Iterate over keys
for key in hash_map:
    print(f"Key: {key}")

# Iterate over key-value pairs
for key, value in hash_map.items():
    print(f"{key}: {value}")

# Iterate over values
for value in hash_map.values():
    print(f"Value: {value}")

Capacity Management

from preshed.maps import PreshMap

# Create with specific initial capacity
hash_map = PreshMap(initial_size=1024)
print(hash_map.capacity)  # 1024

# Map automatically resizes when needed
for i in range(2000):
    hash_map[i] = i * 2

print(hash_map.capacity)  # Will be larger than 1024
print(len(hash_map))  # 2000

Pop Operations

from preshed.maps import PreshMap

hash_map = PreshMap()
hash_map[42] = 100

# Pop with default
value = hash_map.pop(42, 0)
print(value)  # 100
print(42 in hash_map)  # False

# Pop non-existent key
value = hash_map.pop(99, "not found")
print(value)  # "not found"