Help write a normal hash function. Everything I found is a bit like double hashing. And there are no examples. Here is the only thing that I found:

  1. Set i = h1 (K)
  2. If TABLE [i] is empty, then go to step 6, otherwise, if the required address is used at this address, the algorithm is completed.
  3. Set c = h2 (K)
  4. Set i = i - c, if i <0, then i = i + M.
  5. If TABLE [i] is empty, go to step 6. If the search is located at this address, the algorithm is completed, otherwise it returns to step 4.
  6. Insert. If N = M - 1, then the algorithm terminates on overflow. Otherwise, increase N, mark the cell TABLE [i] as busy and set the value of the key K to it.

It is not clear which function to take H1 (k) and H2 (k)

    1 answer 1

    Apparently in the problem it is assumed that K is a number (integer). If this is not the case, then by K (for example, a string) it is necessary to calculate an integer (suppose the sum of all bytes of the string, BUT for practice this is a very bad algorithm for calculating the hash code). Further, the problem assumes that M is the size of the table, and N is the number of keys already placed in it.

    Then a good method is to make the table size a prime number. In this case (yes, actually, in any) it is necessary to take as H1 the remainder of dividing K by M. i will be in the interval 0 - M-1 (that is, inside the table, which is what we need).

    Further, c is a step on the table, it should be in the range 1 - M-1, the choice of H2 itself. 1 and M-1 are trivial (but badly, there will be a high leveling of synonyms). Apparently for c, you can try the remainder of dividing K by Mm (the closest smaller than M is a prime number), it can be calculated once (at the first call) and remembered.