что такое хеширование
Хеш-таблица (хеш-таблица), мы обычно называем ее хеш-таблицей или хэш-таблицей, в ней используется функция, состоящая в том, что массив поддерживает произвольный доступ к данным в соответствии с индексами, поэтому хэш-таблица фактически является расширением массива, эволюционировавшим из массива. Можно сказать, что нет хеш-таблицы без массивов.
Например, у нас есть 100 позиций, и в нумерации нет обычного 4-значного числа.Теперь мы хотим быстро получить информацию о товаре через номер.Как это сделать?Мы можем поместить 100 пунктов информации о товаре в массив, и передать номер элемента%100, например, способ получить значение, продукт со значением 1 помещается в позицию с нижним индексом 1 в массиве, а продукт со значением 2 мы помещаем его в позицию с индексом 2 в массиве. По аналогии игрок с номером K помещается в позицию с индексом K в массиве. Поскольку номер продукта соответствует индексу данных через хэш-функцию (число %100), но когда нам нужно запросить информацию о продукте с номером x, мы используем тот же метод для преобразования числа в индекс массива, тогда мы можем Получить данные из позиции соответствующего индекса массива. Это типичная идея хеширования.
Из вышеприведенного примера можно вывести следующее правило: когда хеш-таблица использует массив для поддержки произвольного доступа в соответствии с индексом, временная сложность равна O(1). Сопоставьте ключевое значение элемента с помощью хеш-функции (номер элемента %100) Проецируется как нижний индекс, а затем сохраняет данные в соответствующей позиции нижнего индекса в массиве. Когда мы запрашиваем элементы по значению ключа, мы используем ту же хеш-функцию для преобразования значения ключа в индекс массива и берем его из позиции соответствующего индекса массива. данные.
открытая адресация
Когда дело доходит до хеширования (или хеш-таблицы), все больше знакомы с HashMap или LinkedHashMap, и сегодняшней главной героиней является ThreadLocalMap, который является внутренним классом в ThreadLocal. Обойти его при анализе исходного кода ThreadLocal невозможно.
Поскольку хеш-таблица использует массив, независимо от того, как спроектирована хэш-функция, неизбежно возникает конфликт хэшей. В приведенном выше примере, если идентификаторы двух продуктов равны 1001 и 1101 соответственно, их данные будут помещены в одну и ту же позицию в массиве, что приведет к конфликту.
Принцип ящика, также известный как принцип ящика Дирихле, принцип ящика. Одно из простых выражений: если есть n клеток и n+1 голубей, и все голуби содержатся в клетках для голубей, то хотя бы в одной клетке есть как минимум 2 голубя.
В качестве реализации хеш-таблицы ThreadLocalMap использует способ разрешения конфликтов — открытую адресацию для решения этой проблемы.
вставка элемента
Суть открытой адресации заключается в повторном обнаружении свободного места и вставке его в случае возникновения коллизии хэшей. Когда мы вставляем данные в хеш-таблицу, если определенные данные хэшируются хеш-функцией, а место хранения уже занято, мы начинаем с текущего места и по очереди ищем в обратном направлении, чтобы увидеть, есть ли какое-либо свободное место, пока мы найди. .
Как видно из рисунка, размер хеш-таблицы равен 10, и до того, как в хеш-таблицу вставлен элемент x, в хэш-таблицу было вставлено 6 элементов. После алгоритма Hash x хешируется до позиции с индексом 7, но в этой позиции уже есть данные, поэтому возникает конфликт. Итак, мы искали назад один за другим, чтобы увидеть, есть ли свободная позиция, и мы не нашли ни одной свободной позиции после обхода до конца, поэтому мы начали поиск с начала таблицы, пока не нашли свободную позицию 2 , поэтому мы вставили его в эту позицию.
поиск элемента
Процесс поиска элемента в хеш-таблице чем-то похож на процесс вставки. Мы используем хеш-функцию, чтобы найти хеш-значение, соответствующее значению ключа искомого элемента, а затем сравниваем элемент с хэш-значением в массиве и с искомым элементом. Если они равны, значит это искомый элемент, иначе ищется по порядку. Если вы перешли к свободной позиции в массиве и еще не нашли ее, это означает, что искомого элемента нет в хеш-таблице.
удаление элемента
Подобно массивам, ThreadLocalMap поддерживает не только операции вставки и поиска, но и операции удаления. Для хэш-таблиц, использующих линейное зондирование для разрешения коллизий, операция удаления немного отличается. Мы не можем просто сделать удаляемый элемент пустым.
Помните операцию поиска, о которой мы только что говорили? При поиске, как только мы находим свободную позицию с помощью метода линейного обнаружения, мы можем определить, что данные не существуют в хеш-таблице. Однако если это свободное место будет удалено позже, это приведет к сбою исходного алгоритма поиска. Данные, которые изначально существовали, будут считаться несуществующими. Как решить эту проблему?
Мы можем перехешировать данные, которые не являются нулевыми, после удаления элемента, так что логика запроса не пострадает.
Другой способ: удаленные элементы могут быть специально помечены как удаленные. При линейном поиске, если он встречает пробел, помеченный как удаленный, он не останавливается, а продолжает поиск.
Процесс перефразирования описан здесь:
При удалении элемента 8 сначала установите значение нижнего индекса 8 в null, а затем перехешируйте непустой элемент массива за ним.
Например, элемент после 8 равен 9, а его исходное положение (9%10=9) — 9, поэтому он не перемещается.
Следующий элемент — 19, который должен быть на позиции с индексом 9, но он уже занят, поэтому найдите следующую свободную позицию, позиция с индексом 3 свободна, и поместите ее в tab[3].
Тогда следующий элемент 1 не перемещается в tab[1], а позиция элемента 7 находится в tab[7], поскольку он уже занят, он помещается в следующую свободную позицию tab[8].
Следующий элемент все еще 19, здесь, поскольку tab[9] уже занят, он помещается в следующую свободную позицию tab[0]. Тогда позиция последнего элемента 4 находится на вкладке [4], поэтому он не перемещается. Следующая позиция элемента 4 пуста, и весь процесс перефразирования завершается.
коэффициент загрузки
Как вы могли обнаружить, линейное зондирование на самом деле довольно проблематично. Когда в таблице HASH вставлена все больше и больше данных, вероятность хеш-столкновения увеличится, количество свободных позиций станет менее и меньше, а время линейного обнаружения станет дольше и дольше.
В крайних случаях нам может потребоваться обнаружить весь хеш-таблица, поэтому временная сложность худшего случая является O (n). Аналогично, при удалении и смотрите, также можно ли линеаризовать весь список списков, чтобы найти данные для поиска или удаления.
Независимо от того, какой метод обнаружения используется, хэш-функция спроектирована разумно, когда в хеш-таблице не так много свободных позиций, вероятность хеш-коллизии будет сильно увеличена. Для того, чтобы максимально обеспечить эффективность работы хеш-таблицы, в общем, мы постараемся сделать все возможное, чтобы в хеш-таблице был определенный процент свободных слотов. Мы используем коэффициент загрузки для представления количества вакансий.
Формула для расчета коэффициента загрузки:Коэффициент загрузки хеш-таблицы = количество элементов, заполненных в таблице / длина хэш-таблицыЧем больше коэффициент загрузки, тем меньше свободного места, тем больше коллизий и производительность хеш-таблицы будет снижаться.
Анализ исходного кода
Определение ThreadLocalMap
Основной структурой данных ThreadLocal является ThreadLocalMap, и ее структура данных выглядит следующим образом:
static class ThreadLocalMap {
// 这里的entry继承WeakReference了
static class Entry extends WeakReference<ThreadLocal<?>> {
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}
// 初始化容量,必须是2的n次方
private static final int INITIAL_CAPACITY = 16;
// entry数组,用于存储数据
private Entry[] table;
// map的容量
private int size = 0;
// 数据量达到多少进行扩容,默认是 table.length * 2 / 3
private int threshold;
Из определения ThreadLocalMap видно, что ключом Entry является ThreadLocal, а значением является значение. В то же время Entry также наследует WeakReference, поэтому ссылка на ключ (экземпляр ThreadLocal), соответствующий Entry, является слабой ссылкой. А коэффициент загрузки определяется как две трети длины массива.
метод set()
private void set(ThreadLocal<?> key, Object value) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
// 采用线性探测,寻找合适的插入位置
for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
// key存在则直接覆盖
if (k == key) {
e.value = value;
return;
}
// key不存在,说明之前的ThreadLocal对象被回收了
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}
// 不存在也没有旧元素,就创建一个
tab[i] = new Entry(key, value);
int sz = ++size;
// 清除旧的槽(entry不为空，但是ThreadLocal为空)，并且当数组中元素大于阈值就rehash
if (!cleanSomeSlots(i, sz) && sz >= threshold)
expungeStaleEntries();
// 扩容
if (size >= threshold - threshold / 4)
resize();
}
Основные шаги приведенного выше исходного кода следующие:
- Метод линейного зондирования использовался для определения подходящей позиции вставки. Сначала определите, существует ли ключ, и если он существует, то он напрямую перезаписывается. Если ключ не существует, чтобы доказать, что он был удален сборщиком мусора, вам необходимо заменить старый элемент новым элементом.
- Соответствующий элемент не существует, необходимо создать новый элемент
- Очистить запись не пусто, а использовать элементы ThreadLocal (ключ ввода повторно используется) для предотвращения утечек памяти.
- При выполнении условий: размер >= порог - порог / 4, массив будет расширен в два раза больше, чем раньше, а положение элементов массива будет пересчитано и перемещено (перехешировано). Например, исходный размер массива 16 в начале, при размере >= (16*2/3=10) - (10/4) = 8 он будет расширен, и размер массива будет расширен до 32.
Будь то метод replaceStaleEntry() или метод cleanSomeSlots(), наиболее важным вызовом метода является expungeStaleEntry(), который вы можете найти в командах get, set и remove в ThreadLocalMap.
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
// 删除对应位置的entry
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
Entry e;
int i;
// rehash过程,直到entry为null
for (i = nextIndex(staleSlot, len);(e = tab[i]) != null; i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
// k为空,证明已经被垃圾回收了
if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
// 判断当前元素是否处于"真正"应该待的位置
if (h != i) {
tab[i] = null;
// 线性探测
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}
Приведенный выше код перехеширования легче понять в сочетании с описанием в начале статьи.При добавлении, получении и удалении из ThreadLocalMap перехеширование будет выполняться согласно условиям.Условия следующие
- Объект ThreadLocal переработан.В настоящее время ключ в записи имеет значение null, а значение не равно null. Это вызовет перефразирование
- Когда пороговое значение достигает двух третей емкости ThreadLocalMap
получить () метод
private Entry getEntry(ThreadLocal<?> key) {
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
// 现在数据中进行查找
if (e != null && e.get() == key)
return e;
else
return getEntryAfterMiss(key, i, e);
}
// 采用线性探测找到对应元素
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while (e != null) {
ThreadLocal<?> k = e.get();
// 找到元素
if (k == key)
return e;
// ThreadLocal为空,需要删除过期元素，同时进行rehash
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
Метод линейного обнаружения проходит через все процессы get и set, понять принцип и посмотреть код очень просто.
метод удаления()
private void remove(ThreadLocal<?> key) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
if (e.get() == key) {
e.clear();
expungeStaleEntry(i);
return;
}
}
}
При удалении удалить старую запись, а потом перефразировать.
Использование ThreadLocal
public class Counter {
private static ThreadLocal<Integer> seqCount = new ThreadLocal<Integer>(){
public Integer initialValue() {
return 0;
}
};
public int nextInt(){
seqCount.set(seqCount.get() + 1);
return seqCount.get();
}
public static void main(String[] args){
Counter seqCount = new Counter();
CountThread thread1 = new CountThread(seqCount);
CountThread thread2 = new CountThread(seqCount);
CountThread thread3 = new CountThread(seqCount);
CountThread thread4 = new CountThread(seqCount);
thread1.start();
thread2.start();
thread3.start();
thread4.start();
}
private static class CountThread extends Thread{
private Counter counter;
CountThread(Counter counter){
this.counter = counter;
}
@Override
public void run() {
for(int i = 0 ; i < 3 ; i++){
System.out.println(Thread.currentThread().getName() + " seqCount :" + counter.nextInt());
}
}
}
}
Эффект операции следующий:
Thread-3 seqCount :1
Thread-0 seqCount :1
Thread-3 seqCount :2
Thread-0 seqCount :2
Thread-0 seqCount :3
Thread-2 seqCount :1
Thread-2 seqCount :2
Thread-1 seqCount :1
Thread-3 seqCount :3
Thread-1 seqCount :2
Thread-1 seqCount :3
Thread-2 seqCount :3
ThreadLocal фактически предоставляет копию переменной для каждого потока, обеспечивая одновременный доступ без каких-либо последствий. Из этого также видно, что сценарии приложений между ним и синхронизированным различны.Синхронизированный — сделать изменение переменных каждым потоком видимым для других потоков, а ThreadLocal — предотвратить влияние других потоков на данные объектов потока. , Это наиболее подходит для сценария, который должен заключаться в совместном использовании данных между различными уровнями разработки в одном потоке.