HashMap为什么会是面试中的常客呢？我觉得有以下几点原因： * 考察你阅读源码的能力 * 是否了解内部数据结构 * 是否了解其存储和查询逻辑 * 对非线程安全情况下的使用考虑 Некоторое время назад коллега брал интервью у Ant Financial и ему задали этот вопрос.На самом деле, многие кейсы выводятся из связи между hashMap, hashTable и ConcurrentHahMap.Конечно, есть и прямые расследования по принципу hashMap. По сути, суть та же, просто проверить, понятны ли вам принципы, реализации и сценарии использования этих часто используемых коллекций в коллекциях. С одной стороны, мы его очень много используем в своей разработке, и конечно есть много людей, которые его используют, но не так много людей, которые используют его хорошо (я тоже много его использую, но не использую хорошо). Так что я воспользовался этой возможностью (принудительно растирая волну), чтобы еще раз взглянуть на этот HashMap.
Эта статья основана на jdk1.7.0_80, немного измененном после jdk 1.8, что будет подробно описано позже.
отношения наследования
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
hashMap реализует три интерфейса Map, Cloneable и Serializable и наследует абстрактный класс AbstractMap. hashTable наследует класс Dictionary, а также реализует три интерфейса: Map, Cloneable и Serializable.
главный атрибут
DEFAULT_INITIAL_CAPACITY начальная емкость по умолчанию 16 (хэш-таблица равна 11) константа
/**
* The default initial capacity - MUST be a power of two.
* 默认初始容量-必须是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
MAXIMUM_CAPACITY константа максимальной емкости по умолчанию
/**
* 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.
*如果有一个更大的值被用于构造HashMap,则使用最大值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
Коэффициент загрузки DEFAULT_LOAD_FACTOR (по умолчанию 0,75) постоянный
/**
* The load factor used when none specified in constructor.
* 加载因子，如果构造函数中没有指定，则使用默认的
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
EMPTY_TABLE пустая таблица по умолчанию
/**
* An empty table instance to share when the table is not inflated.
* 当表不膨胀时共享的空表实例。
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
table table, при необходимости измените размер. Длина должна быть степенью двойки.
Это также основная структура хранения в хэш-карте.
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
размер указывает количество KV, хранящихся в HashMap (сумма KV в связанном списке/дереве)
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
Переменная расширения порога указывает, что операция изменения размера будет выполнена, когда размер HashMap превысит пороговое значение.
порог=вместимость*коэффициент нагрузки
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
Коэффициент загрузки loadFactor Коэффициент загрузки используется для измерения степени заполнения HashMap. Значение loadFactor по умолчанию — 0,75f. Метод расчета коэффициента загрузки HashMap в реальном времени: размер/емкость вместо деления количества занятых сегментов на емкость. (Последующее введение в концепцию ведер)
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
modCount
Количество раз, когда структура этого HashMap изменяется, это те, которые изменяют количество отображений в HashMap или изменяют его внутреннюю структуру (например, перефразируют). Это поле используется для быстрого отказа итераторов для представлений коллекций HashMap. (см. ConcurrentModificationException).
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
hashSeed Случайное значение, связанное с этим экземпляром, хеш-код для хеш-ключа, усложняющий поиск хеш-коллизий. Если 0, то альтернативное хеширование отключено.
/**
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find. If 0 then
* alternative hashing is disabled.
*/
transient int hashSeed = 0;
Структурный анализ
static class Entry<K,V> implements Map.Entry<K,V>
Хэш-карта хранит каждое значение K-V с помощью статического внутреннего класса Entry, который наследуется от внутреннего класса Entry на карте. Посмотрите на конкретный код:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //键对象
V value; //值对象
Entry<K,V> next; //指向链表中下一个Entry对象，可为null，表示当前Entry对象在链表尾部
int hash; //键对象的hash值
/**
* 构造对象
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
/**
* 获取key
*/
public final K getKey() {
return key;
}
/**
* 获取value
*/
public final V getValue() {
return value;
}
/**
* 设置value，这里返回的是oldValue(这个不太明白，哪位大佬清楚的可以留言解释下，非常感谢)
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* 重写equals方法
*/
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
/**
* 重写hashCode方法
*/
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
HashMap — это коллекция, используемая для хранения пар ключ-значение, каждая пара ключ-значение также называется Entry. Эти пары ключ-значение (Entry) разбросаны и сохранены в массиве, который является основой HashMap (то есть таблица-сегмент выше).
Посмотрите на картинку:
Когда хэш-карта инициализируется, значение по умолчанию для каждого пробела равно нулю. При вставке элементов (специально вставленных в следующем анализе) конкретная позиция индекса вычисляется в соответствии со значением ключа. Если это повторяется, используется метод вставки хвоста. чтобы вставить его в следующий связанный список.
вставка хвоста Раньше я тестировал, вставляя 17 фрагментов данных (количество конкретных данных произвольно, чем больше число, тем выше вероятность повторения)
public static void main(String[] args) throws Exception {
HashMap<String, Object> map=new HashMap<>();
for (int i = 0; i < 170; i++) {
map.put("key"+i, i);
}
System.out.println(map);
}
Глядя на следующие контрольные точки, мы можем сделать выводы выше: 1. Для хранения конфликта индексов будет использоваться связанный список;
2. Способ вставки связанного списка — вставка из хвоста (официальное объяснение состоит в том, что обычно данные, вставленные позже, используются чаще), что способствует поиску.
основной метод
Наиболее часто используемый метод hashMap в нашей разработке заключается в том, чтобы сначала создать объект HashMap, затем сохранить его, а затем получить его; соответствующий метод:
Конструктор
поставить функцию
получить функцию
Конструктор
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity 指定的初始化容量大小
* @param loadFactor the load factor 指定的负载因子
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
//如果初始化容量小于0，则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始化容量大于最大容量，则使用默认最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果负载因子小于0或者非数值类型，则抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//初始化负载因子
this.loadFactor = loadFactor;
//初始化threshold
threshold = initialCapacity;
//这个初始化方法是个空方法，应该是意在HashMap的子类中由使用者自行重写该方法的具体实现
init();
}
Два других конструктора на самом деле являются вызовами вышеуказанного конструктора:
//只制定默认容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用HashMap默认的容量大小和负载因子
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
Другой:
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
Создает новую HashMap с тем же отношением сопоставления, что и указанная карта. HashMap создается с коэффициентом загрузки по умолчанию (0,75) и начальной емкостью, достаточной для размещения сопоставлений в указанной карте.
положить метод Во-первых, мы все знаем, что ключ в хэш-карте может быть нулевым, что также является наиболее часто задаваемым вопросом на собеседовании. Тогда позвольте мне сначала понять, почему значение null может быть сохранено в качестве значения ключа.
public V put(K key, V value) {
//如果table是空的
if (table == EMPTY_TABLE) {
//inflate：扩容/膨胀的意思
inflateTable(threshold);
}
//如果key为null 此处敲下桌子，为什么可以存null？
if (key == null)
//执行putForNullKey方法，这个方法的作用是如果key为null，就将当前的k-v存放到table[0],即第一个桶。
return putForNullKey(value);
//对key进行一次hash运算，获取hash值
int hash = hash(key);
//根据key值得hash值和表的长度来计算索引位置
int i = indexFor(hash, table.length);
//移动数据，插入数据
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);
//上面Entry中的setValue中也有提到，返回的都是旧的数据
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
метод хеша:
Извлекает хэш-код объекта и применяет к полученному хэшу дополнительную хэш-функцию, которая защищает от хеш-функций низкого качества. Это важно, потому что HashMap использует хэш-таблицы двух длин, иначе вы столкнетесь с коллизиями хэш-кодов, которые неразличимы в более низком порядке. Примечание. Нулевые ключи всегда сопоставляются с хешем 0, поэтому индекс 0.
/**
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//这个函数确保在每个比特位置上仅以恒定倍数不同
//的散列码具有有限数量的冲突（在默认加载因子下大约为8）。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Описание конкретного процесса конфликта:
пустая таблица hashmap
Вставьте элемент, индекс равен 3 посредством вычисления хэша, потому что в текущей позиции 3 нет элемента, поэтому вы можете вставить его напрямую
Вставьте элемент снова и рассчитайте индекс с помощью хеш-вычисления или 3. Если есть конфликт, поместите вновь вставленный элемент в позицию исходного существующего элемента и укажите его рядом с исходным существующим элементом.получить метод Возвращает значение, которому сопоставлен указанный ключ, или null, если эта карта не содержит сопоставлений ключей.
public V get(Object key) {
//和存null key一样，取的时候也是从table[0]取
if (key == null)
return getForNullKey();
//获取entry
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
метод getEntry
final Entry<K,V> getEntry(Object key) {
//size等于0，说明当前hashMap中没有元素，直接返回null（每个entry默认值为null）
if (size == 0) {
return null;
}
//根据key值计算hash值
int hash = (key == null) ? 0 : hash(key);
//通过hash值获取到索引位置，找到对应的桶链进行遍历查找
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//如果找到则返回，如果没有链表指针移动到下一个节点继续查找。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
Механизм расширения
Как упоминалось выше, пороговое значение, переменная расширения, означает, что операция изменения размера будет выполнена, когда размер HashMap превысит пороговое значение. Его метод расчета: порог=мощность*коэффициент нагрузки.
Из приведенной выше формулы мы можем узнать, что время расширения хэш-карты равноКогда текущее значение текущего размера превышает емкость, умноженную на коэффициент загрузки, расширение будет запущено. Взгляните на исходный код:
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果当前size超过threshold 并且满足桶索引位置不为null的情况下，扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容之后为原来的两倍
resize(2 * table.length);
//重新计算hash值
hash = (null != key) ? hash(key) : 0;
//重写计算索引
bucketIndex = indexFor(hash, table.length);
}
//执行具体的插入操作
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//先取到当前桶的entry
Entry<K,V> e = table[bucketIndex];
//将新的数据插入到table[bucketIndex]，再将之前的entry通过链表简介到table[bucketIndex]的next指向；前面的图已经进行了描述。
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Следует отметить, что расширение не выполняется после заполнения хэш-карты, см. следующие точки останова:
Через конструктор по умолчанию создается новый объект карты, через цикл for вставляется 12 кусков данных, а точка останова находится в конце выполнения.Мы видим, что текущая емкость таблицы равна 16, а пороговое значение переменной раскрытия равно 12. (16x0,75).Теперь 12 меняем на 13.В настоящее время 13 все еще меньше 16, но расширение хэш-карты все еще срабатывает. Текущая емкость таблицы — 32 (увеличена в два раза по сравнению с предыдущим размером), а порог — 24 (32x0,75).Из этих двух диаграмм мы знаем:
Емкость после каждого расширения в два раза превышает первоначальную емкость (2n)
Запуск расширения происходит не из-за того, что текущий объект хэш-карты заполнен, а из-за того, что время запуска управляется пороговой переменной расширения.
резюме
Эта статья просто берет волну исходного кода и переводит комментарии в исходном коде в сочетании с моим собственным пониманием, а также кратко представляет применение хвостовой интерполяции в хэш-карте посредством отладки точек останова. Наконец, решение, когда возникает конфликт индексов в следующей хэш-карте, описано с помощью нескольких рисунков. Hashmap действительно глубокий и поверхностный в интервью, но все же необходимо прочитать исходный код Следующие два блога рекомендуются для всех.