Существует три основных системы коллекций Java - List, Set, Map и Set реализованы на основе Map.В Map HashMap является широко используемым классом и частым гостем в интервью.Я помню, что раньше был ответ на интервью, HashMap это структура данных хеширования связанного списка, его емкость равна 16, а коэффициент загрузки равен 0,75. Когда он больше, чем емкость * коэффициент загрузки, емкость будет удвоена. Операция put заключается в выполнении вычисления хеш-кода для хэш-кода значение ключа. Метод equals ключа находит пару ключ-значение для замены и возвращает старые данные. Если не найдено, то будет вставлено в связанный список, поток HashMap небезопасен. Когда интервьюер слышит эти, первый вопрос почему емкость 16, 15, 14? Зачем удваивать мощность? Почему HashMap рекомендует использовать Key для неизменяемых объектов? В то время я недостаточно глубоко думал, и я уже был взволнован, прежде чем спросил о ConcurrentHashMap... Теперь позвольте мне рассказать о моих взглядах на HashMap.
Краткое описание HashMap
отношения наследования
Давайте посмотрим на отношения наследования HashMap:
① Добавлено объявление интерфейса Map, чтобы метод getInterfaces класса Class мог напрямую получить интерфейс Map
②.ошибка является ошибкой
③ Оптимизирован для инструмента генерации документов API Java для создания более точных типов документов.
Структура данных HashMap
Давайте посмотрим, какие атрибуты есть в Entry.В 1.8 Entry переименовали в Node, а атрибуты остались без изменений.После изменений 1.8 поговорим о 1.7.
static class Entry implements Map.Entry {
/** 贱对象*/
final K key;
/** 值对象*/
V value;
/** 指向下一个Entry对象*/
Entry next;
/** 键对象哈希值*/
int hash;
}
1.7 Анализ исходного кода HashMap
Ключевые свойства HashMap
/**
* 默认初始容量16——必须是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* HashMap存储的键值对数量
*/
transient int size;
/**
* 默认负载因子0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 扩容阈值，当size大于等于其值，会执行resize操作
* 一般情况下threshold=capacity*loadFactor
*/
int threshold;
/**
* Entry数组
*/
transient Entry[] table = (Entry[]) EMPTY_TABLE;
/**
* 记录HashMap修改次数，fail-fast机制
*/
transient int modCount;
/**
* hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算
* hashSeed是一个与实例相关的随机值，用于解决hash冲突
* 如果为0则禁用备用哈希算法
*/
transient int hashSeed = 0;
Конструктор HashMap
/**
* 指定容量及负载因子构造方法
*/
public HashMap(int initialCapacity, float loadFactor) {
//校验初始容量
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;
//空方法，让其子类重写例如LinkedHashMap
init();
}
/**
* 默认构造方法，采用默认容量16，默认负载因子0.75
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 指定容量构造方法，负载因子默认0.75
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Из этих трех методов построения мы можем обнаружить, что, хотя указан начальный размер емкости, таблица в это время все еще пуста, это пустой массив, а порог расширения - начальная емкость.Перед операцией размещения массив будет быть создан.
/**
* 根据已有Map构造新HashMap的构造方法
* 初始容量:参数map大小除以默认负载因子+1与默认容量的最大值
* 初始负载因子:默认负载因子0.75
*/
public HashMap(Map m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
//把传入的map里的所有元素放入当前已构造的HashMap中
putAllForCreate(m);
}
Этот метод построения заключается в вызове метода inflateTable перед операцией размещения. Раздувание означает расширение. Давайте посмотрим на этот метод. Обратите внимание, что пороговое значение расширения порога в это время является начальной емкостью.
private void inflateTable(int toSize) {
//返回不小于number的最小的2的幂数，最大为MAXIMUM_CAPACITY
int capacity = roundUpToPowerOf2(toSize);
//设置扩容阈值，值为容量*负载因子与最大容量+1的较小值
threshold = (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY + 1);
//创建数组
table = new Entry[capacity];
//初始化HashSeed值
initHashSeedAsNeeded(capacity);
}
/**
* 返回不小于number的最小的2的幂数，最大为MAXIMUM_CAPACITY
*/
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
/**
* 若number不小于最大容量则为最大容量
* 若number小于最大容量大于1，则为不小于number的最小的2的幂数
* 若都不是则为1
*/
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
Отсюда мы можем перейти к HashMap, чтобы создать массив со степенью двойки, так почему же он должен быть разработан таким образом? Я представлю его позже.
положить метод
Самое большее, что я вызываю для добавления элементов в HashMap, — это метод put
public V put(K key, V value)
Давайте посмотрим на его реализацию кода:
public V put(K key, V value) {
//若数组为空时创建数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//若key为null
if (key == null)
return putForNullKey(value);
//对key进行hash计算，获取hash值
int hash = hash(key);
//根据刚得到的hash值与数组长度计算桶位置
int i = indexFor(hash, table.length);
//遍历桶中链表
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//key值与hash值都相同的话进行替换
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//空方法，让其子类重写例如LinkedHashMap
e.recordAccess(this);
//返回旧值
return oldValue;
}
}
//记录修改
modCount++;
//链表中不存在此键，则调用addEntry方法向链表中添加新结点
addEntry(hash, key, value, i);
return null;
}
Из приведенного выше исходного кода мы видим:
① HashMap сначала определяет, пуст ли массив, если это кондиционер, используйте inflateTable для расширения.
② Затем оцените, является ли ключ нулевым, если он нулевой, вызовите метод putForNullKey, чтобы поставить.Таким образом, HashMap позволяет ключу быть нулевым.
③ Снова выполните вычисление хеш-функции для ключа, и полученное значение хэш-функции и текущая длина массива будут рассчитаны для получения индекса в массиве.
④ Затем пройдите по связанному списку по индексу массива, если хэш ключа совпадает с хэшем входящего ключа, а равенство ключа возвращается к истинному, а затем напрямую перезаписывает значение
⑤ Наконец, если он не существует, создайте новый узел в этом связанном списке.
Пошаговое введение (первый шаг не упоминается выше), второй шаг — это метод putForNullKey, из которого мы можем узнать, что если ключ равен нулю, он сначала пройдет по связанному списку из корзины с 0-й позицией, и если ключ узла найден, заменить, если он равен нулю, и добавить узел, если он не существует. AddEntry в методе будет объяснено позже.
private V putForNullKey(V value) {
//遍历0位置桶上的链表，若存在结点Entry的key为null替换value，返回旧值
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//若不存在，0位置桶上的链表中添加新结点
addEntry(0, null, value, 0);
return null;
}
На третьем шаге сначала просмотрите хэш-алгоритм HashMap, получите хэш-значение ключевого объекта и примените дополнительную хэш-функцию к хэш-результату объекта, чтобы предотвратить хеш-функции низкого качества.Примечание: пустые ключи всегда сопоставляются с хэши 0, поэтому индекс равен 0, оптимизирован метод хеширования 1.8,
final int hash(Object k) {
// 当h不为0且键对象类型为String用此算法，1.8已删除
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//此函数确保在每个比特位置上仅以恒定倍数不同的hashCode具有有限的碰撞数量（在默认负载因子下约为8）
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Рассчитайте позицию ковша на основе вычисленного значения и длины массива:
static int indexFor(int h, int length) {
return h & (length-1);
}
Этот метод выполняет операцию по модулю длины массива, а доступ к полученному остатку осуществляется из следующей таблицы.Затем, поскольку это операция по модулю, почему бы не использовать h%length напрямую, потому что ее эффективность очень низка, поэтому бит Из этого мы можем видеть, что предполагаемая длина It равна 16. Когда наш h равен 1 и 17, мы вычисляем, что индекс ведра равен 1. Эта ситуация называется конфликтом (k1≠k2, и f( k1)=f(k2)).При возникновении конфликта HashMap использует метод цепных адресов (метод соединения всех синонимов в односвязный список) для разрешения конфликтов.
Далее предположим, что когда длины равны 16, 15 и 14 соответственно, их времена столкновения:
| length = 16 | length = 15 | length = 14 | ||||||
| h | h&length-1 | результат | h&length-1 | результат | h&length-1 | результат | ||
| 0 | 0000 & 1111 | 0000 | 0 | 0000 & 1110 | 0000 | 0000 & 1101 | 0000 | |
| 1 | 0001 & 1111 | 0001 | 1 | 0001 & 1110 | 0000 | 0001 & 1101 | 0001 | |
| 2 | 0010 & 1111 | 0010 | 2 | 0010 & 1110 | 0010 | 0010 & 1101 | 0000 | |
| 3 | 0011 & 1111 | 0011 | 3 | 0011 & 1110 | 0010 | 0011 & 1101 | 0001 | |
| 4 | 0100 & 1111 | 0100 | 4 | 0100 & 1110 | 0100 | 0100 & 1101 | 0100 | |
| 5 | 0101 & 1111 | 0101 | 5 | 0101 & 1110 | 0100 | 0101 & 1101 | 0101 | |
| 6 | 0110 & 1111 | 0110 | 6 | 0110 & 1110 | 0110 | 0110 & 1101 | 0100 | |
| 7 | 0111 & 1111 | 0111 | 7 | 0111 & 1110 | 0110 | 0111 & 1101 | 0101 | |
| 8 | 1000 & 1111 | 1000 | 8 | 1000 & 1110 | 1000 | 1000 & 1101 | 1000 | |
| 9 | 1001 & 1111 | 1001 | 9 | 1001 & 1110 | 1000 | 1001 & 1101 | 1001 | |
| 10 | 1010 & 1111 | 1010 | 10 | 1010 & 1110 | 1010 | 1010 & 1101 | 1000 | |
| 11 | 1011 & 1111 | 1011 | 11 | 1011 & 1110 | 1010 | 1011 & 1101 | 1001 | |
| 12 | 1100 & 1111 | 1100 | 12 | 1100 & 1110 | 1100 | 1100 & 1101 | 1100 | |
| 13 | 1101 & 1111 | 1101 | 13 | 1101 & 1110 | 1100 | 1101 & 1101 | 1101 | |
| 14 | 1110 & 1111 | 1110 | 14 | 1110 & 1110 | 1110 | 1110 & 1101 | 1100 | |
| 15 | 1111 & 1111 | 1111 | 15 | 1111 & 1110 | 1110 | 1111 & 1101 | 1101 | |
| 0 конфликтов | 8 конфликтов | 8 конфликтов | ||||||
Так почему же начальная емкость должна быть 16 вместо 8 или 32? Я думаю, что если будет 8, то порог расширения 6, а если не поставить несколько, то расширится, а если 32, то столько не поставишь, а ресурсы зря.
На четвертом шаге, если хэш ключа совпадает с хэшем входящего ключа, а равенству ключа возвращается значение true, то значение хеш-функции, которое непосредственно перезаписывает value.key, вычисляется на основе его хэш-кода. значение, то когда мы используем доступное. Когда объект изменен, его значение хэш-кода может легко измениться, поэтому возникает риск того, что исходное значение не может быть найдено, поэтому HashMap рекомендует использовать неизменяемые объекты в качестве ключей.
Последний шаг метода addEntry создает новый узел, код выглядит следующим образом
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前hashmap中的键值对数量超过扩容阈值，进行2倍扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//2倍扩容
resize(2 * table.length);
//扩容后，桶的数量增加了，重新对键进行哈希码的计算
hash = (null != key) ? hash(key) : 0;
//根据键的新哈希码和新的桶数量重新计算桶索引值
bucketIndex = indexFor(hash, table.length);
}
//创建结点
createEntry(hash, key, value, bucketIndex);
}
/**
* 头插结点
* 将原本在数组中存放的链表头置入到新的Entry之后，将新的Entry放入数组中
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Давайте не будем сначала рассматривать ситуацию с расширением.Когда расширение не требуется, хэш-карта использует метод вставки головы для вставки узлов.Почему нам нужна вставка головы вместо вставки хвоста, потому что данные, вставленные позже, используются чаще, а по отдельности доступ к связному списку невозможен только случайным образом Запрос просматривается с самого начала, поэтому используется вставка в начало Внезапно возникает вопрос, почему бы не использовать линейный метод исследования в виде двумерного массива для решения конфликтов. конец массива тоже O(1), но самый большой недостаток массива в том, что если его не вставить в конец, эффективность очень низкая, а во-вторых, если добавляемые данные распределены равномерно, то массив на каждое ведро должно резервировать память.
Давайте посмотрим на расширение:
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];
//将旧Entry数组转移到新Entry数组中去
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//重新设置扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Метод Transfer просматривает все Entry старого массива, пересчитывает заголовки индекса один за другим в соответствии с новой емкостью и сохраняет их в новом массиве, который довольно проблематично расширять, поэтому, если мы знаем, сколько данных нам нужно добавить , лучше указать инициализацию емкости.
/**
* 将旧Entry数组转移到新Entry数组中去
*/
void transfer(Entry[] newTable, boolean rehash) {
//获取新数组的长度
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry 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;
}
}
}
Здесь может появиться круговой связанный список, ведущий к бесконечному циклу Предположим, что емкость равна 4, коэффициент загрузки по умолчанию равен 0,75, а порог расширения равен 3. Текущее хранилище HashMap выглядит следующим образом:
Предполагая, что два потока хотят добавить данные в этот HashMap одновременно, при расширении емкости Thread1 готовится к обработке Entry1, после выполнения Entry
Thread2 завершает выполнение метода передачи
Вставьте Entry1 в новый массив, а затем e будет Entry2.Когда наступает очередь следующего цикла, next становится Entry1 из-за работы Thread2.
Кроме того, это напоминает мне классическую инверсию связанного списка вопросов на собеседовании, и я сам это понял.
public class Node {
private Node next;
private Object item;
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
public static Node get(){
Node last = new Node(6, null);
Node fifth = new Node(5,last);
Node fourth = new Node(4, fifth);
Node third = new Node(3, fourth);
Node second = new Node(2, third);
Node first = new Node(1, second);
return first;
}
public static void outPut(Node node){
while(node != null){
System.out.print(node.item);
node = node.next;
}
}
public static Node reverse(Node node){
Node newNode = node;
Node temp = null;
while (node != null && node.next != null){
Node next = node.next;
node.next = temp;
temp = node;
newNode = new Node(next.item, node);
node = next;
}
return newNode;
}
public static void main(String[] args) {
Node first = get();//获取单链表头结点
outPut(first);//输出整条链表数据
first = reverse(first);
outPut(first);
}
}
получить метод
Зная принцип put, понять операцию get несложно.Для начала посмотрим на код:
/**
* 返回到指定键所映射的值，若不存在返回null
*/
public V get(Object key) {
//与put一样单独处理
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
Как и при хранении нулевого ключа, получите его из корзины в позиции 0.
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
getEntry
final Entry getEntry(Object key) {
//size为0，即hashmap为空，返回null
if (size == 0) {
return null;
}
//对key进行hash计算，获取hash值
int hash = (key == null) ? 0 : hash(key);
//根据hash值与数组长度获取桶位置，遍历对应桶上链表
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//key值与hash值都相同的话返回结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
//若不存在返回null
return null;
}
резюме
Эта статья в основном вращается вокруг исходного кода java7HashMap, чтобы объяснить его принцип и подвести итоги:
①Поскольку операция размещения обрабатывает сценарий, в котором ключ равен нулю, HashMap допускает использование нуля в качестве ключа.
②Поскольку HashMap выполняет вычисление хеш-функции в соответствии со значением хэш-кода ключа при вычислении индекса корзины для получения хеш-значения и выполняет операцию И с массивом длиной 1. Все двоичные биты длины-1 равны 1, что может быть равномерно распределяется во избежание конфликтов, поэтому емкость HashMap должна быть равна степени 2
③Поскольку операция HashMap будет выполнять вычисление хеш-функции вокруг хэш-кода ключа, а хэш-код изменяемых объектов легко изменить, HashMap рекомендует использовать неизменяемые объекты в качестве ключей.
④Поточно-небезопасный метод расширения HashMap может привести к бесконечному циклу кругового связанного списка, поэтому, если вам нужно работать в многопоточном сценарии, вы можете использовать ConcurrentHashMap.
⑤ Когда возникает конфликт, HashMap использует метод цепочки адресов (метод zipper) для разрешения конфликта, а затем получает Entry, соответствующую ключу, в соответствии с хэшем ключа и методом equals.
⑥ Почему начальная емкость HashMap установлена на 16, я думаю, если она будет 8, порог расширения будет равен 6, а если поставить несколько, емкость будет расширена, а если 32, то не будет размещена так много, пустая трата ресурсов
Ссылаться на
https://coolshell.cn/articles/9606.html
http://www.cnblogs.com/chenssy/p/3521565.html