目录
`MyHashMap` 是一个简单的哈希表实现，用于存储键值对。为了更好地理解其实现原理，以下是对代码的详细解释：
基本结构
- DEFAULT_CAPACITY: 默认的哈希表容量，为 16。
- LOAD_FACTOR: 负载因子，为 0.75。当哈希表中的元素数量超过容量的 75% 时，哈希表会自动扩容。
- size: 当前哈希表中存储的元素数量。
- table: 一个 `Object` 数组，用于存储键值对。
主要方法
`put(K key, V value)`
- 功能: 将键值对插入哈希表。
- 步骤:
1. 检查是否需要扩容：如果当前元素数量 `size` 超过了当前容量乘以负载因子，则调用 `resize` 方法进行扩容。
2. 计算键的哈希值，并通过 `getIndex` 方法将其映射到数组中的一个索引位置。
3. 将值存储到该索引位置，并增加 `size`。
`get(K key)`
- 功能: 根据键获取对应的值。
- 步骤:
1. 计算键的哈希值，并通过 `getIndex` 方法将其映射到数组中的一个索引位置。
2. 返回该索引位置的值。
`remove(K key)`
- 功能: 根据键删除对应的值。
- 步骤:
1. 计算键的哈希值，并通过 `getIndex` 方法将其映射到数组中的一个索引位置。
2. 如果该索引位置有值，则将该位置置为 `null`，并减少 `size`。
`containsKey(K key)`
- 功能: 检查哈希表中是否包含指定的键。
- 步骤:
1. 计算键的哈希值，并通过 `getIndex` 方法将其映射到数组中的一个索引位置。
2. 返回该索引位置是否有值。
辅助方法
`getIndex(K key)`
- 功能: 计算键的哈希值，并将其映射到数组中的一个索引位置。
- 步骤:
1. 获取键的哈希码。
2. 使用 `Math.abs` 方法取哈希码的绝对值，以避免负数索引。
3. 对哈希码取模，得到数组中的索引位置。
`resize(int newCapacity)`
- 功能: 扩容哈希表。
- 步骤:
1. 创建一个新的数组 `newTable`，其容量为当前容量的两倍。
2. 遍历旧数组 `table`，将非空的元素重新哈希并存储到新数组中。
3. 将 `table` 指向新数组 `newTable`。
存在的问题
- 冲突处理: 当前实现没有处理哈希冲突，即在同一个索引位置只能存储一个值。实际上，哈希表通常会使用链表或红黑树来处理冲突。
- 类型安全: 在 `resize` 方法中，假设值的类型为键的类型，这在实际应用中是不安全的。
`MyHashMap` 是一个简单的哈希表实现，使用了基本的哈希函数和数组来存储键值对。它支持插入、获取、删除和检查键是否存在等操作，并且在元素数量超过负载因子时会自动扩容。然而，该实现没有处理哈希冲突，因此在实际应用中可能需要进一步改进。
接着前面介绍的map，实现一个基于模运算取余的最简单的HashMap
public class MyHashMap<K, V> implements MyMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
private int size = 0;
private Object[] table = new Object[DEFAULT_CAPACITY];
@Override
public void put(K key, V value) {
// 检查是否需要扩容
if (size >= table.length * LOAD_FACTOR) {
resize(table.length * 2);
}
int index = getIndex(key);
table[index] = value;
size++;
}
@Override
public V get(K key) {
int index = getIndex(key);
return (V) table[index];
}
@Override
public boolean remove(K key) {
if (key == null) {
return false;
} else {
int index = getIndex(key);
if (table[index] != null) {
table[index] = null;
size--;
return true;
} else {
return false;
}
}
}
@Override
public boolean containsKey(K key) {
int index = getIndex(key);
return table[index] != null;
}
private int getIndex(K key) {
int hashCode = key.hashCode();
return Math.abs(hashCode) % table.length; // 使用绝对值避免负索引
}
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
Object[] newTable = new Object[newCapacity];
// 重新哈希所有现有元素
for (Object value : table) {
if (value != null) {
K key = (K) value; // 假定值类型为键类型（仅适用于简单场景）
int newIndex = getIndex(key);
newTable[newIndex] = value;
}
}
table = newTable;
}
}测试：
public class Test {
public static void main(String[] args) {
MyMap<String, Integer> map = new MyHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map.get("a"));
System.out.println(map.get("b"));
map.put("a", 4);
System.out.println(map.get("a"));
System.out.println(map.remove("a"));
System.out.println(map.get("a"));
System.out.println(map.containsKey("a"));
System.out.println(map.containsKey("b"));
}
}结果：
1
2
4
true
null
false
true