Алгоритм - реализовать две функции, которые назначают / освобождают уникальные идентификаторы из пула

Question

Я пытаюсь найти хорошее решение для этого вопроса -

Реализуйте две функции, которые назначают / освобождают уникальные идентификаторы из пула. Использование памяти должно быть сведено к минимуму, а назначение / освобождение должно быть быстрым, даже в условиях высокой конкуренции. alloc() возвращает доступный идентификатор релиза (id) выпускает ранее назначенный идентификатор

Первой мыслью было сохранить карту идентификаторов и доступности (на логическом уровне). Что-то вроде этого

Map<Integer, Boolean> availabilityMap = new HashMap();

public Integer alloc() {
    for (EntrySet es : availabilityMap.entrySet()) {
        if (es.value() == false) {
            Integer key = es.key();
            availabilityMap.put(key, true);
            return key;
        }
    }
}

public void release(Integer id) {
    availabilityMap.put(id, false);
}

Однако это не идеально для нескольких потоков, и "использование памяти должно быть минимизировано, а назначение / освобождение должно быть быстрым, даже при высокой конкуренции".

Что было бы хорошим способом оптимизировать использование памяти и скорость? Для использования памяти, я думаю, карту следует заменить другой структурой данных, но я не уверен, что это такое. Что-то вроде битовой карты или битового набора? Как я могу сохранить идентификатор и доступность в этом случае? Для параллелизма мне придется использовать блокировки, но я не уверен, как эффективно справиться с конфликтами. Может быть, поместить имеющиеся идентификаторы в отдельные блоки, чтобы каждый из них мог быть доступен независимо? Есть хорошие предложения?

Answer 1

Редактировать: Изменен нижний страж, исправлена ​​ошибка

---

Во-первых, не перебирайте всю карту, чтобы найти доступный идентификатор. Вам нужно только постоянное время, чтобы сделать это.

Чтобы сделать это быстро, вы можете сделать следующее:

1. Создать int index = 1; для вашего счетчика. Технически это число сгенерированных идентификаторов + 1, и всегда > 0,

2. Создать ArrayDeque<Integer> free = new ArrayDeque<>(); разместить бесплатные идентификаторы. Гарантированный постоянный доступ.

3. Когда вы выделяете ID, если очередь свободных ID пуста, вы можете просто вернуть счетчик и увеличить его (т.е. return index++;). В противном случае, возьми его голову и верни это.

4. Когда вы отпускаете идентификатор, нажмите на ранее использованный идентификатор на free Deque.

5. Запомни synchronize ваши методы.

Это гарантирует O(1) распределение и освобождение, и оно также сохраняет распределение довольно низким (буквально один раз за free). Хотя это синхронизировано, это достаточно быстро, чтобы это не было проблемой.

Реализация может выглядеть так:

import java.util.ArrayDeque;

public class IDPool {
    int index = 1;
    ArrayDeque<Integer> free = new ArrayDeque<>();

    public synchronized int acquire() {
        if (free.isEmpty()) return index++;
        else return free.pop();
    }

    public synchronized void release(id) {
        free.push(id);
    }
}

---

Кроме того, если вы хотите, чтобы список бесплатных идентификаторов был уникальным (как и в случае чего-либо важного), а также постоянным, вы можете сделать следующее:

1. Используйте HashMap<Integer id, Integer prev> держать все сгенерированные идентификаторы. Помните, что это не нужно заказывать или даже повторять.

   • Технически это будет стек, закодированный в хэш-карте.
   • Высокоэффективные реализации этого существуют.
   • На самом деле, любой неупорядоченный int -> int Карта будет делать здесь.

2. Отследить top Идентификатор для бесплатного набора идентификаторов. Помните, что 1 не может представлять ничего, а ноль используется, так что вам не нужно его упаковывать. (Идентификаторы всегда положительны.) Первоначально, это было бы просто int top = 1;

3. При выделении идентификатора, если есть свободные идентификаторы (т.е. top >= 2), сделайте следующее:

   • Установить новый top к старому headзначение в free карта.
   • Установить старый top Значение в карте до 0, маркировка его используется.
   • Вернуть старое top,

4. Выпуская старый идентификатор, сделайте это вместо этого:

   • Если старый идентификатор уже находится в пуле, верните его раньше, чтобы мы не повредили его.
   • Установите значение идентификатора на карте к старому top,
   • Установить новый top к идентификатору, так как он всегда используется последним.

Оптимизированная реализация будет выглядеть так:

import java.util.HashMap;

public class IDPool {
    int index = 2;
    int top = 1;
    HashMap<Integer, Integer> pool = new HashMap<>();

    public synchronized int acquire() {
        int id = top;
        if (id == 1) return index++;
        top = pool.replace(id, 0);
        return id;
    }

    public synchronized void release(id) {
        if (pool.getOrDefault(id, 1) == 0) return;
        pool.put(id, top);
        top = id;
    }
}

При необходимости вы могли бы использовать растущий целочисленный массив вместо хеш-карты (он всегда непрерывный) и добиться значительного прироста производительности. На самом деле, именно так я и буду реализовывать это. Для этого потребовалось бы небольшое количество битов, потому что я бы сохранил размер массива до следующей степени 2.

---

Да... Мне пришлось написать похожий пул на JavaScript, потому что мне нужны были умеренно быстрые идентификаторы в Node.js для потенциально высокочастотной и долгоживущей связи IPC.

Хорошая вещь об этом состоит в том, что он обычно избегает распределений (наихудший случай - один раз для каждого полученного идентификатора, когда ни один не освобожден), и он очень пригоден для последующей оптимизации в случае необходимости.

Answer 2

Прежде всего, вы не хотите бегать по всей карте, чтобы найти доступный идентификатор.

Таким образом, вы можете поддерживать два набора идентификаторов, первый для доступных идентификаторов, а второй - для распределенных идентификаторов.

Тогда это сделает распределение / выпуск довольно простым и быстрым.

Также вы можете использовать ConcurrentMap для обоих контейнеров (наборов), это уменьшит конкуренцию.