Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one of the partitions.Assuming this data structure is implemented within an array insertions are performed by computing the beginning partition location corresponding to the key for the element in question and a linear search is performed until a sentinel empty-value is found (or the end of the partition). Searches are performed analogously.What is the name of the data structure described above? Does it have any advantage over a hash-table?
What is the name of this partition-indexed key-value data structure?
ds.data structures;terminology
If you implement your data structure using an array, you can view it as a bidimensional array (M rows, N/M columns) where the row index is what you call key for the element.After you find the row you can put your element in a free cell of the row. When the row is full, you can either:stop (the element cannot be inserted)delete the oldest element of the row (if this is not a problem for you :-)))proceed and scan the next rows (assuming that you store the whole key + value in each cell) until you find an empty cell (or the array is full)The algorithm is fastest than hash table with chaining but options 1. and 2. have obvious limitations.If you use option 3. you can use all the N elements (cells) of the array, but the performance of the algorithm can degrade to linear search very quickly.I really don't know if this algorithm has a particular name, but you can consider it as a STATIC HASHING TECNIQUE. Perhaps it is suitable for quick hash-table implementations in limited environments (firmware, drivers, ....).