Java hashed lock table

Question

Есть ли структура или lib в java, предназначенная для использования в качестве «хеш-таблицы для блокировок»?

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

Я выполняю замену update-replace на предыдущее значение, а не на добавление, чтобы исключить некоторые параллельные библиотеки в jdk.

Ниже моя попытка реализации:

private final Object[] locks = new Object[256]; 
    { 
    for (int i = 0; i < 256; i++) { 
     locks[i] = new Object(); 
    } 
    } 

    final static int p = 64; 
    byte[] hashTable = new byte[1 << p]; 
    int populatedCount = 0; 

    public void add(String s, int i) { 
    int h = GetHash(s); 
    int hashBucket = h >>> (32 - p); 
    int lockHash = h & 0xFF; 
    int oldValue; 
    synchronized (locks[lockHash]) { 
     oldValue = this.hashTable[hashBucket]; 
     this.hashTable[hashBucket] = (byte) Math.max(this.hashTable[hashBucket], i); 
    } 
    if (oldValue == 0) { 
     this.populatedCount++; 
    } 
    } 

Что мне действительно нужно, это редкий одновременно примитивный массив ...

Answer 1

Если понял corrctly, вам нужно получить атомарно и замены для примитивный массив (здесь: int []). Верный?

Если это так, вы должны прочитать о AtomicInteger. Это класс, который точно обеспечивает эти атомные операции. Вы можете сделать AtomicInteger [].

Но - при изучении Java API - лучшее решение может быть найдено: AtomicIntegerArray. Объект этого класса содержит int [] в одном из своих полей и, он обеспечивает атомные операции над своими значениями.

---

EDIT

Хммм ... Требование сначала сделать расчет (максимум в этом случае), удерживая замок, кажется, немного сложнее.

Следующий подкласс может сделать трюк:

public class MyAtomicIntegerArray extends AtomicIntegerArray { 
    // constructors (see also class AtomicIntegerArray) 

    public int setIfGreater(int index, int value) { 
     while(true) { 
      int oldValue = get(index); 
      int newValue = Math.max(value, oldValue); 
      if(compareAndSet(index, oldValue, newValue)) 
       return oldValue; 
     } 
    } 
} 

while(true) необходим, так как метод compareAndSet может вернуться false, если другой поток обновляется значение в это время. В этом случае нам нужно снова рассчитать.

После этого вы использовать этот класс, и этот метод в вашем коде:

private static final ARRAY_SIZE = ...; 

private final MyAtomicIntegerArray hashTable = new MyAtomicIntegerArray(ARRAY_SIZE); 

public void add(String s, int i) { 
    int h = GetHash(s); 
    int hashBucket = h >>> (32 - p); 
    int oldValue = hashTable.setIfGreater(hashBucket, i); 
    if (oldValue == 0) { 
     this.populatedCount++; 
    } 
} 

Answer 2

Я предполагаю, что это решение является более хака и работает, только если целочисленный ключ находится в диапазоне 0-255/-128 до 127.

Вы обсуждали, как вы не можете синхронизировать свой примитивный ключ просто из-за его примитива. Почему бы не преобразовать его в объект?

Возьмите значение lastHash и применить метод Integer.valueOf() на нем, чтобы получить объект Integer затем синхронизировать сам объект Integer как таковые:

public void add(String s, int i) { 
    int h = GetHash(s); 
    int hashBucket = h >>> (32 - p); 
    int lockHash = h & 0xFF; 
    int oldValue; 
    //Subtract 128 to move the range of values into the cached range of -128 to 127. 
    Integer lockVal = Integer.valueOf(lockHash - 128); 

    synchronized (lockVal) { 
     oldValue = this.hashTable[hashBucket]; 
     this.hashTable[hashBucket] = (byte) Math.max(this.hashTable[hashBucket], i); 
    } 
    if (oldValue == 0) { 
     this.populatedCount++; 
    } 
} 

возвращения объекта Integer для чисел от -128 до 127 всегда будут то же самое из-за кэширования, как определено в Integer.valueOf(), показанный здесь:

Этот метод всегда будет хранить значения в диапазоне от -128 до 127 включительно и может кэшировать другие значения за пределами этого диапазона.

В этом случае, вы технически получили себе целый ряд объектов, которые кэшируются и гарантированно не изменяются для целого диапазона от -128 до 127, таким образом вызывая Integer.valueOf() на эти цифры были бы идеальным для вашего дело.