networking-data-structures-and-algorithms.md (1274B)
1 +++ 2 title = 'Networking data structures and algorithms' 3 +++ 4 5 ## Networking data structures and algorithms 6 Deciding if an element exists in a large set 7 - hashing: mapping data to fixed size values with a function 8 - hash function properties: deterministic, efficiently computable, minimize collisions 9 - modulo hashing: `h(x) = x % table_size`, with `table_size` a prime number 10 - handle collisions with separate chaining (linked list on each hash value), or open addressing (look for next open spot following a given strategy if collisions detected) 11 - bloom filter: use multiple hash functions to lower collision rate 12 13 Count occurrences for large set of elements: 14 - counting bloom filter: on insert, increment counters corresponding to hash values. on read, look up counters and take the minimum count (does not ensure correctness, only upper bound). 15 - count-min sketch: three hash functions, each mapped to array of counters. on insert, increment. on read, obtain minimum of all counters. 16 17 Find match on prefix of a string: 18 - Trie: binary tree whose nodes have part of the prefix 19 - PATRICIA trie: like radix trie, with radix 2 20 - direct trie: combine segments in entries 21 - hardware implementation in TCAM: hardware device that lets you match on set of records in constant time