## 4 Theoretical Analysis
### Signature Collision  
A key with a variable length needs to be converted to a fixed-length signature to be stored in a fixed-width hash entry. Since a signature is generated by hashing, _signature collision_ can also occur, in which two or more different keys are mapped to the same signature. The number of bits for a signature is set as \(2 log_{2}n\) in this work, where \(n\) is the number of elements stored in a hash table. In a hash table, a signature collision can cause two types of search failures: _false result_ and _false positive_. A _false result_ occurs for elements included in a given set if two or more different keys which have the same signature but different return values are mapped to the same entry in a hash table in insertion procedure. In this case, if the key which could not be stored because of entry collision is given as an input, a wrong value can be returned in search procedure, as the signature of the key matches the stored signature. _False positive_ occurs for an input not included in a given set if the input has the same signature as an element included in the set and the hash index of the input is mapped to the entry, where the signature of the element is stored. In search procedure, the input is recognized as the element that has been stored in insertion procedure. The probabilities of false result and false positive caused by signature collision can be derived as follows. Let \(r\) represent the number of available signatures. If the number of bits of a signature is set as \(2 log_{2}n\), then \(r=2^{2 log_{2}n}=n^{2}\). Probability that a signature value is unused after one element is mapped to a signature by hashing is \(1-\frac{1}{r}\). Thus, probability that a signature is unused after \(n\) elements are mapped by hashing is \((1-\frac{1}{r})^{n}\). Let \(E(N_{unused})\) be the expected number of unused signatures. \[E(N_{unused})=\sum_{i=1}^{r}{(1-\frac{1}{r})}^{n}=r(1-\frac{1}{r})^{n} \tag{3}\]  
Let \(E(N_{used})\) be the expected number of used signatures. \[E(N_{used})=r-E(N_{unused})=r-r(1-\frac{1}{r})^{n} \tag{4}\]  
Each used signature would contain one key (element) that has not been collided in the process of signature mapping. Therefore, the number of collisions would be \(n\) minus the number of used signatures. Let \(E(N_{collision})\) represent the expected number of collisions in signature mapping. \[E(N_{collision})=n-E(N_{used})=n-r+r(1-\frac{1}{r})^{n} \tag{5}\]  
If we set \(r=n^{2}\), then  
\[E(N_{collision})=n-n^{2}+n^{2}(1-\frac{1}{n^{2}})^{n}. \tag{6}\]  
We can numerically show that \(E(N_{collision})\) in Label (6) converges to 0.5 as \(n\) becomes large. Let \(P_{co}\) represent the probability that an element are collided in the process of signature mapping. \[P_{co}=\frac{E(N_{collision})}{n}=1-n+n(1-\frac{1}{n^{2}})^{n} \tag{7}\]  
If an element is mapped to a bucket, where another element with the same signature was already stored, the element that has been collided in signature mapping cannot be stored because the element is considered to be already stored. Therefore, when both signature collision and bucket collision occur in an insertion procedure, a false result occurs in the search procedure. Let \(B\) represent the number of buckets in a hash table and \(P_{fr}\) represent the probability of false results. In other words, \(P_{fr}\) represents the probability that an element is mapped to the bucket where another element with the same signature as itself is stored. \[P_{fr}=P_{co}\cdot\frac{1}{B}=\left(1-n+n(1-\frac{1}{n^{2}})^{n}\right)\cdot\frac{ 1}{B} \tag{8}\]  
Let \(P_{us}\) represent the probability that a non-programmed input (which is not included in the insertion set) is mapped to a used signature. As there are \(r\) possible signatures,  
\[P_{us}=\frac{E(N_{used})}{r}=1-(1-\frac{1}{r})^{n}=1-(1-\frac{1}{n^{2}})^{n}. \tag{9}\]  
A false positive occurs in search procedure, when a non-programmed input is mapped to a specific used signature and its hash index is mapped to the bucket, where the specific used signature is stored.