关于java:HashMap知识点总结这一篇算是总结的不错的了建议看看

HashMap 存储构造

外部蕴含了⼀个 Entry 类型的数组 Entry[] table。transient Entry[] table;(transient: 示意不能被序列化)Entry 类型存储着键值对。它蕴含了四个字段，Entry 是⼀个链表。即数组中的每个地位被当成⼀个桶，⼀个桶寄存⼀个 Entry 链表。HashMap 使⽤拉链法来解决抵触，同⼀个链表中寄存哈希值和散列桶取模运算后果雷同的 Entry。

惯例操作

• final K getKey();
• final V getValue()；
• final V setValue(V newValue);
• final boolean equals(Object o);
• final int hashCode();
• final String toString();

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;
 Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n;
 key = k;
 hash = h;
2. 拉链法的⼯作原理
 }
 public final K getKey() {return key;}
 public final V getValue() {return value;}
 public final V setValue(V newValue) {
 V oldValue = value;
 value = newValue;
 return oldValue;
 }
 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;
 }
 public final int hashCode() {return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 }
 public final String toString() {return getKey() + "=" + getValue();}
}

插入 put 操作

• 插入数组是对 hash 值与散列表应用除留余数的办法计算失去对应桶序号；
• 插入时采纳链表的头插法进行插入;
• HashMap 容许插⼊键为 null 的键值对。然而因为 null 的 hashCode() ⽅法，也就⽆法确定该键值对应桶下标，只能通过强制指定第 0 个桶寄存键为 null 的键值对；

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);
 }
 // 键为 null 独自解决
 if (key == null)
 return putForNullKey(value);
 int hash = hash(key);
 // 确定桶下标
 int i = indexFor(hash, table.length);
 // 先找出是否曾经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
 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; }

private V putForNullKey(V value) {for (Entry<K,V> 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++;
 addEntry(0, null, value, 0);
 return null; }

void addEntry(int hash, K key, V value, int bucketIndex) {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);
}
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++; }

扩容

设 HashMap 的 table ⻓度为 M，须要存储的键值对数量为 N，如果哈希函数满⾜平均性的要求，那么每条链表的⻓度⼤约为 N/M，因而查找的复杂度为 O(N/M)。为了让查找的老本升高，应该使 N/M 尽可能⼩，因而须要保障 M 尽可能⼤，也就是说 table 要尽可能⼤。

• HashMap 采⽤动静扩容来依据以后的键值对数量来调整数组长度，使得空间效率和工夫效率都能失去保障。(HashMap 扩容并不是等到数组满了才扩容，因为元素是插入到链表中，永远也不会满，所以有一个阈值–threshold，当等于它时就进行扩容操作)
• capacity 个别为 2 的 n 次方，即便用户传入的不是 2 的 n 次方，它也能够⾃动地将传⼊的容量转换为 2 的 n 次⽅。起因是除留余数取模时采纳的是位运算来代替取模运算，可能极⼤升高从新计算桶下标操作的复杂度。(位运算只用于 2 进制，所以须要 2 的 n 次方)；
• 当须要扩容时，使⽤ resize() 实现，令 capacity 为原来的两倍，扩容操作须要把 oldTable 的所有键值对从新插入 newTable 中，因而这⼀步是很费时的。
• 当⼀个桶存储的链表⻓度⼤于等于 8 时会将链表转换为红⿊树。

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 if (size++ >= threshold)
 resize(2 * table.length);
}

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);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];
 if (e != null) {src[j] = null;
 do {
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 } while (e != null);
 }
 }
}

与 Hashtable 的⽐较 **

Hashtable 使⽤ synchronized 来进⾏同步。
HashMap 能够插⼊键为 null 的 Entry。
HashMap 的迭代器是 fail-fast 迭代器。
HashMap 不能保障随着工夫的推移 Map 中的元素秩序是不变的。

总结

欢送关注公众号：前程有光，支付一线大厂 Java 面试题总结 + 各知识点学习思维导 + 一份 300 页 pdf 文档的 Java 外围知识点总结！