Insertion Times Linear Quadratic Double Chained Perfect Perfect* 0.25x ERR ERR ERR 0.214 ERR ERR 0.5x ERR ERR ERR 0.187 ERR ERR 1x 0.793 0.138 0.201 0.173 2.222 0.075 1.01x 0.436 0.065 0.080 0.161 2.205 0.057 1.5x 0.030 0.026 0.036 0.202 1.586 0.055 2x 0.024 0.026 0.034 0.150 1.191 0.057 4x 0.028 0.028 0.028 0.177 0.655 0.045 10x 0.026 0.028 0.027 10.000 0.271 0.042 Search Times Linear Quadratic Double Chained Perfect 0.25x ERR ERR ERR 0.097 ERR 0.5x ERR ERR ERR 0.061 ERR 1x 0.855 0.132 0.182 0.055 0.021 1.01x 0.417 0.059 0.075 0.066 0.025 1.5x 0.027 0.028 0.040 0.089 0.042 2x 0.024 0.022 0.030 0.052 0.040 4x 0.013 0.027 0.026 0.069 0.026 10x 0.017 0.029 0.027 0.285 0.027 Efficiency Linear Quadratic Double Chained Perfect 0.25x ERR ERR ERR 75.5% ERR 0.5x ERR ERR ERR 56.8% ERR 1x 50.1% 50.6% 50.6% 36.9% 36.9% 1.01x 49.0% 50.5% 49.2% 36.7% 36.7% 1.5x 33.6% 33.7% 33.7% 27.3% 27.3% 2x 25.0% 25.0% 25.3% 21.4% 21.4% 4x 12.7% 12.7% 12.9% 11.7% 11.7% 10x 4.8% 4.9% 4.9% 4.7% 4.7% Probe Length Probe Length/Search Linear Quadratic Double Chained Perfect Linear Quadratic Double Chained Perfect 0.25x ERR ERR ERR 30761 ERR 0.25x ERR ERR ERR 2.01 ERR 0.5x ERR ERR ERR 15513 ERR 0.5x ERR ERR ERR 1.01 ERR 1x 1506521 163397 164708 7689 ERR 1x 98.22 10.65 10.74 0.50 ERR 1.01x 755426 74190 71402 7651 ERR 1.01x 49.25 4.84 4.66 0.50 ERR 1.5x 30969 26501 25585 5148 ERR 1.5x 2.02 1.73 1.67 0.34 ERR 2x 22893 21727 21766 3814 ERR 2x 1.49 1.42 1.42 0.25 ERR 4x 17893 17813 17734 1947 ERR 4x 1.17 1.16 1.16 0.13 ERR 10x 16146 16159 16137 732 ERR 10x 1.05 1.05 1.05 0.05 ERR Hash Functions on the Perfect Hash Table - Insertion Time Hash Functions on the Perfect Hash Table - Collisions Division Multiplication Reciprocal Random Division Multiplication Reciprocal Random 1x 2.222 2.279 2.307 2.424 1x 36.9% 36.9% 36.9% 36.9% 1.01x 2.205 2.413 2.334 2.279 1.01x 36.7% 36.7% 36.7% 36.7% 1.5x 1.586 1.632 1.636 1.564 1.5x 27.3% 27.3% 27.3% 27.3% 2x 1.191 1.214 1.216 1.161 2x 21.4% 21.4% 21.4% 21.4% 4x 0.655 0.620 0.714 0.606 4x 11.7% 11.7% 11.7% 11.7% 10x 0.271 0.277 0.282 0.254 10x 4.7% 4.7% 4.7% 4.7% Hash Functions on the Perfect Hash Table - Moves Hash Functions on the Perfect Hash Table - Guesses Division Multiplication Reciprocal Random Division Multiplication Reciprocal Random 1x 7620 7620 7620 7620 1x 19757 19613 20243 18880 1.01x 7651 7451 7651 7651 1.01x 19678 19812 21628 18497 1.5x 5148 5148 5148 5148 1.5x 12339 12075 12164 11412 2x 3814 3814 3814 3814 2x 8341 9651 8621 8296 4x 1947 1947 1947 1947 4x 3999 4431 4227 4036 10x 732 732 732 732 10x 1525 1467 1589 1433 Elements: 15338 Average Variance Data Linear 1x Itime 0.793 0.000 0.81 0.811 0.81 0.81 0.811 0.77 0.783 0.767 0.769 Stime 0.855 0.001 0.88 0.879 0.852 0.893 0.851 0.837 0.824 0.837 0.838 Collisions: 7681 Steps: 1506521 Linear 1.01x Itime 0.436 0.003 0.384 0.398 0.385 0.52 0.493 Stime 0.417 0.000 0.425 0.412 0.425 0.412 0.411 Collisions: 7522 Steps: 755426 Linear 1.5x Itime 0.030 0.000 0.028 0.027 0.028 0.028 0.027 0.042 0.028 0.029 0.028 0.041 0.026 0.028 Stime 0.027 0.000 0.027 0.028 0.027 0.013 0.028 0.04 0.027 0.026 0.039 0.014 0.027 0.027 Collisions: 5158 Steps: 30969 Linear 2x Itime 0.024 0.000 0.013 0.016 0.029 0.027 0.027 0.029 0.027 Stime 0.024 0.000 0.029 0.025 0.026 0.015 0.042 0.014 0.014 Collisions: 3832 Steps: 22893 Linear 4x Itime 0.028 0.000 0.027 0.028 0.029 0.029 0.029 Stime 0.013 0.000 0.014 0.013 0.012 0.013 0.012 Collisions: 1943 Steps: 17893 Linear 10x Itime 0.026 0.000 0.025 0.027 0.028 0.014 0.029 0.03 0.027 Stime 0.017 0.000 0.015 0.014 0.013 0.027 0.013 0.025 0.014 Collisions: 739 Steps: 16146 Average Variance Data Quadratic 1x Itime 0.138 0.000 0.137 0.136 0.137 0.143 0.137 Failed Stime 0.132 0.000 0.124 0.124 0.125 0.124 0.165 Collisions: 7757 Steps: 163397 0.069 0.069 Quadratic 1.01x Itime 0.065 0.000 0.068 0.055 0.055 0.069 0.068 0.069 0.069 Stime 0.059 0.000 0.055 0.069 0.068 0.055 0.055 0.055 0.055 Collisions: 7753 Steps: 74190 Quadratic 1.5x Itime 0.026 0.000 0.029 0.028 0.018 0.028 0.028 Stime 0.028 0.000 0.031 0.015 0.04 0.027 0.027 Collisions: 5173 Steps: 26501 Quadratic 2x Itime 0.026 0.000 0.028 0.028 0.03 0.027 0.028 0.015 Stime 0.022 0.000 0.027 0.013 0.025 0.028 0.013 0.027 Collisions: 3828 Steps: 21727 Quadratic 4x Itime 0.028 0.000 0.027 0.029 0.031 0.024 0.031 Stime 0.027 0.000 0.028 0.026 0.024 0.031 0.024 Collisions: 1952 Steps: 17813 Quadratic 10x Itime 0.028 0.000 0.029 0.029 0.015 0.014 0.035 0.046 Stime 0.029 0.000 0.038 0.026 0.026 0.028 0.031 0.026 Collisions: 748 Steps: 16159 Average Variance Data Double 1x Itime 0.201 0.001 0.248 0.179 0.178 0.251 0.179 0.168 Stime 0.182 0.000 0.219 0.165 0.165 0.203 0.164 0.178 Collisions: 7767 Steps: 164708 Double 1.01x Itime 0.080 0.000 0.082 0.082 0.082 0.069 0.083 Stime 0.075 0.000 0.082 0.083 0.068 0.082 0.062 Collisions: 7539 Steps: 71402 Double 1.5x Itime 0.036 0.000 0.028 0.027 0.041 0.025 0.053 0.042 Stime 0.040 0.000 0.041 0.041 0.028 0.055 0.051 0.026 Collisions: 5164 Steps: 25585 Double 2x Itime 0.034 0.000 0.052 0.04 0.028 0.027 0.028 0.027 Stime 0.030 0.000 0.028 0.041 0.027 0.028 0.027 0.028 Collisions: 3877 Steps: 21766 Double 4x Itime 0.028 0.000 0.028 0.028 0.027 0.028 0.027 0.029 Stime 0.026 0.000 0.027 0.027 0.014 0.033 0.028 0.024 Collisions: 1971 Steps: 17734 Double 10x Itime 0.027 0.000 0.027 0.027 0.027 0.055 .028 .026 Stime 0.027 0.000 0.014 0.028 0.027 0.025 0.027 0.043 Collisions: 744 Steps: 16137 Average Variance Data Chained 0.25x Itime 0.214 0.000 0.217 0.22 0.222 0.205 0.205 Stime 0.097 0.001 0.083 0.069 0.152 0.069 0.112 Collisions: 11584 Steps: 30761 Chained 0.5x Itime 0.187 0.001 0.22 0.178 0.187 0.213 0.138 0.138 0.234 Stime 0.061 0.000 0.07 0.055 0.055 0.055 0.068 0.068 0.055 Collisions: 8718 Steps: 15513 Chained 1x Itime 0.173 0.003 0.15 0.151 0.138 0.15 0.275 Stime 0.055 0.000 0.055 0.055 0.054 0.055 0.055 Collisions: 5665 Steps: 7689 Chained 1.01x Itime 0.161 0.001 0.15 0.151 0.151 0.223 0.137 0.151 Stime 0.066 0.001 0.055 0.055 0.054 0.125 0.054 0.055 Collisions: 5626 Steps: 7651 Chained 1.5x Itime 0.202 0.001 0.208 0.208 0.208 0.236 0.151 Stime 0.089 0.001 0.066 0.139 0.081 0.104 0.055 Collisions: 4182 Steps: 5148 Chained 2x Itime 0.150 0.000 0.145 0.151 0.15 0.151 0.152 Stime 0.052 0.000 0.055 0.055 0.055 0.041 0.054 Collisions: 3275 Steps: 3814 Chained 4x Itime 0.177 0.001 0.151 0.165 0.165 0.165 0.25 0.165 Stime 0.069 0.002 0.055 0.042 0.041 0.054 0.165 0.055 Collisions: 1801 Steps: 1947 Chained 10x Itime 32.497 0.000 32.497 Stime 0.285 0.000 0.285 Collisions: 716 Steps: 732 Average Variance Data Perfect Div 1x Itime 2.222 0.001 2.252 2.225 2.239 2.169 2.238 2.211 Failed Stime 0.021 0.000 0.013 0.013 0.027 0.027 0.028 0.015 Atime: 2.147 0.003 2.211 2.129 2.199 2.073 2.183 2.088 Collisions: 5663 Moves: 7620 Guesses: 19757 Perfect Div 1.01x Itime 2.205 0.002 2.156 2.21 2.238 2.138 2.236 2.25 Stime 0.025 0.000 0.028 0.028 0.028 0.028 0.027 0.013 Atime: 2.147 0.002 2.1 2.102 2.144 2.141 2.199 2.198 Collisions: 5626 Moves: 7651 Guesses: 19678 Perfect Div 1.5x Itime 1.586 0.001 1.58 1.553 1.648 1.591 1.566 1.58 Stime 0.042 0.002 0.13 0.026 0.027 0.014 0.027 0.027 Atime: 1.532 0.003 1.539 1.526 1.635 1.509 1.458 1.523 Collisions: 4182 Moves: 5148 Guesses: 12339 Perfect Div 2x Itime 1.191 0.003 1.195 1.277 1.209 1.208 1.13 1.124 Stime 0.040 0.002 0.13 0.027 0.013 0.028 0.013 0.028 Atime: 1.134 0.001 1.155 1.18 1.134 1.136 1.112 1.084 Collisions: 3275 Moves: 3814 Guesses: 8341 Perfect Div 4x Itime 0.655 0.002 0.604 0.59 0.631 0.687 0.701 0.714 Stime 0.026 0.000 0.028 0.028 0.028 0.014 0.027 0.028 Atime: 0.610 0.002 0.563 0.562 0.588 0.643 0.657 0.645 Collisions: 1801 Moves: 1947 Guesses: 3999 Perfect Div 10x Itime 0.271 0.000 0.273 0.273 0.287 0.275 0.261 0.259 Stime 0.027 0.000 0.028 0.027 0.027 0.027 0.027 0.027 Atime: 0.230 0.001 0.247 0.254 0.223 0.253 0.167 0.235 Collisions: 716 Moves: 732 Guesses: 1525 Average Variance Data Perfect Mult 1x Itime 2.279 0.002 2.252 2.266 2.293 2.237 2.252 2.376 Failed Stime 0.039 0.000 0.042 0.028 0.042 0.041 0.041 0.041 Atime: 2.104 0.003 2.074 2.114 2.193 2.045 2.059 2.14 Collisions: 5667 Moves: 7620 Guesses: 19613 Perfect Mult 1.01x Itime 2.413 0.014 2.678 2.362 2.335 2.362 2.362 2.376 Stime 0.037 0.000 0.028 0.042 0.041 0.028 0.041 0.041 Atime: 2.142 0.001 2.072 2.14 2.171 2.17 2.116 2.183 Collisions: 5626 Moves: 7451 Guesses: 19812 Perfect Mult 1.5x Itime 1.632 0.001 1.635 1.662 1.579 1.619 1.673 1.621 Stime 0.043 0.000 0.04 0.055 0.041 0.042 0.041 0.041 Atime: 1.526 0.001 1.554 1.574 1.497 1.47 1.551 1.511 Collisions: 4182 Moves: 5148 Guesses: 12075 Perfect Mult 2x Itime 1.214 0.003 1.194 1.193 1.181 1.333 1.202 1.18 Stime 0.041 -0.000 0.041 0.041 0.041 0.041 0.041 0.041 Atime: 1.140 0.004 1.1 1.114 1.099 1.277 1.12 1.131 Collisions: 3275 Moves: 3814 Guesses: 9651 Perfect Mult 4x Itime 0.620 0.000 0.632 0.618 0.618 0.618 0.617 0.618 Stime 0.041 0.000 0.041 0.041 0.041 0.041 0.042 0.042 Atime: 0.574 0.000 0.576 0.576 0.591 0.577 0.563 0.562 Collisions: 1801 Moves: 1947 Guesses: 4431 Perfect Mult 10x Itime 0.277 0.001 0.246 0.247 0.289 0.261 0.357 0.26 Stime 0.049 0.000 0.056 0.055 0.049 0.041 0.053 0.042 Atime: 0.247 0.003 0.219 0.206 0.231 0.248 0.357 0.219 Collisions: 716 Moves: 732 Guesses: 1467 Average Variance Data Perfect Reci 1x Itime 2.307 0.004 2.294 2.442 2.294 2.266 2.292 2.251 Stime 0.044 0.000 0.041 0.042 0.041 0.041 0.042 0.055 Atime: 2.101 0.003 2.085 2.185 2.156 2.073 2.09 2.015 Collisions: 5665 Moves: 7620 Guesses: 20243 Perfect Reci 1.01x Itime 2.334 0.001 2.307 2.335 2.307 2.335 2.372 2.348 Stime 0.041 0.000 0.041 0.041 0.041 0.041 0.04 0.041 Atime: 2.096 0.004 2.102 2.105 2.049 2.157 1.981 2.179 Collisions: 5626 Moves: 7651 Guesses: 21628 Perfect Reci 1.5x Itime 1.636 1.639 1.601 1.607 1.799 1.594 1.621 1.594 Stime 0.041 -0.000 0.041 0.041 0.041 0.041 0.041 0.041 Atime: 1.516 0.004 1.453 1.496 1.651 1.485 1.485 1.524 Collisions: 4182 Moves: 5148 Guesses: 12164 Perfect Reci 2x Itime 1.216 0.002 1.181 1.291 1.264 1.195 1.181 1.182 Stime 0.041 -0.000 0.041 0.041 0.041 0.041 0.041 0.041 Atime: 1.116 0.003 1.084 1.168 1.2 1.127 1.04 1.075 Collisions: 3275 Moves: 3814 Guesses: 8621 Perfect Reci 4x Itime 0.714 0.010 0.629 0.7 0.627 0.631 0.87 0.824 Stime 0.048 0.000 0.041 0.042 0.042 0.041 0.08 0.041 Atime: 0.556 0.060 0.589 0.062 0.563 0.535 0.804 0.78 Collisions: 1801 Moves: 1947 Guesses: 4227 Perfect Reci 10x Itime 0.282 0.002 0.261 0.261 0.261 0.262 0.261 0.383 Stime 0.050 0.000 0.055 0.055 0.041 0.054 0.041 0.055 Atime: 0.229 0.001 0.219 0.207 0.219 0.221 0.22 0.287 Collisions: 716 Moves: 732 Guesses: 1589 Average Variance Data Perfect Rand 1x Itime 2.424 0.061 2.31 2.311 2.974 2.328 2.311 2.31 Stime 0.025 0.000 0.024 0.024 0.024 0.025 0.024 0.028 Atime: 2.157 0.043 2.073 2.073 2.623 2.07 2.053 2.052 Collisions: 5665 Moves: 7620 Guesses: 18880 Perfect Rand 1.01x Itime 2.279 0.001 2.279 2.301 2.242 2.304 2.242 2.307 Stime 0.025 0.000 0.028 0.027 0.024 0.024 0.024 0.024 Atime: 2.136 0.001 2.138 2.174 2.094 2.168 2.084 2.156 Collisions: 5626 Moves: 7651 Guesses: 18497 Perfect Rand 1.5x Itime 1.564 0.000 1.562 1.569 1.562 1.556 1.561 1.573 Stime 0.022 0.000 0.021 0.024 0.024 0.024 0.021 0.02 Atime: 1.501 0.000 1.49 1.511 1.483 1.486 1.501 1.532 Collisions: 4182 Moves: 5148 Guesses: 11412 Perfect Rand 2x Itime 1.161 0.000 1.161 1.157 1.161 1.157 1.17 1.16 Stime 0.023 0.000 0.024 0.021 0.024 0.024 0.021 0.021 Atime: 1.106 0.000 1.105 1.102 1.127 1.074 1.138 1.088 Collisions: 3275 Moves: 3814 Guesses: 8296 Perfect Rand 4x Itime 0.606 0.000 0.608 0.605 0.6 0.604 0.608 0.608 Stime 0.023 0.000 0.02 0.024 0.024 0.024 0.024 0.024 Atime: 0.569 0.000 0.567 0.563 0.551 0.579 0.574 0.58 Collisions: 1801 Moves: 1947 Guesses: 4036 Perfect Rand 10x Itime 0.254 0.000 0.254 0.251 0.254 0.258 0.254 0.254 Stime 0.027 0.000 0.027 0.029 0.027 0.024 0.027 0.027 Atime: 0.239 0.001 0.203 0.238 0.233 0.239 0.299 0.219 Collisions: 716 Moves: 732 Guesses: 1433