2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Sounds like a hash table to me, with collision resolution by chaining $\endgroup$
    – Gautam Kamath
    Jan 23, 2011 at 23:41
  • $\begingroup$ Yes, I guess you are right. The only difference I see is the case when one of the partitions is at maximum occupancy due to the lack of indirection in the described scheme. $\endgroup$
    – user3392
    Jan 24, 2011 at 0:50
  • 1
    $\begingroup$ @Gautam make this a full answer ? $\endgroup$
    – Suresh Venkat
    Jan 24, 2011 at 6:39

3 Answers 3

Reset to default
1
$\begingroup$

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:

  1. stop (the element cannot be inserted)
  2. delete the "oldest" element of the row (if this is not a problem for you :-)))
  3. 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, ....).

Improve this answer
$\endgroup$
3
$\begingroup$

Sounds like a hash table to me, with collision resolution by chaining.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is direct chaining (in contrast to indirect chaining) $\endgroup$
    – Raphael
    Jan 25, 2011 at 10:41
1
$\begingroup$

Your description reminds me a kind of cache I have studied some time ago. Instead of storing only one entry for each hash value, you can store a small quantity of entries. This reduce the number of misses when you have addresses with the same hash value in the same program, and you can check if an address is in a (small) partition in small time, implementing it by hardware.

Comparing with hash table with collision resolution by chaining, I can think a simple advantage: the chains can't get long, since the partitions size is at most N/M, bounding the search time. On the other hand, if one of your partitions get full, you get stuck, even if you have lots of free space in other partitions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You can avoid getting stuck while still having empty space by rehashing/reassigning keys. $\endgroup$
    – Raphael
    Jan 25, 2011 at 10:43
  • $\begingroup$ Yes, if this is possible. Vor also suggested some alternate solutions for this space problem. My answer was made assuming the structure as described, I didn't consider changes on it. $\endgroup$
    – Vinicius dos Santos
    Jan 25, 2011 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.