某大厂一面：HashMap 的put方法具体做了哪些操作

HashMap 的 put 方法是一个常用的操作，它将一个键值对插入到哈希表中。下面是 put 方法执行的详细流程，包括各个步骤的解释，并附上相应的代码片段。

1. 检查键是否为 null

如果传入的键为 null，HashMap 会特别处理这种情况，因为 null 是允许作为键的，但是它会在特殊位置（通常是数组的第一个位置）存储。

if (key == null) {return putForNullKey(value);
}

2. 计算哈希值

对于非 null 的键，HashMap 会首先计算出该键的哈希值。哈希值的计算是通过调用键的 hashCode() 方法，再经过一定的扰动处理，以减少哈希冲突。

int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);

这里的 hash() 是一个方法，用于对键的哈希值进行扰动，indexFor() 方法则用来根据计算出的哈希值找到数组中的位置。

3. 查找位置

接下来，HashMap 会根据计算出的索引（index）来查找对应的桶（数组位置）。如果该位置已经存在元素，则会检查该位置的链表或红黑树结构，查看是否已经存在相同的键。

for (Entry<K,V> e = table[index]; e != null; e = e.next) {K k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;return oldValue;}
}

4. 插入新元素

如果在相应位置没有找到相同的键，HashMap 会将新的键值对插入到桶中。如果该位置为空，直接插入该元素。如果该位置已经存在链表或红黑树，则会把新元素加入到链表头部或树中。

createEntry(hash, key, value, index);

5. 扩容

HashMap 会根据当前的负载因子（默认是 0.75）来判断是否需要扩容。如果当前元素数量超出了负载因子的限制，HashMap 会进行扩容操作，这会重新计算每个元素的位置，并将元素重新插入到新的数组中。

if (size > threshold)resize();

完整代码示例

public V put(K key, V value) {if (key == null) {return putForNullKey(value);}int hash = hash(key.hashCode());int index = indexFor(hash, table.length);for (Entry<K,V> e = table[index]; e != null; e = e.next) {K k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;return oldValue;}}createEntry(hash, key, value, index);if (size++ >= threshold) {resize();}return null;
}private int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}private int indexFor(int hash, int length) {return hash & (length - 1);
}private void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);
}private void resize() {// 扩容的具体实现
}

关键点总结：

1. 哈希值计算：使用 hashCode 和扰动函数来减少冲突。
2. 桶的查找：通过数组索引查找对应位置，如果发生冲突，使用链表或红黑树来存储多个元素。
3. 元素插入：如果该位置没有找到相同的键，插入新元素。
4. 扩容机制：当负载因子达到一定比例时，HashMap 会扩展数组并重新散列元素。

这个过程对于每次调用 put 都是会依次执行的，确保 HashMap 的高效插入与查询操作。