Для чего в основном используется HashMap? почему ты хочешь сделать это?
Мы использовали hashmap много раз, основная цель — ускорить скорость поиска. Каждый, кто изучал структуру данных, знает, что запрос и изменение массива происходит очень быстро, но добавление элемента или удаление элемента — очень медленно, а связанный список — наоборот, очень медленно.В общем, чтобы улучшить скорость запроса, мы должны определить различные правила при вставке элементов, это увеличивает сложность.Если вы не понимаете, вы можете Найдите эту главу в соответствующей книге по алгоритмам.А наша хэш-карта — это структура данных, объединяющая массивы и связанные списки для увеличения скорости выполнения запросов. Необходимо понимать операцию сдачи hashmap.
# 图 解 h 数据 的 数据 数据
Ранее мы говорили, что хэш-карта — это структура, объединяющая массив и связанный список.
Таким образом, глядя на эту картину, каждый элемент массива на самом деле является связанным списком. Мы все знаем, что когда используется Hashmap, это нажатие клавишного значения ключа. Тогда в идеальном времени он должен быть каждый элемент массива, то есть соответствующий связанный список имеет только один узел. Эта эффективность самая быстрая. Поскольку это почти эквивалентно найти элемент в массиве.
Но если лицо нехорошее, или вообще алгоритм хеширования написан. Будет казаться, что остальные элементы этого массива пусты, и тогда данные, которые мы вставляем, находятся в связанном списке, соответствующем одной позиции:
Из-за этого поиск очень медленный. Первое равно o(1), второе равно o(n)
Глядя на картинку, вы также можете видеть, что наша хэш-карта позволяет ключу быть нулевым, но может быть только один элемент, ключ которого равен нулю, хотя ключ может быть нулевым, Но мы не поощряем это.
Понимание факторов нагрузки
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
Это исходный код хэш-карты jdk8 на моем компьютере.Обратите внимание, что мы можем знать, что по умолчанию, когда мы создаем хэш-карту, размер по умолчанию представляет собой массив из 16 элементов.
Так что же делает этот DEFAULT_LOAD_FACTOR?
Мы все знаем, что если размер массива нашей хеш-карты равен всего 16, так что, когда наши данные также имеют время 16, наилучшей ситуацией является элемент Соответствующие списку только два узла. Чтобы вставить данные 32, лучший результат цепочки имеет два узла. 128 Чтобы вставить данные, список Есть восемь узлов. Найти его наверняка снизит скорость.Чтобы улучшить скорость поиска, мы, очевидно, должны увеличить размер массива., Поэтому, когда расширяется до размера массива? Это когда количество элементов больше, чемдлина массива * коэффициент загрузки, нам нужно увеличить размер массива, чтобы удвоить исходный размер. Например: 1. Начальная длина массива по умолчанию — 16. 2. Когда количество вставленных элементов превысит 12, мы расширим длину массива до 32.
Почему это значение коэффициента загрузки равно 0,75, я не знаю. . . . Во всяком случае, вы знаете, что есть такая вещь. 0,75 должен быть лучшим алгоритмом для установки.
В чем смысл и цель увеличения длины массива?
Как мы уже говорили, мы можем увеличить скорость поиска данных после расширения длины массива. Может быть кто-то недостаточно понял, здесь мы приведем простой пример, который поможет вам понять.
-
Будем считать, что длина массива всего 2.5,7,9 и нужно вставить эти три элемента. Мы выбрали алгоритм хеширования и значения элементов массива по модулю длины.
-
Тогда очевидно, что после модуля 579 и 2 значение равно 1, тогда три элемента 5, 7 и 9 будут вставлены в позицию 1 этого массива длины 2.
-
Затем нам нужно найти три элемента числа 579, что, очевидно, медленнее, потому что для его поиска нам нужно перейти к связанному списку, соответствующему позиции a[1]. Итак, мы начинаем увеличивать длину массива
-
Длина расширенного массива равна 4. Тогда после 579 по модулю 4 соответствующие значения равны 1, 3, 1 и, очевидно, 5 и 9 помещаются в позицию a[1]. 7 было размещено a[3] в этой позиции.
-
Затем расширяем длину, тогда длина массива 8, 579 на 8 отсчетов соответственно соответственно соответственно 5, 7, 1 явных 5, 7, 9 эти три элемента соответствующие позиции То есть A [5], A [7], A [1], в это время наша эффективность поиска и только 2, эффективность контрастности массива значительно улучшена.
Описанный выше процесс мы называем перефразированием.
Понять исходный код hashmap в jdk7
Как упоминалось ранее, для хэш-карт наиболее важной является операция размещения. Давайте посмотрим на операции put jdk7.
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
//如果数组为空 先构造一个数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null的情况要特殊处理
if (key == null)
return putForNullKey(value);
//通过传进来的key的值 我们计算出一个hash的值
int hash = hash(key);
//用hash的值和数组长度一起计算出 这个key-value应该放入数组的位置，也就是数组中的索引值
int i = indexFor(hash, table.length);
//看看数组这个索引位置下的链表有没有key和传进来的key是相等的，如果有那么就替换掉，并且把老的值返回
//发生这种情况时，因为return了 所以函数到这里就结束掉了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果没发生上述情况 就意味着一个新的元素被增加进来
addEntry(hash, key, value, i);
return null;
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
//h是计算出来的hash值，length是数组长度 实际上这里就是取模操作。
//和我们前文中的例子是一样的，就等于 h%length.这种写法效率更高而已
return h & (length-1);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//这里也好理解哈，如果发生了要扩充数组长度的情况，那么hash值要重新计算
//重新计算的hash值 也要再利用一次重新计算出再数组中的索引位置
//threshold其实就是前文我们提到的 数组长度*负载因子
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//这里我们重点看一下这个resize的操作
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//构造出一个新的数组 容量当然翻倍啦
Entry[] newTable = new Entry[newCapacity];
//然后把老的数组的值放到新的数组里面
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//然后把新的数组的索引赋值
table = newTable;
//最后重新计算这个阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//接着看我们的transfer函数 实际上jdk7和8 关于hashmap最大的不同就在这里了
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//就跟前文中的例子一样，构建新数组的时候，老数组中的哪些元素在新数组中的索引我们都要重新计算一遍
//仅此而已
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
//这个也比较简单，实际上插入元素的时候，我们都是把新来的元素 放入链表的头部，然后让新来的元素的next指针指向
//来之前的链表的头部元素，所以jdk7的插入元素是在链表头部插入。
//在这个地方我们也可以再想明白一个问题，在transfer函数中，我们重新计算索引的时候，先去老的链表里从链表头部
//取一个元素出来放入到新数组的索引里，取完第一个再取第二个
//那么后面的元素也是后计算出索引放入到新的数组对应的链表里。既然是后放入，那么肯定后放入的会在链表的头部了
//这就代表一个结果：因为我们每次插入元素是在链表头部插，所以如果新的数组构造出来以后，我们的索引计算出来
//仍旧相等的话，这2个元素仍旧会放到一个索引对应的链表中，只不过之前在头部的，现在去了尾部。
//也就是说在transfer的过程中，链表的顺序被倒置
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Разница между jdk8 и jdk7
Есть два основных момента.
1. Конфликт хэшей, то есть если вычисляемые значения хэшей совпадают, разве мы не помещаем их в связанный список? jdk7 — вставить новый элемент в голову, jdk8 вставляет новые элементы в конец.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果hash相等key也相等 那么先拿着引用 等会直接替换掉老值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//这边是红黑树的逻辑，jdk8在链表长度超过8的时候会转红黑树，这属于数据结构
//的范畴 我们日后再说。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//这边应该明显的看出来，新来的元素在链表的位置是在尾部的，而不是jdk7种的头部
p.next = newNode(hash, key, value, null);
//转红黑树的操作 如果链表长度大于8的话 红黑树的问题属于数据结构问题 我们日后再说
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
-
Второй момент — самая большая разница: операция resize() в jdk8 выполняется намного быстрее, чем в jdk7, и список изменения размера в jdk7 будет инвертирован, а в jdk8 — нет.
Рассмотрим следующий сценарий:
Начальная длина массива 16, добавляем 2 элемента, хешкод 5, хешкод 21. После берем остаток 16, Позиция вычисляемого индекса 5 соответствует a[5], а 21 соответствует a[5], так что эти две позиции существуют в одном и том же связанном списке.
Когда все больше и больше элементов, наконец, превышают порог, массив расширяется до длины 32. В это время 5 и 21 будут делиться на 32. 5 соответствует a[5], а 21 соответствует положению a[21.Обратим внимание на хэш-код 21, который соответствует предыдущей позиции. После удвоения a[5] в позиции 21 добавляется 16. Это 16 на самом деле длина расширения.Эта математическая формула может быть абстрагирована как
позиция перед расширением oldIndex Расширенная позиция либо остается прежней, либо oldIndex + длина до расширения.
С помощью этого набора математических правил мы можем оптимизировать его при изменении размера, и нам не нужно пересчитывать хэш и индекс, как в jdk7.
Ниже приведен основной процесс изменения размера jdk8.
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
//这个链表用来表示扩充以后 新增bit为0的链表 也就是说这个链表上的元素扩充前后位置不变
Node<K,V> loHead = null, loTail = null;
//这个用来表示扩充以后要挪动位置的链表 挪动位置也就是说新增的bit为1了。
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
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) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//这个地方 对应着上文我们的公式
newTab[j + oldCap] = hiHead;
}
}
}
}
}
hashmap в многопоточности
Хорошо известная хэш-карта, очевидно, не поддерживает синхронизацию потоков. Основная причина заключается в том, что потоки легко мешают процессу изменения размера хэш-карты. Очень вероятно, что порядок выполнения промежуточной операции изменения размера и операции передачи будет нарушен.Вы должны знать, что операция передачи представляет собой связанный список. Легко может показаться, что вы указываете на меня, а я указываю вам на такой круговой связанный список.Как только круговой связанный список возникает, базовая программа сообщит об ошибке в бесконечном цикле.
Более того, даже если эта экстремальная ситуация не возникает, если операция размещения не заблокирована, изменение значения по желанию приведет к тому, что выход будет несовместим с тем, который вы ввели.
Наша хэш-таблица — более экстремальный метод, который напрямую блокирует метод put. Хотя это делается раз и навсегда, но крайне неэффективно. Не рекомендуется.
Конечно, мы можем сделать другой путь.
HashMap hm=new HashMap();
Collections.synchronizedMap(hm);
Это также обеспечивает синхронизацию потоков. Посмотрите на принцип:
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
/**
* @serial include
*/
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
synchronized (mutex) {m.putAll(map);}
}
public void clear() {
synchronized (mutex) {m.clear();}
}
private transient Set<K> keySet;
private transient Set<Map.Entry<K,V>> entrySet;
private transient Collection<V> values;
Лучше, чем hashtable, но все равно добавлю слишком много замков. Улучшен, но все еще не достаточно хорош.
ConcurrentHashMap — идеальное решение таких проблем.
Короче говоря, причина, по которой ConcurrentHashMap более эффективен, чем приведенная выше схема, заключается главным образом в том, что
Мы можем рассматривать хэшмап как набор банков, например, в этот набор входят Промышленный и коммерческий банк Китая, Строительный банк Китая, Торговый банк Китая, Сельскохозяйственный банк и так далее.
Первые два почти до тех пор, пока вы приходите копить деньги, независимо от того, в какой банк вы хотите пойти, вы должны стоять в очереди.
Гранулярность ConcurrentHashMap будет уменьшена до такой степени, что пока вы вносите деньги, вы будете стоять в очереди только у дверей банка, в который хотите пойти. Эффективность значительно выше.
Чтобы по-настоящему понять исходный код ConcurrentHashMap, нам нужно иметь глубокое представление о ключевом слове volatile transient, а также о механизме блокировки ReentrantLock. Давайте сначала продадим его здесь. Мы поговорим о ConcurrentHashMap позже, и каждый может его понять.
Кратко об опыте использования
(1) HashMap: он хранит данные в соответствии со значением hashCode ключа.В большинстве случаев его значение может быть расположено напрямую, поэтому он имеет высокую скорость доступа, но порядок обхода неясен. HashMap позволяет ключу одной записи быть нулевым не более чем и позволяет значению нескольких записей быть нулевым. HashMap не является потокобезопасным, то есть несколько потоков могут одновременно записывать HashMap в любое время, что может привести к несогласованности данных. Если вам необходимо обеспечить безопасность потоков, вы можете использовать метод synchronizedMap Collections, чтобы сделать HashMap потокобезопасным, или использовать ConcurrentHashMap.
(2) Hashtable: Hashtable — это устаревший класс. Общие функции многих отображений аналогичны HashMap. Разница в том, что он наследуется от класса Dictionary и является потокобезопасным. В любой момент времени Hashtable может писать только один поток, а параллелизм не так хорош, как ConcurrentHashMap, потому что ConcurrentHashMap вводит блокировки сегментов. Hashtable не рекомендуется использовать в новом коде, его можно заменить HashMap, когда не требуется потокобезопасность, и ConcurrentHashMap, когда требуется потокобезопасность.
(3) LinkedHashMap: LinkedHashMap является подклассом HashMap, который сохраняет порядок вставки записей.При использовании Iterator для обхода LinkedHashMap первая полученная запись должна быть вставлена первой, или она может быть создана с параметрами и отсортирована в соответствии с порядком доступа. .
(4) TreeMap: TreeMap реализует интерфейс SortedMap, который может сортировать записи, которые он сохраняет, в соответствии с ключом. По умолчанию используется сортировка в порядке возрастания значения ключа. Вы также можете указать компаратор сортировки. Когда итератор используется для обхода TreeMap, полученные записи сортируются. При использовании отсортированных карт рекомендуется использовать TreeMap. При использовании TreeMap ключ должен реализовывать интерфейс Comparable или передавать пользовательский компаратор при построении TreeMap, иначе во время выполнения будет создано исключение типа java.lang.ClassCastException.