Посмотрите на [Hash] из HashMap, словарь Redis. . .

Java

предисловие

Сегодня проверил рыбу.HashMapИсходный код, я думаю об интервью с Дашеном, и интервьюер спросилRedis 字典а такжеHashMapЧем отличается процесс хэширования. . . Честно говоря, я тоже видел дизайн и реализацию Redis (рекомендуется), но точно описать не могу, поэтому написал эту статью.

Примечание: Поскольку эта статья посвящена процессу хеширования, часть исходного кода зависит от простых для понимания описаний великих богов~

Хеш-функция (хеш-алгоритм)

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

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

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

  • хэш-коллизия: вход и выход хэш-функции не являются уникальными соответствиями.Например, хеш-значения, полученные из входов A и B хеш-функции, оба являются C.

  • Общие хеш-функции:

прямая адресация цифровой анализ квадратный метод метод складывания остаточный метод метод случайных чисел

  • Предположительно все знают сценарии HashMap и словаря Redis, и будут выбирать исходя изМетод остаткаОптимизирован для использования в качестве хэш-функции. Концепция каждого метода не будет здесь повторяться, пожалуйста, перейдите кПроверьте это здесь.

Решение Hash Collision (Hash Collision)

  • hash？->散列算法的选择->散列冲突怎么解决Предположительно, это мнение большинства моих коллег. Итак, давайте посмотрим, каковы основные алгоритмы разрешения коллизий хэшей?

открытая адресация

  • Как только произошла коллизия, переходим к поиску следующего пустого хеш-адреса, простейший алгоритм компании следующий.f(key) = (f(key) + d) mod m(d= 1,2,...,m-1)Возьми каштан, поставьmВместо 12 вставляем 26, 37 по очереди, (26+1)% 12 = (37+1)%12, есть конфликт хэшей, поэтому снова (37+2)%12 = 4, значение хеша другое, конфликт разрешен.

Перефразирование

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

метод цепного адреса

  • Сначала используйте метод остатка, чтобы получить хеш-значение.Если хэш-значение конфликтует, вставьте конфликтующие узлы один за другим через связанный список, чтобы сформировать структуру, как показано ниже. Следующий пример:f(x) = key mod 12В сцене видно, что 48 % 12 = 12 % 12 = 0, образуя связанный список.

Закон об общей зоне разлива

  • Используйте дополнительное общее хранилище для хранения элементов с конфликтующими хэш-значениями.

HashMap

Алгоритм хеширования HashMap

виньеткаLOAD_FACTOR(коэффициент нагрузки)

  • каждый знаетHashMapпо умолчаниюLOAD_FACTORдля0.75, какова его функция? Следуйте исходному коду, чтобы следовать трассировке ниже ~

  • newОдинHashMap, комментарии к исходному коду говорят намcapacity16,load_factorсоставляет 0,75.

/**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
  • вместе сputЭлементы, мы должны проводить расширение, увидетьresize()Функция относится к знаковой части поста.
else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  • Видно, что порог пройден черезcapacityумножить наload_factorпроизводное, то есть16 * 0.75 = 12.HashMapЕсли элементов больше, чем порог, емкость должна быть расширена, что можно понимать какНебольшой порог относительно емкости снижает вероятность коллизии хэшей, потому что вероятность коллизии хэшей с 16 элементами ниже, чем у 12 элементов при той же хэш-функции..

Формула и анализ хеш-функции

  • Алгоритм хеширования HashMap аппроксимирует деление с остатком, но не работаетMODопераций, но использовать побитовые операции, предполагаяkeyвходное значение, хэш-функцияf(key)Конкретная формула выглядит следующим образом:
f(key) = hash(key) & (table.length - 1) 
hash(key) = (h = key.hashCode()) ^ (h >>> 16)
  • hash(key) & (table.length - 1)правдаtable.lengthФактически аналогичный эффект имеет оптимизированная версия остатка, основанная на методе деления и оставления остатка. из-заHashMapВозможности расширяются каждый разtable.lengthбудет2^n, поэтому битовые операции значительно эффективнее.
  • >>>это беззнаковый оператор сдвига вправо, мы знаемhashCode()Диапазон значений очень широк, а сама возможность конфликта очень мала, но это согласуется с вышеизложенным.table.length - 1Эта вероятность увеличивается, потому чтоtable.lengthявляется небольшим значением. Вот почему используйте>>> 16причина,hashCode()Верны как старший, так и младший битыf(key)При определенном влиянии распределение получается более равномерным, а вероятность коллизии хэшей меньше.

Разрешение конфликтов хэшей HashMap

  • HashMapРазрешение хеш-коллизии, очевидно,метод цепного адреса, собственно, это и видно из конструкции.
  • МогуHashMapизresize()Этот метод также можно увидеть, см. исходный код ниже. . . Примечания к .
if (oldTab != null) {
			// 遍历旧数组上的节点
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 当前链表只有一个节点（没有散列冲突的情况）
                    if (e.next == null)
	                    // 通过散列算法计算存放位置并放入
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
	                    // 红黑树去了。。。
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
	                    // 低位链表、高位链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
	                        // 遍历发生散列冲突的链表
                            next = e.next;
                            // hash值小于旧数组容量 放入低位链表
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // hash值大于等于旧数组大小 放入高位链表
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 低位链表放在原来index下
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 高位链表放在原来index + 旧数组大小
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;

Словарь Redis

Введение в структуры данных

а такжеHashMapпримерно в том же месте

Во-первых, краткое описание структуры данных словаря Redis было полностью затенено, когда я учился в колледже.Cязык.

typedef struct dictht {
	// 哈希表数组
	dictEntry **table;

	// 哈希表大小
	unsigned long size;

	// 哈希表大小掩码，用于计算索引值
	// 总是等于size - 1
	unsigned long sizemask;
	
	// 哈希表已使用节点数
	unsigned long used;
	
} dictht
  • Есть массив хэш-таблиц, он выглядит знакомо, иNode<K,V>[]Аналогично по эффекту, давайте посмотримdictEntryэтот класс.
typedef struct dictEntry {
	// 键
	void *key

	// 值
	union {
		void *val;
		unit64_tu64;
		int64_ts64;
	} v

	// next指针
	struct dictEntry *next;
}

  • Снова немного знакомая пара ключ-значение!keyсвойства содержат ключи в парах ключ-значение, аvСвойства содержат значения, где значение пары ключ-значение может быть указателем,unit64_t,int64_tЦелое.nextУказатель на другой узел хеш-таблицы, который может соединять несколько хэш-таблиц с одной и той же парой ключ-значение в связанный список.

  • Видно, что до сих порHashMapПо сути, разницы нет, за исключением нескольких дополнительных свойств (размер хеш-таблицы, количество используемых узлов, маска и т. д.).

разница

  • Я только что увидел, что нижний слой словаря реализован структурой хеш-таблицы, так что же представляет собой истинное лицо словаря?
typedef struct dict {
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;

	// 哈希表(上文讲的)
	dictht ht[2];

	// rehash索引
	// 当rehash不在进行时，值为-1
	int trehashidx;
}
  • До сих пор была представлена ​​структура данных словаря Redis.На следующем рисунке показан словарь в нормальном состоянии.

Алгоритм хеширования словаря Redis

  • рассчитатьхэш-значениеПроцесс вычисления хэшей для функций на основе словаря, которые вычисляют хэши:hash = dict -> type->hashFunction(key)
  • Используйте атрибут SizeMask и значение HASH HASH HASH TALL для расчета значения индекса, в зависимости от ситуацииht[0]илиht[1]. На самом деле иHashMapизhash(key) & (table.length - 1)то же самое, потому что в примечаниях говоритсяsizemaskвсегда равноsize - 1.

index = hash & dict->ht[x].sizemask

  • Алгоритм вычисления хеш-значения, используемый Redis, таков:MurmurHash2, автор не может объяснить,связь дается.

Разрешение конфликтов хэшей словаря Redis

  • Хэш-таблица Redis также используетметод цепного адреса, каждый узел имеетnextУказатель, несколько узлов образуют односвязный список, иHashMapРазница в том, что, поскольку хвостового указателя нет, используйтепробка для головыДобавьте новый узел в начало связанного списка.

Разница между Redis и HashMap

Глядя на хэш-алгоритм и разрешение хеш-конфликтов, особой разницы нет, так в чем же разница? То естьПерефразирование.

Rehash

  • Как упоминалось ранее, в структуре данных словаря есть две хеш-таблицы (ht[2]), секрет здесь.

  • RehashЦель состоит в том, чтобы поддерживать коэффициент загрузки хеш-таблицы в разумных пределах.расширить или сжать.

  • Действуйте следующим образом:

    1. для словаряht[1]Хеш-таблицы выделяют пространство, если вы выполняетерасширятьоперация, тоht[1]Размер в первую очередь больше или равенht[0].used *2из2^n; если исполнениесокращатьоперация, тоht[1]Размер первого больше или равенht[0].usedиз2^n.
    2. будет сохранен вht[0]Все пары ключ-значение вrehashприбытьht[1]выше, т. е. пересчитать значения хэша и индекса ключа, а затем поместить пару ключ-значение вht[1]в указанном месте в хеш-таблице.
    3. когдаht[0]Все содержащиеся пары ключ-значение переносятся вht[1]Позже(ht[0]становится пустой хэш-таблицей), отпуститеht[0],Будуht[1]Установить какht[0], И вht[1]Заново создайте пустую хеш-таблицу в следующий разrehashподготовиться к.

  • Примечание: Progressive Rehash в этой статье не упоминается.Автор рисунка действительно немотивирован.Структура данных более сложная,пожалуйста поймите.

Суммировать

В этой статье кратко анализируется алгоритм хеширования и решение хеш-коллизии.HashMap,Redis 字典изhash, взгляды не обязательно правильные, прошу критиковать и исправлять!

использованная литература

Категории