# Scalable Name Lookup for NDN Using Hierarchical Hashing and Patricia Trie
## 4 Proposed Name Lookup Scheme
### Hash Table  
All hash tables are organized in the same format regardless of their component levels. Figure 5 shows the structure of the hash table and two types of hashing schemes. As shown in Figure 5a, the hash table consisted of three fields: _itab_size_, _tot_no_keys_, and _htab_[_htab_size_]. The former two fields, _htab_size_ and _tot_no_keys_, were the hash table size and the total number of stored keys, respectively. Those were supplementary fields to dynamically adjust the hash table size. For the adjustment purpose, we exploited a load factor that was calculated by _tot_no_keys/_htab_size_. The value of _htab_size_ was always a power of two. The field _htab_ was an array of pointers to the Patricia tries or the linked lists, and it was actually the hash table itself.  
Figure 4: Proposed structure of the forwarding information base (FIB).  
A collision problem may occur when the same hashing value is produced for different keys. Our hashing scheme used a Patricia trie for the overflow area instead of a linked list to resolve the collision problem. Figure 5b,c compare separate chaining with our scheme by an example where five keys were stored: \(com\), \(edu\), \(org\), \(net\) and \(kr\). Suppose h(\"\(com\)\") = h(\"\(edu\)\") = h(\"\(org\)\") = 0, and h(\"\(net\)\") = h(\"\(kr\)\") = 3. Thus, {\(com\), \(edu\), \(org\)} and {\(net\), \(kr\)} are stored in the 0-th and the 3 rd buckets, respectively. In separate chaining, all the keys that are hashed in a bucket are maintained in a linked list, as shown in Figure 5b. On the other hand, in our scheme, the keys in a bucket were the leaves of a Patricia trie, as shown in Figure 5c. In this example, _lttab_size_ is 4 and _tot_no_keys_ was 5, so the actual load factor was 1.25 (=5/4).  
For a given search key \(K\), the hashing time is usually \(O(k)\) where \(k\) is the length of \(K\). The selective bit extraction of a key reduces hashing time, but it may cause an undesirable result. Upon a successful search, every key in a linked list should be compared with a search key until the matched key is found in separate chaining. If there are \(m\) keys in a bucket, the total comparison time is \(O(mk)\). On the other hand, in a Patricia trie, key comparison is only taken once in a leaf node. Only bit inspection is needed while traversing intermediate nodes in a Patricia trie. Overall comparison time is \(O(h+k)\), where \(h\) is the height of a Patricia trie, and \(h\) is \(\log_{2}m\) in the best case and \(m\) in the worst case, so the comparison time is \(O(m+k)\) in the worst. In practice, \(m\) is not so large, and \(k\) can be large.  
Each hash table size is varied and can even be dynamically changed by means of a key insertion induced by an update of the FIB. This means one should not fix hash table size by using a static array. For scalability, we used dynamic arrays for hash tables in which its size can be doubled. The amortized cost of insertion and deletion for a dynamic array is \(O(1)\)[26]. Given a limit of load factor \(\beta\), we controlled the size of hash table to meet the restriction, \(\alpha\leq\beta\) where \(\alpha\) is the actual load factor. \(\alpha\) is defined as \(d/N\), where \(d\) is the number of stored keys and \(N\) is the number of buckets in the hash table. Whenever \(\alpha>\beta\) by insertion of a new key, the hash table size is doubled. \(\alpha\) represents the average number of keys in a bucket or the average number of leaves in Patricia tries. By controlling the hash table size, \(\alpha\) satisfies the following restriction.  
\[\alpha\leq\beta\text{ if }N=1 \tag{1}\]  
\[\beta/2\leq\alpha\leq\beta\text{ if }N\geq 2 \tag{2}\]