BSCL: algoritmo de Busca Sequencial de Colisões Lineares

Abstract

Access to database indexes, compiler symbol tables, operating system commands, routing device ports, telecommunication registers, processor caches, among others, are inserted into areas of Computer Science research with a common point - search algorithm. These applications can handle large sets of elements where the cost of searching for a key can be high. Thus, there is a need to develop algorithms that, in addition to efficiency, focus on efficiency, both in processing time and in the use of system resources. This dissertation aims to propose a sequential search algorithm called Linear Collision Sequential Search (BSCL), based on the probabilistic distribution of Poisson, for large static data arrays where key columns are ordered and evenly distributed numbers. As a result, we present a comparison of the BSCL with an algorithm already consecrated and in use in several computational routines - Perfect Hash Table. The Experimental validation focuses on three metrics - processing time, number of iterations, and memory resources. The dissertation concludes that BSCL is superior to the Perfect Hash in computation time and memory resources. Its main contribution is to demonstrate that simpler routines can have more expressive computational results.