Hello, I found a hash table implementation, but I don’t understand the logic of the push method:

 public boolean push(T1 x, T2 y) { int h = returnHash(x); // это мы посчитали hashCode для ключа int i=0; try{ if (table[h].isDeleted() ) { // проверили было ли там какое-то значение когда-нибудь table[h] = new Pair<T1, T2>(x, y);// если да то записали новое return true; } for (i = h + 1; i != h; i = (i + 1) % table.length) {//вот это место вообще не понятно if (table[i].isDeleted() || table[i].getKey() == x) { table[i] = new Pair<T1, T2>(x, y); return true; } } return false; } catch(NullPointerException e) { table[h] = new Pair<T1, T2>(x, y); return true; } }

Where did this cycle come from? Why is it needed? Why not just check that the cell is null and write there, or not?

    1 answer 1

    The fragment of the HashMap implementation you quoted uses the open addressing method to resolve collisions.

    Unlike the chain method, where elements with keys that have the same hash codes are placed in the same basket (in the list or tree), in the open addressing method, elements with keys that have the same hash codes are placed directly in the array itself (but in other baskets).

    Where did this cycle come from? Why is it needed?

    This cycle is used to search for an empty basket to place an added pair in it when a collision occurs.

    Why not just check that the cell is null and write there, or not?

    If you look carefully at the code, here (in particular) it is implemented: first, based on the hash code of the key, the basket number ( h ) is calculated, then the table[h] is accessed:

     table[h].isDeleted()

    in which, if table[h] == null , a NullPointerException will be thrown, which is immediately handled:

     table[h] = new Pair<T1, T2>(x, y);

    Therefore, if there is nothing and was not in the basket with number h , then the pair will be placed there, if there was something in the basket before, but now it is not (case when table[h].isDeleted() == true ), then again, the pair will be placed in this basket, and if the basket is busy, it will search for another basket in which the added pair will be placed.

    I want to note that the implementation of HashMap from the JDK uses a different method for resolving collisions, namely, the chaining method .

    By the way, this is some rather strange implementation of adding a pair to a HashMap :

    • If all baskets are occupied, then the next added pair will simply not be added to the HashMap (in this implementation, the array does not expand and the pairs are not redistributed to the baskets);
    • In HashMap method for inserting a pair is traditionally referred to as put , and push refers to the stack.
    • How here, interestingly, get in this class is implemented, if push can push a pair into, one might say, a random index on the table . Probably also a cycle across the table ... - Regent