<p>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".</p>

<p>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:</p>

<ol>
<li>stop (the element cannot be inserted)</li>
<li>delete the "oldest" element of the row (if this is not a problem for you :-)))</li>
<li>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)</li>
</ol>

<p>The algorithm is fastest than hash table with chaining but options 1. and 2. have obvious limitations.</p>

<p>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.</p>

<p>I really don't know if this algorithm has a particular name, but you can consider it as a <strong>STATIC HASHING</strong> TECNIQUE. Perhaps it is suitable for quick hash-table implementations in limited environments (firmware, drivers, ....).</p>

CC BY-SA 2.5
2011-01-24T13:42:24.610Z
2011-01-24T14:25:24.900Z
2011-01-24T14:25:24.900Z
Marzio De Biasi
<p>Sounds like a hash table to me, with collision resolution by chaining.</p>

CC BY-SA 2.5
2011-01-25T10:41:54.810Z
It is *direct* chaining (in contrast to *indirect* chaining)
Raphael
CC BY-SA 2.5
2011-01-24T16:23:14.927Z
2011-01-24T16:23:14.927Z
Gautam Kamath
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-25T10:43:13.153Z
You can avoid getting stuck while still having empty space by rehashing/reassigning keys.
Raphael
CC BY-SA 2.5
2011-01-25T12:18:57.910Z
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.
Vinicius dos Santos
CC BY-SA 2.5
2011-01-24T11:40:16.400Z
2011-01-24T11:40:16.400Z
Vinicius dos Santos
<p>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.</p>

<p>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.</p>

<p>What is the name of the data structure described above? Does it have any advantage over a hash-table?</p>

CC BY-SA 2.5
2011-01-23T23:41:43.567Z
Sounds like a hash table to me, with collision resolution by chaining
Gautam Kamath
CC BY-SA 2.5
2011-01-24T00:50:27.727Z
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.
user3392
CC BY-SA 2.5
2011-01-24T06:39:55.590Z
@Gautam make this a full answer ?
Suresh Venkat
<ds.data-structures><terminology>
What is the name of this partition-indexed key-value data structure?
user3392
# What is the name of this partition-indexed key-value data structure?

(Asked by: username_0 on 2011-01-23)

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?

**Tags:** ds.data-structures, terminology

> **Comments:**
> **username_1**: Sounds like a hash table to me, with collision resolution by chaining  
> **username_0**: 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.  
> **username_2**: @Gautam make this a full answer ?  

---

## 3 answers

### Answer by username_3 on 2011-01-24. Score: 1 | Accepted answer

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, ....).


---

### Answer by username_1 on 2011-01-24. Score: 3

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

> **Comments:**
> **username_4**: It is *direct* chaining (in contrast to *indirect* chaining)  

---

### Answer by username_5 on 2011-01-24. Score: 1

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.

> **Comments:**
> **username_4**: You can avoid getting stuck while still having empty space by rehashing/reassigning keys.  
> **username_5**: 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.  

---

