Алгоритм кэширования часов

Мне кажется, вы сами себе все усложняете. Причина, по которой люди используют этот подход, заключается в том, что он ОЧЕНЬ прост.

Это позволит избежать замены записи, которая недавно использовалась.

private final Object[] objects = new Object[5];
private final boolean[] referenced = new boolean[objects.length];
private int clock = 0;

public Object getOrCache(Object obj) {
    for (int i = 0, objectsLength = objects.length; i < objectsLength; i++) {
        Object o = objects[i];
        if (obj.equals(o)) {
            referenced[i] = true;
            return obj;
        }
    }
    while(referenced[clock]) {
        referenced[clock] = false;
        incrClock();
    }
    objects[clock] = obj;
    incrClock();
    return obj;
}

private void incrClock() {
    if (++clock >= objects.length)
        clock = 0;
}

Это не беспокоит.

private final Object[] objects= new Object[5];
private int clock = 0;

public Object getOrCache(Object obj) {
   for(Object o: objects) 
       if (obj.equals(o))
           return obj;
   objects[clock++ % objects.length] = obj;
   return obj;
}

Прав ли я, когда думаю, что все эти объекты поначалу будут иметь clockbit = 0?

Если они не указаны, то да.

Должны ли мы пытаться найти тот же объект в кеше без часовой стрелки (только ifInCache(comingObject))?

Да, вы должны проверить, находится ли объект уже в кеше. В этом случае опорный бит (тактовый бит) будет установлен в 1.

Что произойдет, если такого объекта в кеше нет? Где стартовая позиция для стрелки часов?

Если объект еще не находится в кеше, вы проверяете объект по стрелке часов. Позиция руки будет последней позицией в кеше, если она еще не заполнена, и в противном случае останется неизменной между двумя поисками в кеше (она будет увеличена самими поисками).

Пример (размер кеша = 5):

• добавить A -> рука на 0 до и на 1 после
• добавить B -> рука на 1 до и на 2 после
• добавить C -> рука на 2 до и на 3 после
• добавить D -> рука на 3 до и на 4 после
• добавить E -> рука на 4 до и на 0 после
• добавить F -> рука в 0, проверить указанный бит A, если он равен 0, заменить и увеличить руку, в противном случае увеличить только руку -> после этого рука будет в 1

Обратите внимание, что если у всех объектов бит ссылки установлен на 1, объект в руке будет заменен, так как после проверки объекта его бит ссылки установлен на 0, и, таким образом, при второй проверке объекта бит будет равен 0.

Изменить:

Вот расширенная/скорректированная версия кода @PeterLawrey:

private final Object[] objects= new Object[5]; 
private final boolean[] referenced = new boolean[5]; //boolean for simplicity
private int clock = 0;

public Object getOrCache(Object obj) {
   for(int i = 0; i < objects.length; ++i) {
     if (obj.equals(objects[i])) {
       referenced[i] = true; //object has been referenced, note that this is for simplicity and could be optimized
       return obj;
     }
   }

   //loop over the entries until there is a non-referenced one
   //reference flags are removed in the process
   while( referenced[clock] ) {
     referenced[clock] = false;
     clock = (clock + 1) % objects.length; //for clarity
   }

   //replace the object at the current clock position and increment clock
   objects[clock] = obj;
   referenced[clock] = true;
   clock = (clock + 1) % objects.length; //for clarity

   return obj;
}