0
# Short Hash Functions
1

2
Fast, non-cryptographic hash function (SipHash-2-4) optimized for hash tables, data structures, and applications requiring short, uniform hash values.
3

4
## Capabilities
5

6
### SipHash-2-4
7

8
Compute SipHash-2-4, a fast and secure short hash function suitable for hash tables and data structure applications.
9

10
```javascript { .api }
11
/**
12
 * Compute SipHash-2-4 short hash
13
 * @param out - Output buffer for hash (must be BYTES long)
14
 * @param input - Input buffer to hash
15
 * @param k - Key buffer (must be KEYBYTES long)
16
 * @throws Error if buffer sizes are incorrect or hashing fails
17
 */
18
function crypto_shorthash(out: Buffer, input: Buffer, k: Buffer): void;
19
```
20

21
**Usage Example:**
22

23
```javascript
24
const sodium = require('sodium-native');
25

26
// Generate key for SipHash
27
const key = Buffer.alloc(sodium.crypto_shorthash_KEYBYTES);
28
sodium.randombytes_buf(key);
29

30
// Compute short hash
31
const input = Buffer.from('Hello, World!');
32
const hash = Buffer.alloc(sodium.crypto_shorthash_BYTES);
33

34
sodium.crypto_shorthash(hash, input, key);
35

36
console.log('Short hash:', hash.toString('hex'));
37
console.log('Hash length:', hash.length, 'bytes');
38
```
39

40
## Constants
41

42
```javascript { .api }
43
// Output hash size in bytes (8 bytes = 64 bits)
44
const crypto_shorthash_BYTES: number;
45

46
// Key size in bytes (16 bytes = 128 bits)
47
const crypto_shorthash_KEYBYTES: number;
48
```
49

50
## Use Cases
51

52
SipHash is designed for scenarios where you need:
53

54
- **Hash Tables**: Fast, collision-resistant hashing for hash table keys
55
- **Data Structures**: Checksums for data structure integrity
56
- **Bloom Filters**: Multiple hash functions with different keys
57
- **Load Balancing**: Consistent hashing for distributed systems
58
- **Deduplication**: Fast content fingerprinting
59
- **DoS Protection**: Hash table collision resistance
60

61
## Security Considerations
62

63
- **Not Cryptographically Secure**: SipHash is designed for speed, not cryptographic security
64
- **Key Secrecy**: Keep hash keys secret to prevent hash collision attacks
65
- **Collision Resistance**: Provides good collision resistance when key is unknown to attacker
66
- **Performance**: Much faster than cryptographic hashes like SHA-256
67

68
## Common Patterns
69

70
### Hash Table Implementation
71

72
```javascript
73
const sodium = require('sodium-native');
74

75
class SecureHashTable {
76
  constructor(initialSize = 1000) {
77
    this.buckets = new Array(initialSize).fill(null).map(() => []);
78
    this.size = initialSize;
79
    this.count = 0;
80
    
81
    // Generate secret key for hash function
82
    this.hashKey = Buffer.alloc(sodium.crypto_shorthash_KEYBYTES);
83
    sodium.randombytes_buf(this.hashKey);
84
  }
85
  
86
  hash(key) {
87
    const keyBuffer = Buffer.from(key.toString());
88
    const hashOutput = Buffer.alloc(sodium.crypto_shorthash_BYTES);
89
    
90
    sodium.crypto_shorthash(hashOutput, keyBuffer, this.hashKey);
91
    
92
    // Convert to array index
93
    return hashOutput.readBigUInt64LE(0) % BigInt(this.size);
94
  }
95
  
96
  set(key, value) {
97
    const index = Number(this.hash(key));
98
    const bucket = this.buckets[index];
99
    
100
    // Check if key already exists
101
    for (let i = 0; i < bucket.length; i++) {
102
      if (bucket[i][0] === key) {
103
        bucket[i][1] = value;
104
        return;
105
      }
106
    }
107
    
108
    // Add new key-value pair
109
    bucket.push([key, value]);
110
    this.count++;
111
    
112
    // Resize if load factor too high
113
    if (this.count > this.size * 0.75) {
114
      this.resize();
115
    }
116
  }
117
  
118
  get(key) {
119
    const index = Number(this.hash(key));
120
    const bucket = this.buckets[index];
121
    
122
    for (const [k, v] of bucket) {
123
      if (k === key) {
124
        return v;
125
      }
126
    }
127
    
128
    return undefined;
129
  }
130
  
131
  delete(key) {
132
    const index = Number(this.hash(key));
133
    const bucket = this.buckets[index];
134
    
135
    for (let i = 0; i < bucket.length; i++) {
136
      if (bucket[i][0] === key) {
137
        bucket.splice(i, 1);
138
        this.count--;
139
        return true;
140
      }
141
    }
142
    
143
    return false;
144
  }
145
  
146
  resize() {
147
    const oldBuckets = this.buckets;
148
    this.size *= 2;
149
    this.buckets = new Array(this.size).fill(null).map(() => []);
150
    this.count = 0;
151
    
152
    // Rehash all existing entries
153
    for (const bucket of oldBuckets) {
154
      for (const [key, value] of bucket) {
155
        this.set(key, value);
156
      }
157
    }
158
  }
159
}
160

161
// Usage
162
const hashTable = new SecureHashTable();
163

164
hashTable.set('user:123', { name: 'Alice', email: 'alice@example.com' });
165
hashTable.set('user:456', { name: 'Bob', email: 'bob@example.com' });
166

167
console.log(hashTable.get('user:123'));
168
```
169

170
### Bloom Filter Implementation
171

172
```javascript
173
const sodium = require('sodium-native');
174

175
class BloomFilter {
176
  constructor(expectedElements, falsePositiveRate = 0.01) {
177
    // Calculate optimal bit array size and hash function count
178
    this.bitCount = Math.ceil(-(expectedElements * Math.log(falsePositiveRate)) / (Math.log(2) ** 2));
179
    this.hashCount = Math.ceil((this.bitCount / expectedElements) * Math.log(2));
180
    
181
    // Initialize bit array
182
    this.bits = new Uint8Array(Math.ceil(this.bitCount / 8));
183
    
184
    // Generate multiple hash keys
185
    this.hashKeys = [];
186
    for (let i = 0; i < this.hashCount; i++) {
187
      const key = Buffer.alloc(sodium.crypto_shorthash_KEYBYTES);
188
      sodium.randombytes_buf(key);
189
      this.hashKeys.push(key);
190
    }
191
  }
192
  
193
  hash(input, keyIndex) {
194
    const inputBuffer = Buffer.from(input.toString());
195
    const hashOutput = Buffer.alloc(sodium.crypto_shorthash_BYTES);
196
    
197
    sodium.crypto_shorthash(hashOutput, inputBuffer, this.hashKeys[keyIndex]);
198
    
199
    return Number(hashOutput.readBigUInt64LE(0) % BigInt(this.bitCount));
200
  }
201
  
202
  add(element) {
203
    for (let i = 0; i < this.hashCount; i++) {
204
      const bitIndex = this.hash(element, i);
205
      const byteIndex = Math.floor(bitIndex / 8);
206
      const bitOffset = bitIndex % 8;
207
      
208
      this.bits[byteIndex] |= 1 << bitOffset;
209
    }
210
  }
211
  
212
  contains(element) {
213
    for (let i = 0; i < this.hashCount; i++) {
214
      const bitIndex = this.hash(element, i);
215
      const byteIndex = Math.floor(bitIndex / 8);
216
      const bitOffset = bitIndex % 8;
217
      
218
      if ((this.bits[byteIndex] & (1 << bitOffset)) === 0) {
219
        return false; // Definitely not in set
220
      }
221
    }
222
    
223
    return true; // Probably in set
224
  }
225
  
226
  getInfo() {
227
    return {
228
      bitCount: this.bitCount,
229
      hashCount: this.hashCount,
230
      expectedElements: Math.ceil(this.bitCount / (-Math.log(0.01) / Math.log(2))),
231
      memoryUsage: this.bits.length
232
    };
233
  }
234
}
235

236
// Usage
237
const bloom = new BloomFilter(10000, 0.01); // 10k elements, 1% false positive rate
238

239
// Add elements
240
bloom.add('user:12345');
241
bloom.add('user:67890');
242
bloom.add('user:11111');
243

244
// Test membership
245
console.log('Contains user:12345:', bloom.contains('user:12345')); // true
246
console.log('Contains user:99999:', bloom.contains('user:99999')); // probably false
247

248
console.log('Bloom filter info:', bloom.getInfo());
249
```
250

251
### Consistent Hashing for Load Balancing
252

253
```javascript
254
const sodium = require('sodium-native');
255

256
class ConsistentHashRing {
257
  constructor(virtualNodes = 150) {
258
    this.virtualNodes = virtualNodes;
259
    this.ring = new Map(); // hash -> server
260
    this.servers = new Set();
261
    
262
    // Single key for all hash operations
263
    this.hashKey = Buffer.alloc(sodium.crypto_shorthash_KEYBYTES);
264
    sodium.randombytes_buf(this.hashKey);
265
  }
266
  
267
  hash(input) {
268
    const inputBuffer = Buffer.from(input.toString());
269
    const hashOutput = Buffer.alloc(sodium.crypto_shorthash_BYTES);
270
    
271
    sodium.crypto_shorthash(hashOutput, inputBuffer, this.hashKey);
272
    
273
    return hashOutput.readBigUInt64LE(0);
274
  }
275
  
276
  addServer(server) {
277
    this.servers.add(server);
278
    
279
    // Add virtual nodes for this server
280
    for (let i = 0; i < this.virtualNodes; i++) {
281
      const virtualKey = `${server}:${i}`;
282
      const hash = this.hash(virtualKey);
283
      this.ring.set(hash, server);
284
    }
285
    
286
    // Sort ring by hash values
287
    this.sortedHashes = Array.from(this.ring.keys()).sort((a, b) => {
288
      if (a < b) return -1;
289
      if (a > b) return 1;
290
      return 0;
291
    });
292
  }
293
  
294
  removeServer(server) {
295
    this.servers.delete(server);
296
    
297
    // Remove virtual nodes for this server
298
    for (let i = 0; i < this.virtualNodes; i++) {
299
      const virtualKey = `${server}:${i}`;
300
      const hash = this.hash(virtualKey);
301
      this.ring.delete(hash);
302
    }
303
    
304
    // Update sorted hash list
305
    this.sortedHashes = Array.from(this.ring.keys()).sort((a, b) => {
306
      if (a < b) return -1;
307
      if (a > b) return 1;
308
      return 0;
309
    });
310
  }
311
  
312
  getServer(key) {
313
    if (this.servers.size === 0) {
314
      throw new Error('No servers available');
315
    }
316
    
317
    const keyHash = this.hash(key);
318
    
319
    // Find first server hash >= key hash
320
    for (const serverHash of this.sortedHashes) {
321
      if (serverHash >= keyHash) {
322
        return this.ring.get(serverHash);
323
      }
324
    }
325
    
326
    // Wrap around to first server
327
    return this.ring.get(this.sortedHashes[0]);
328
  }
329
  
330
  getServerDistribution(keys) {
331
    const distribution = new Map();
332
    
333
    for (const server of this.servers) {
334
      distribution.set(server, 0);
335
    }
336
    
337
    for (const key of keys) {
338
      const server = this.getServer(key);
339
      distribution.set(server, distribution.get(server) + 1);
340
    }
341
    
342
    return distribution;
343
  }
344
}
345

346
// Usage
347
const hashRing = new ConsistentHashRing();
348

349
// Add servers
350
hashRing.addServer('server1:8080');
351
hashRing.addServer('server2:8080');
352
hashRing.addServer('server3:8080');
353

354
// Route requests
355
const testKeys = Array.from({length: 1000}, (_, i) => `request:${i}`);
356
const distribution = hashRing.getServerDistribution(testKeys);
357

358
console.log('Load distribution:');
359
for (const [server, count] of distribution) {
360
  console.log(`${server}: ${count} requests (${(count/testKeys.length*100).toFixed(1)}%)`);
361
}
362

363
// Add new server and see redistribution
364
hashRing.addServer('server4:8080');
365
const newDistribution = hashRing.getServerDistribution(testKeys);
366

367
console.log('\nAfter adding server4:');
368
for (const [server, count] of newDistribution) {
369
  console.log(`${server}: ${count} requests (${(count/testKeys.length*100).toFixed(1)}%)`);
370
}
371
```
372

373
### Fast Content Deduplication
374

375
```javascript
376
const sodium = require('sodium-native');
377

378
class ContentDeduplicator {
379
  constructor() {
380
    this.hashKey = Buffer.alloc(sodium.crypto_shorthash_KEYBYTES);
381
    sodium.randombytes_buf(this.hashKey);
382
    
383
    this.seenHashes = new Set();
384
    this.contentMap = new Map(); // hash -> content reference
385
  }
386
  
387
  fingerprint(content) {
388
    const contentBuffer = Buffer.isBuffer(content) ? content : Buffer.from(content);
389
    const hash = Buffer.alloc(sodium.crypto_shorthash_BYTES);
390
    
391
    sodium.crypto_shorthash(hash, contentBuffer, this.hashKey);
392
    
393
    return hash.toString('hex');
394
  }
395
  
396
  isDuplicate(content) {
397
    const fingerprint = this.fingerprint(content);
398
    return this.seenHashes.has(fingerprint);
399
  }
400
  
401
  addContent(content, metadata = null) {
402
    const fingerprint = this.fingerprint(content);
403
    
404
    if (this.seenHashes.has(fingerprint)) {
405
      return { isDuplicate: true, fingerprint };
406
    }
407
    
408
    this.seenHashes.add(fingerprint);
409
    this.contentMap.set(fingerprint, {
410
      content: content,
411
      metadata: metadata,
412
      firstSeen: new Date(),
413
      refCount: 1
414
    });
415
    
416
    return { isDuplicate: false, fingerprint };
417
  }
418
  
419
  getContent(fingerprint) {
420
    return this.contentMap.get(fingerprint);
421
  }
422
  
423
  incrementReference(fingerprint) {
424
    const entry = this.contentMap.get(fingerprint);
425
    if (entry) {
426
      entry.refCount++;
427
    }
428
  }
429
  
430
  getStats() {
431
    return {
432
      uniqueContent: this.seenHashes.size,
433
      totalReferences: Array.from(this.contentMap.values())
434
        .reduce((sum, entry) => sum + entry.refCount, 0),
435
      memoryUsage: this.contentMap.size
436
    };
437
  }
438
}
439

440
// Usage
441
const deduplicator = new ContentDeduplicator();
442

443
// Add some content
444
const content1 = 'This is some content';
445
const content2 = 'This is different content';
446
const content3 = 'This is some content'; // Duplicate of content1
447

448
const result1 = deduplicator.addContent(content1, { source: 'file1.txt' });
449
const result2 = deduplicator.addContent(content2, { source: 'file2.txt' });
450
const result3 = deduplicator.addContent(content3, { source: 'file3.txt' });
451

452
console.log('Content1 result:', result1);
453
console.log('Content2 result:', result2);
454
console.log('Content3 result (duplicate):', result3);
455

456
if (result3.isDuplicate) {
457
  deduplicator.incrementReference(result3.fingerprint);
458
}
459

460
console.log('Deduplication stats:', deduplicator.getStats());
461
```