0
# Hash Maps
1

2
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.
3

4
## Capabilities
5

6
### PreshMap Class
7

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

10
```python { .api }
11
class PreshMap:
12
    """
13
    Hash map that assumes keys come pre-hashed. Maps uint64_t → uint64_t.
14
    Uses open addressing with linear probing.
15
    """
16
    def __init__(self, initial_size: int = 8):
17
        """
18
        Create a new hash map.
19
        
20
        Parameters:
21
        - initial_size: Initial capacity (must be power of 2, defaults to 8)
22
        """
23
        
24
    def __getitem__(self, key: int) -> int | None:
25
        """
26
        Get value for key.
27
        
28
        Parameters:
29
        - key: 64-bit unsigned integer key
30
        
31
        Returns:
32
        - Value associated with key, or None if key not found
33
        """
34
        
35
    def __setitem__(self, key: int, value: int) -> None:
36
        """
37
        Set value for key.
38
        
39
        Parameters:
40
        - key: 64-bit unsigned integer key
41
        - value: 64-bit unsigned integer value
42
        """
43
        
44
    def __delitem__(self, key: int) -> None:
45
        """
46
        Delete key from map.
47
        
48
        Parameters:
49
        - key: 64-bit unsigned integer key
50
        
51
        Raises:
52
        - KeyError: If key not found
53
        """
54
        
55
    def __len__(self) -> int:
56
        """
57
        Get number of key-value pairs in map.
58
        
59
        Returns:
60
        - Number of inserted keys
61
        """
62
        
63
    def __contains__(self, key: int) -> bool:
64
        """
65
        Check if key exists in map.
66
        
67
        Parameters:
68
        - key: 64-bit unsigned integer key
69
        
70
        Returns:
71
        - True if key exists, False otherwise
72
        """
73
        
74
    def __iter__(self) -> Iterator[int]:
75
        """
76
        Iterate over keys in map.
77
        
78
        Returns:
79
        - Iterator over keys
80
        """
81
```
82

83
### Dictionary-like Methods
84

85
Standard dictionary operations for convenient usage.
86

87
```python { .api }
88
def pop(self, key: int, default=None) -> int | None:
89
    """
90
    Remove key and return its value.
91
    
92
    Parameters:
93
    - key: 64-bit unsigned integer key
94
    - default: Value to return if key not found
95
    
96
    Returns:
97
    - Value associated with key, or default if key not found
98
    """
99
    
100
def items(self) -> Iterator[tuple[int, int]]:
101
    """
102
    Iterate over (key, value) pairs.
103
    
104
    Returns:
105
    - Iterator yielding (key, value) tuples
106
    """
107
    
108
def keys(self) -> Iterator[int]:
109
    """
110
    Iterate over keys.
111
    
112
    Returns:
113
    - Iterator over keys
114
    """
115
    
116
def values(self) -> Iterator[int]:
117
    """
118
    Iterate over values.
119
    
120
    Returns:
121
    - Iterator over values
122
    """
123
```
124

125
### Properties
126

127
```python { .api }
128
@property
129
def capacity(self) -> int:
130
    """
131
    Get current capacity of the hash map.
132
    
133
    Returns:
134
    - Current capacity (always power of 2)
135
    """
136
```
137

138
## Usage Examples
139

140
### Basic Operations
141

142
```python
143
from preshed.maps import PreshMap
144

145
# Create a hash map
146
hash_map = PreshMap()
147

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

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

156
# Check membership
157
print(12345 in hash_map)  # True
158
print(99999 in hash_map)  # False
159

160
# Get size
161
print(len(hash_map))  # 2
162
```
163

164
### Iteration
165

166
```python
167
from preshed.maps import PreshMap
168

169
hash_map = PreshMap()
170
hash_map[1] = 100
171
hash_map[2] = 200
172
hash_map[3] = 300
173

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

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

182
# Iterate over values
183
for value in hash_map.values():
184
    print(f"Value: {value}")
185
```
186

187
### Capacity Management
188

189
```python
190
from preshed.maps import PreshMap
191

192
# Create with specific initial capacity
193
hash_map = PreshMap(initial_size=1024)
194
print(hash_map.capacity)  # 1024
195

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

200
print(hash_map.capacity)  # Will be larger than 1024
201
print(len(hash_map))  # 2000
202
```
203

204
### Pop Operations
205

206
```python
207
from preshed.maps import PreshMap
208

209
hash_map = PreshMap()
210
hash_map[42] = 100
211

212
# Pop with default
213
value = hash_map.pop(42, 0)
214
print(value)  # 100
215
print(42 in hash_map)  # False
216

217
# Pop non-existent key
218
value = hash_map.pop(99, "not found")
219
print(value)  # "not found"
220
```
221

222
## Performance Characteristics
223

224
- **Average case**: O(1) for get, set, delete operations
225
- **Worst case**: O(n) when many keys hash to same location
226
- **Memory**: Efficient open addressing reduces memory overhead
227
- **Cache performance**: Linear probing provides good locality
228
- **Resize**: Automatic doubling when capacity exceeded