【Java】HashMap知识点总结，这一篇算是总结的不错的了，建议看看！

HashMap存储结构

内部包含了⼀个 Entry 类型的数组 Entry[] table。transient Entry[] table;(transient:表示不能被序列化)Entry类型存储着键值对。它包含了四个字段， Entry 是⼀个链表。即数组中的每个位置被当成⼀个桶，⼀个桶存放⼀个Entry链表。HashMap 使⽤拉链法来解决冲突，同⼀个链表中存放哈希值和散列桶取模运算结果相同的 Entry。
【Java】HashMap知识点总结，这一篇算是总结的不错的了，建议看看！

常规操作

  • 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 时会将链表转换为红⿊树。

参数含义
capacitytable 的容量⼤⼩，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次⽅。
size键值对数量。
thresholdsize 的临界值，当 size ⼤于等于 threshold 就必须进⾏扩容操作。
loadFactor装载因⼦，table 能够使⽤的⽐例，threshold = (int)(capacity* loadFactor)。

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核心知识点总结！

以上是 【Java】HashMap知识点总结，这一篇算是总结的不错的了，建议看看！ 的全部内容， 来源链接： utcz.com/a/89511.html

回到顶部