Hello dear colleagues, I am faced with a task in which it is necessary:

Create a directory-collection that should have methods:

  1. boolean insert(T key, V value) ;
  2. V get(T key) ;
  3. boolean delete(T key) ;
  4. Implement an iterator.
  5. Internal implementation must use an array.
  6. It is necessary to provide a fixed time to insert and receive.

And my problem is that I do not understand how, there can be a fixed time of insertion, and receipt. After all, if I use an array, I still have to go over the keys to match. And even if I manage to build a hash table based on the associated structure, still get time, for the last and first elements will be different (the option using trees is excluded, because they have not yet passed).

Please help me with the idea of ​​how this should fundamentally work so that all the conditions of the task set before me are observed. ps just please do not write the code, I want it myself, I just need to get the idea how it should work.

  • one
    For a set of arbitrary objects, it will not be possible to implement insert / extraction always in O(1) , since in the general case collisions are always possible. In the same HashMap in the worst case (when all elements are in the same basket), the extraction will be for O(n) if the basket is implemented as a linked list and for O(log n) if the basket is implemented as a balanced tree. - post_zeew

1 answer 1

And my problem is that I do not understand how, there can be a fixed time of insertion and receipt.

In general, insert / remove an element in a constant time will not work. In the absence of collisions, it is possible to insert / remove an element beyond O(1) , but collisions (for an unlimited set of objects) are always possible. In the case of collisions, it is possible to insert / remove an element for O(n) (in the case of using a linked list) and for O(log n) (in the case of using a balanced tree).

After all, if I use an array, I still have to go over the keys to match

If you use an array with normal addressing, then yes, element retrieval by key will be possible in O(n) . But you can implement a hash table, in which, at best, the element will be retrieved in constant time.

And even if I manage to build a hash table based on the associated structure, it’s still time to get , for the last and first elements it will be different

Yes, it will vary. And it will be constant only if the desired item is first in the basket.

the option of using trees is excluded because have not yet passed

Even in this case, the time to retrieve an item is not always constant.

Please help with the idea how this should work in principle so that all the conditions of the task set before me are met

You need to implement a simple HashMap , but the 6th item will be executed only partially. Sometimes an element will be inserted / removed in a constant time, and sometimes linear or logarithmic (this depends on the data structure that will be used to resolve collisions).

The main idea of HashMap is that the hash code of the key is used to calculate the index of an element in the array (basket number). In the simplest case, the basket number can be obtained as:

 int index = HASH_CODE % TABLE_LENGTH;

Where:

  • HASH_CODE - element hash key;
  • TABLE_LENGTH - the size of the array that is used to store items (number of baskets).

To resolve collisions, you can use, for example, the chaining method (it is used in HashMap ), or open addressing (in this case, the element with the matching hash code is located in the next next basket).

Read how HashMap - you need to implement a similar data structure.

In general, your question is very general and voluminous. It is better to divide it into several questions, then you can give a specific answer.