В этой статье будет объяснен принцип реализации соответствующей реализации HashMap в фреймворке коллекции java, а затем проанализирован исходный код HashMap JDK7 (JDK8 будет другим, вы можете сами прочитать исходный код HashMap JDK8, если вам нужно знать) .
Общие изменения HashMap в JDK7 и JDK8 (на самом деле это часто задаваемый вопрос на собеседовании~):
1.7 использует массив + связанный список, 1.8 использует массив + связанный список/красно-черное дерево, то есть когда длина связанного списка превышает определенную длину в 1.7, он меняется на хранение красно-черного дерева.
1.7 Необходимо пересчитывать хеш-значение и позицию индекса при расширении емкости В 1.8 хэш-значение не пересчитывается, а новая позиция индекса вычисляется умелым использованием операции & с емкостью после расширения емкости.
1.7 использует метод вставки заголовка для вставки связанного списка, а 1.8 использует метод вставки хвоста.
В 1.7 принят метод вставки заголовка, и исходный порядок элементов в связанном списке будет изменен во время расширения, так что связанный список будет образовывать цикл в параллельном сценарии; в 1.8 принят метод вставки хвоста , который сохранит исходные элементы связанного списка при расширении порядка, не будет проблем с формированием кольца из связанного списка.
содержание
-
что такое хеш-таблица
-
Принцип реализации HashMap
-
Почему длина массива HashMap должна быть степенью двойки?
-
Переопределение метода equals требует одновременного переопределения метода hashCode.
-
Суммировать
1. Что такое хеш-таблица
Прежде чем обсуждать хэш-таблицу, давайте в общих чертах разберемся с производительностью основных операций, таких как добавление новых данных и поиск других структур данных.
множество:Непрерывный сегмент ячеек памяти используется для хранения данных. Для поиска указанного индекса временная сложность O(1), для поиска по заданному значению необходимо обойти массив и сравнить заданное ключевое слово и элементы массива один за другим, временная сложность O( n) Для порядковых массивов можно использовать бинарный поиск, интерполяционный поиск, поиск Фибоначчи и т. д., чтобы увеличить сложность поиска до O(logn); для общих операций вставки и удаления, которые включают перемещение элементов массива, средняя сложность Также О (п)
Линейный связанный список:Для таких операций, как добавление и удаление связанного списка (после нахождения указанной позиции операции), необходимо только обработать ссылки между узлами, а временная сложность составляет O (1), в то время как операция поиска должна пройти по связанному списку. сравнивать по одному, что сложно. Степень O (n)
Бинарное дерево:Для относительно сбалансированного упорядоченного двоичного дерева средняя сложность операций вставки, поиска и удаления составляет O(logn).
Хеш-таблица:По сравнению с приведенными выше структурами данных, производительность операций добавления, удаления, поиска и других операций в хеш-таблице очень высока.Без учета коллизии хэшей можно выполнить только одно позиционирование, а временная сложность O(1), допустим взгляните, как хеш-таблица достигает удивительного постоянного порядка O (1).
Мы знаем, что существует только две физические структуры хранения структур данных:Последовательная структура хранения и цепная структура хранения(Такие как стеки, очереди, деревья, графы и т.д. абстрагируются от логической структуры и отображаются в память, а эти две формы физической организации), и как мы упоминали выше, найти элемент в массиве по индексу , a позиционирование может быть достигнуто, хеш-таблица использует эту функцию,Основой хеш-таблицы является массив.
Например, если мы хотим добавить или найти элемент, мы можем сопоставить ключевое слово текущего элемента с определенной позицией в массиве с помощью функции и завершить операцию, позиционируя индекс массива один раз.
место хранения = f(ключевое слово)
Среди них эта функция f обычно называется хэш-функцией, и дизайн этой функции напрямую влияет на качество хэш-таблицы. Например, предположим, что мы хотим выполнить операцию вставки в хеш-таблицу:
Операция поиска та же самая, сначала вычисляем фактический адрес хранилища через хэш-функцию, а потом вынимаем его из соответствующего адреса в массиве.
хэш-коллизия
Однако нет ничего идеального, а что, если фактический адрес хранения, полученный хеш-функцией, одинаков для двух разных элементов? То есть, когда мы выполняем хеш-операцию над элементом, получаем адрес хранения, а затем вставляем его, мы обнаруживаем, что он был занят другими элементами.Фактически это так называемая хеш-коллизия, также называемая хеш-коллизия.
Как мы упоминали ранее, дизайн хеш-функции очень важен.Хорошая хеш-функция сделает вычисления максимально простыми, а распределение хеш-адресов будет равномерным., Однако нам нужно четко понимать, что массив представляет собой непрерывное пространство памяти фиксированной длины, какой бы хорошей ни была хеш-функция, она не может гарантировать, что полученный адрес хранения никогда не будет конфликтовать.
Так как же разрешаются хеш-коллизии?Существует много решений для хеш-коллизий: метод открытой адресации (при возникновении конфликта продолжайте искать следующий незанятый адрес хранилища), метод повторной хэш-функции, метод цепного адреса, и HashMap принимает метод цепного адреса, также это способ массив + связанный список,
Во-вторых, принцип реализации HashMap
Основой HashMap является массив Entry. Запись — это основная единица HashMap, и каждая запись содержит пару ключ-значение.
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;Entry — это статический внутренний класс в HashMap. код показывает, как показано ниже
//java冒泡排序示例
public class PaoPaixu {
public static void sort(int[] data){
int tmp;
for (int i = 0; i < data.length; i++) {
for (int j = i+1; j < data.length; j++) {
if(data[i]>data[j]){
data[i]=data[i]+data[j];
data[j]=data[i]-data[j];
data[i]=data[i]-data[j];
}
}
}
}
public static void main(String[] args) {
int data ={5,4,2,1,8,9,4,3} ;
sort(data);
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}Таким образом, общая структура HashMap выглядит следующим образом.
Проще говоря, HashMap состоит из массива + связанного списка. Массив является основной частью HashMap, а связанный список существует в основном для разрешения конфликтов хэшей. Если в расположенном массиве нет связанного списка (следующая запись текущих точек входа в ноль), то для таких операций, как поиск и добавление, к нему нужно обратиться только один раз; если найденный массив содержит связанный список, для операции добавления временная сложность составляет O (n). ; Для операции поиска по-прежнему необходимо пройтись по связанному списку, а затем сравнить и выполнить поиск по одному через метод equals ключевого объекта. Следовательно, с точки зрения производительности, чем меньше связанных списков в HashMap, тем выше производительность.
Несколько других важных полей
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值initialCapacity默认为16，loadFactory默认为0.75我们看下其中一个public HashMap(int initialCapacity, float loadFactor) {
//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}Из приведенного выше кода мы видим, чтоВ обычном конструкторе для таблицы-массива не выделяется место в памяти (за исключением конструктора, входным параметром которого является указанная карта), но фактически массив таблицы создается при выполнении операции размещения.
Хорошо, давайте посмотрим на реализацию операции put.
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);
//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
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++;
//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);
//新增一个entry
return null;
}Давайте посмотрим на метод inflateTable
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);
//capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}Метод inflateTable используется для выделения места в памяти для таблицы магистрального массива. С помощью roundUpToPowerOf2(toSize) он может гарантировать, что емкость больше или равна toSize с точностью до ближайшей второй степени toSize, например toSize=13, тогда вместимость=16;to_size= 16,вместимость=16;to_size=17,вместимость=32.
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}Эта обработка в roundUpToPowerOf2 делает длину массива степенью 2, а Integer.highestOneBit используется для получения значения, представленного крайним левым битом (остальные биты равны 0).
хэш-функция
//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}Значение, рассчитанное приведенной выше хеш-функцией, далее обрабатывается indexFor для получения фактического места хранения.
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}h&(length-1) гарантирует, что полученный индекс должен быть в пределах диапазона массива.Например, емкость по умолчанию 16, length-1=15, h=18, а преобразование в двоичный файл рассчитывается как
1 0 0 1 0
& 0 1 1 1 1
__________________
0 0 0 1 0 = 2Окончательный расчетный индекс=2. Некоторые версии будут использовать для вычисления здесь операцию по модулю, что также может гарантировать, что индекс должен быть в пределах диапазона массива, но битовая операция имеет более высокую производительность для компьютера (в HashMap большое количество битовых операций)
Итак, процесс определения конечного места хранения выглядит следующим образом:
Давайте посмотрим на реализацию addEntry:
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}Из вышеприведенного кода видно, что когда возникает конфликт хэшей и размер больше порогового, массив необходимо расширить, при расширении необходимо создать новый массив с длиной в два раза больше предыдущего массива, а затем добавляются элементы в текущий массив Entry.После того, как все они переданы, длина нового массива после расширения в два раза больше, чем раньше, поэтому расширение является относительно ресурсоемкой операцией.
3. Почему длина массива HashMap должна быть степенью двойки?
Продолжим рассмотрение упомянутого выше метода изменения размера.
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);
}Если массив расширяется, длина массива меняется, а индекс места хранения = h&(length-1), индекс тоже может меняться, и индекс нужно пересчитывать.Для начала рассмотрим метод передачи.
void transfer(Entry[] newTable, Boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
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);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}Этот метод последовательно проходит данные в старом массиве и выбрасывает их в новый расширенный массив.Вычисление позиции индекса нашего массива выполняется путем хеширования хэш-кода значения ключа, а затем по длине-1. операции получают конечную позицию индекса массива.
Длина массива hashMap должна быть равна степени 2. Например, двоичное представление 16 равно 10000, тогда длина 1 равна 15, а двоичное представление равно 01111. Аналогично, длина развернутого массива равна 32, двоичное представление равно 100000, а длина-1 равна 31. , что равно 011111 в двоичном формате.
Из рисунка ниже мы также можем видеть, что это гарантирует, что все младшие биты равны 1, и есть только одно отличие после расширения, то есть добавляется самая левая 1, так что при передаче h&(length-1) , до тех пор, пока h Соответствующий крайний левый бит разницы равен 0, что может гарантировать, что полученный новый индекс массива согласуется со старым индексом массива (значительно уменьшает перемещение позиции данных старого массива, который был хеширован задолго до этого), личное понимание .
Кроме того, длина массива остается степенью 2, а младшие биты длины-1 все равны 1, что сделает индекс индекса полученного массива более однородным, например:
Мы видим, что в приведенной выше операции & старшие биты не повлияют на результат (хэш-функция может также использовать различные битовые операции, чтобы сделать младшие биты более хэшируемыми), мы обращаем внимание только на младшие биты, если младшие биты все 1, то для младшей части h любое изменение одного бита повлияет на результат, то есть для получения места хранения index=21 младший бит h имеет только эту комбинацию. По этой же причине длина массива должна быть степенью двойки.
Если это не степень 2, то есть младшие биты не все равны 1. В это время, чтобы сделать index=21, младшая часть h больше не является уникальной, и вероятность коллизии хэшей станет При этом индекс, соответствующий этому биту, все равно не будет равен 1, и соответствующие позиции массива будут потеряны.
получить метод
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}Метод get возвращает соответствующее значение через значение ключа. Если ключ имеет значение null, перейдите непосредственно к таблице [0], чтобы получить его. Давайте еще раз посмотрим на метод getEntry.
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
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;
}Видно, что реализация метода get относительно проста, key(hashcode)-->hash-->indexFor-->final index position, найти соответствующую позицию table[i], а затем проверить, есть ли связанный список, просмотреть связанный список и передать ключ. Метод equals сравнивает и находит соответствующие записи. Следует отметить, что некоторые считают, что при переходе по связанному списку после определения позиции в массиве оценка e.hash == hash не требуется, и можно использовать только оценку равенства.
На самом деле это не так, только представьте, если входящий ключевой объект переписывает метод equals, но не переписывает hashCode, и объект оказывается в этой позиции массива, если только equals используется для оценки того, может ли он быть равным, но его хэш-код несовместим с текущим объектом, в этом случае, согласно соглашению хэш-кода объекта, текущий объект не может быть возвращен, а должен быть возвращен нуль, что будет подробнее объяснено в следующем примере.
В-четвертых, переписывание метода equals требует одновременного переписывания метода hashCode.
Анализ исходного кода HashMap представлен здесь. Наконец, давайте поговорим об общей проблеме, которая будет упоминаться в различных материалах: «При переписывании equals вы также должны одновременно покрывать хэш-код». , Что произойдет, если вы переопределите равенство без переопределения хэш-кода
/**
* Created by chengxiao on 2016/11/15.
*/
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public Boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值，通过idCard来确定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出，从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
}
}Фактический результат:
结果：nullЕсли у нас уже есть определенное понимание принципа HashMap, этот результат понять несложно. Хотя используемые нами ключи логически эквивалентны (по сравнению с равными), когда мы выполняем операции получения и помещения, поскольку метод hashCode не перезаписывается, при выполнении операций помещения ключ(хэшкод1)-- >хэш-->индексФор-->конечный индекс позиция, а когда значение извлекается с помощью ключа key(hashcode1) --> хэш --> indexFor --> конечная позиция индекса, поскольку хэш-код1 не равен хэш-коду2, никто не находится в позиции массива и возвращает логически неверное значение null (также может случиться так, что будет обнаружена позиция в массиве, но также будет определено, равно ли хэш-значение ее записи, как упоминалось в методе get выше.)
Следовательно, при перезаписи равен методу, вы должны обратить внимание на переопределение метода HASHCODE, но также убедитесь, что метод HASHCODE должен вернуть одно и то же целое значение на два объекта, которые определяют равных. И если равна судит два объекта, которые неравны, его хэшкод может быть одинаковым (просто имеет хэш-конфликт, должен пытаться избежать).
V. Резюме
В этой статье описывается принцип реализации HashMap, а также проводится его дальнейший анализ в сочетании с исходным кодом. В ней также рассматриваются некоторые конструктивные особенности деталей исходного кода. Наконец, в ней кратко рассказывается, почему необходимо переписать метод hashCode при переписывании equals. . Я надеюсь, что эта статья может помочь всем, и добро пожаловать на обсуждение и исправление, спасибо за вашу поддержку!
Источник: cnblogs.com/chengxiao/p/6059914.htm
Благодарим за прочтение всей статьи. Чтобы узнать больше технических статей и задать вопросы для интервью от крупных производителей, вы можете подписаться на общедоступный аккаунт WeChat: место сбора Java-программистов.