The scatter search technique is implemented using the data structure known as a scatter table, or hash table. This implementation of the hash table has configuration options to work with the following variants of the technique:
● For simplicity, we assume that the information record stored in the hash table should be set to match the type of the key used.
● The size of the scatter table, which we denote hereafter as tableSize, indicates the number of positions in the table. As we have seen, this parameter does not only indicate the amount of memory that is reserved when constructing the table, but it also affects the behavior of the scatter function and the scan function.
● The scatter function maps the value of the key k of type Key to a table position in the range [0..tableSize-1].
The following scatter functions are implemented:
■ Module, h(k) = k % tableSize.
■ Sum-based, h(k) = sum(ki) % tableSize.
■ Pseudo-random, h(k) = {srand(k); rand()}.
● To resolve collisions in the scatter table i implemented the next techniques:
○ Open scattering, each position in the hash table contains a dynamic, list-like data structure where all synonyms, generated by the scattering function, are inserted.
○ Closed dispersion, each position of the hash table contains a static, array-like data structure where all the synonyms generated by the dispersion function are inserted where the maximum number of records that can be stored in that position is set.
● In the implementation of the closed dispersion technique, the following additional parameters are defined;
○ The block size, which we denote blockSize, indicates the maximum number of records that can be stored in the same table position.
○ The scan strategy for resolving the overflow in a block implements the following scan functions, where k is the value of the key, and the parameter i is the number of the scan attempt.
■ Linear scan, g(k,i) = i.
■ Quadratic scan, g(k,i) = i2.
■ Double dispersion, g(k,i) = f(k) * i
■ Redispersion, g(k,i) = f(i)(k).
+ The elimination technique is not implemented. Only insertion and search are implemented at the moment.
None
No installation required :)
- Download the files
- Compile with g++
g++ bigint_main.cc bigint_func.cc
- All ready!
(You can find instructions about the arguments of the program by running the program whit the argument "-help")
./a.out --help
Distributed under the MIT License.
Joel Óscar - josc.margut@gmail.com