class RobinHoodBackwardShiftHashMap implements LoadedPagesMap {

    @Override public void put(int grpId, long pageId, long val, int ver) {
        assert grpId != 0;

        // initial index is also ideal for inserted element
        int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets;

        int swapCnt = 0;

        int grpIdToInsert = grpId;
        long pageIdToInsert = pageId;
        long valToInsert = val;
        int verToInsert = ver;
        int idxIdealToInsert = idxInit;

        for (int i = 0; i < numBuckets; i++) {
            int idxCurr = (idxInit + i) % numBuckets;

            final long base = entryBase(idxCurr);
            final int dibEntryToInsert = distance(idxCurr, idxInit);

            final int curGrpId = getGrpId(base);
            final long curPageId = getPageId(base);
            final int curIdealBucket = getIdealBucket(base);
            final long curVal = getValue(base);
            final int curVer = getVersion(base);
            final int dibCurEntry = distance(idxCurr, curIdealBucket);

            if (isEmpty(curGrpId, curPageId)) {
                setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert);

                setSize(size() + 1);

                return;
            }
            else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) {
                if (swapCnt != 0)
                    throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr));

                setValue(base, valToInsert);

                return; //equal value found
            }
            else if (dibCurEntry < dibEntryToInsert) {
                //swapping *toInsert and state in bucket: save cur state to bucket
                setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert);

                idxIdealToInsert = curIdealBucket;
                pageIdToInsert = curPageId;
                grpIdToInsert = curGrpId;
                valToInsert = curVal;
                verToInsert = curVer;

                swapCnt++;
            }
        }

        // no free space left
        throw new IgniteOutOfMemoryException("No room for a new key");
    }

    public  RobinHoodBackwardShiftHashMap(long baseAddr, long size);

}