Сравнение исходного кода Java HashMap и карты Go

Java Go

предисловие

В Java реализация hashmap очень тонкая, и она постоянно оптимизируется, особенно в версии 1.8 появилось красно-черное дерево и оптимизировано расширение, а в Go карта существует как ключевое слово. исходный код двух, чтобы сравнить их сходства и различия, оба не потокобезопасны

Java(HashMap)

Сегменты в хэш-карте представляют собой массив следующим образом

transient Node<K,V>[] table;

Это структура Node, потому что у него есть следующая ссылка, поэтому, очевидно, это структура связанного списка, и то, что хранится в массиве, можно понимать как указатель на начало.

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; 
        final K key;
        V value;
        Node<K,V> next; // 链表的下一个Node的引用	
}

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

  • threadshold: Критическое значение для определения необходимости расширения емкости.При превышении этого порога длина корзины будет увеличена в 2 раза, что равно length*loadFactor
  • loadFactor: коэффициент нагрузки, доля элементов в длине, сверх этой доли длина будет увеличена в 2 раза
  • размер: количество элементов

Значение loadFactor по умолчанию в исходном коде Jdk равно 0,75, которое обычно не нужно изменять.Если вы считаете, что элементы на карте растут очень быстро, вы можете уменьшить ее.Если памяти мало, вы можете увеличить ее. .

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

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Здесь хеш-значение получается с помощью операции высокого порядка и операции по модулю, потому что эффективность операции & по модулю выше, чем у операции %, а длина ведра стабильна в n-й степени 2. Этот метод очень распространен в Jdk, включая ArrayDeque. Этот метод также используется в других пакетах для повышения эффективности.

Расширение (изменить размер)

Сегмент представляет собой массив. Массив не может быть расширен автоматически. Для хранения исходного массива можно использовать только новый массив. В java7 новое хэш-значение вычисляется каждый раз, когда выполняется расширение. В java8 используется побитовая операция AND & используется для реализации расширения.После повторного хеширования, повышения эффективности, очень тонкий

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) { 
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {                   
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {    // 按位与结果为0的时候位位置不变
    loTail.next = null;
    newTab[j] = loHead; 
}
if (hiTail != null) {   // 按位与结果为1的时候原来的位置移动原来长度
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

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

Go (карта ключевых слов)

Реализация карты в последней версии Go1.11 была перенесена с hmap.go в исходной среде выполнения на map.go в пакете среды выполнения.Если вы хотите просмотреть исходный код, вы можете перейти к клонированию копии на github. Во-первых, благодаря комментариям мы можем многому научиться.Принцип реализации map

  1. map представляет собой хеш-таблицу, данные хранятся в массиве сегментов, каждый сегмент содержит 8 k/v, а эффективность запроса повышается за счет старших 8 бит ключа.
  2. Расширение в go сильно отличается от такового в java: oldbucket не будет сразу перенесен в новое ведро, как в java, для миграции будет использоваться методrowWork только при доступе к ведру, и в конечном итоге оно будет завершено с помощью доступ ко всем миграциям
  3. Значение loadFactor по умолчанию равно 6,5.Согласно комментариям, этот результат является лучшим результатом после многих тренировок.

Ядром карты является структура hmap.

type hmap struct {
	count     int //元素个数
	flags     uint8
	B         uint8  
	noverflow uint16 
	hash0     uint32 
	buckets    unsafe.Pointer // buckets数组指针
	oldbuckets unsafe.Pointer // 扩容时复制数组指针
	nevacuate  uintptr        // 已经迁移的数量
	extra *mapextra 
}

Еще одна важная структура — bmap.

type bmap struct {
	tophash [bucketCnt]uint8
}

Как видно из комментариев в bmap, tophash хранит старшие восемь бит хеша 8 ключей, что быстрее при запросах.

Followed by bucketCnt keys and then bucketCnt values.

Followed by an overflow pointer.

В структуре bmap также есть две структуры, к которым необходимо получить доступ через операции с указателями, одна из них — это структура, такая как key0/key1/key2/key3/val0/val1/val2/val3, которая может сэкономить место, и, наконец, переполнение. указатель в итоге образует структуру, аналогичную той, что есть в java.Видно, что для решения конфликта адресов также используется метод zipper.

Расширение

Между расширением в go и java есть большая разница: сначала создается новый массив двойной длины для замены исходного массива, а затем oldbucket добавляет исходные элементы, и только потом при обращении к корзине, в которой находится текущий ключ. Только после этого будет вызываться методrowWork для повторного хеширования для переноса исходных элементов. Преимущество этого в том, что не нужно долго блокироваться из-за копирования всего массива при расширении.Карта в redis также использует этот метод, чтобы избежать блокировки на долгое время.

Точно так же карта в Go не безопасна для сопрограммы.Если вам нужна безопасность сопрограммы, есть три варианта.

  • Используйте способ инкапсуляции карты и rwlock в официальном блоге
  • Используйте стороннюю поточно-ориентированную карту, реализованную с сегментированными блокировками.
  • использовать sync.Map
Категории