数据结构与算法面试题：实现一个哈希表，并考虑哈希冲突的解决方案。
简介：实现一个哈希表，并考虑哈希冲突的解决方案。
算法思路
哈希表（Hash Table，也叫散列表）是一种有着很快插入和查找速度的数据结构，适用于一些需要快速查找、插入数据的应用场合。哈希冲突常用的解决方法包括线性探测与链地址法。
- 线性探测：当发生哈希冲突时，将待插入元素放到下一个空闲槽中，如果下一个位置已经被占用，则依次向后查找，直到找到第一个空闲槽为止。
- 链地址法：当发生哈希冲突时，将该位置上之前的元素都存在一个链表中，插入新元素时将其加入链表尾部即可。
以下是使用C++实现哈希表的代码，并附有详细注释：
#include <iostream> #include <vector> using namespace std; // 哈希表节点 struct Node { int key; int val; Node* next; Node(int k, int v) : key(k), val(v), next(nullptr) {} }; class MyHashMap { private: vector<Node*> data; // 存储哈希表节点的数据数组 int size; // 当前数据个数 int cap; // 数组容量 double loadFactor; // 负载因子 // 获取某个数字的哈希值 int hashCode(int key) { return key % cap; } public: // 构造函数 MyHashMap() : size(0), cap(1000) { data.resize(cap, nullptr); loadFactor = 0.75; } // 插入或更新数据 void put(int key, int value) { int idx = hashCode(key); // 获取插入位置的哈希值 // 检测是否已有该元素 Node* node = data[idx]; while (node != nullptr) { if (node->key == key) { node->val = value; return; } node = node->next; } // 如果容量满了，进行扩容 if (size >= loadFactor * cap) { vector<Node*> old_data = data; cap *= 2; data.clear(); data.resize(cap, nullptr); size = 0; for (int i = 0; i < old_data.size(); ++i) { Node* node = old_data[i]; while (node != nullptr) { put(node->key, node->val); node = node->next; } } } // 在指定位置插入新元素 Node* new_node = new Node(key, value); new_node->next = data[idx]; data[idx] = new_node; ++size; } // 获取某个键对应的值，不存在则返回-1 int get(int key) { int idx = hashCode(key); Node* node = data[idx]; while (node != nullptr) { if (node->key == key) { return node->val; } node = node->next; } return -1; } // 删除某个元素 void remove(int key) { int idx = hashCode(key); Node* node = data[idx]; if (node == nullptr) return; // 特殊处理头节点的情况 if (node->key == key) { data[idx] = node->next; delete node; --size; return; } // 删除中间或尾部位置上的元素 while (node->next != nullptr) { if (node->next->key == key) { Node* del_node = node->next; node->next = del_node->next; delete del_node; --size; return; } node = node->next; } } }; int main() { MyHashMap myHashMap; myHashMap.put(1, 1); myHashMap.put(2, 2); cout << myHashMap.get(1) << endl; // 1 cout << myHashMap.get(3) << endl; // -1 myHashMap.put(2, 1); cout << myHashMap.get(2) << endl; // 1 myHashMap.remove(2); cout << myHashMap.get(2) << endl; // -1 return 0; }
这个实现使用一个vector<Node*>数组来存储哈希表中的节点，其中Node是链表节点的结构体。在哈希表的构造函数中，我们设置了默认容量为1000，并将数组大小初始化为该值。此外，还指定了一个负载因子loadFactor，一旦当前数据总数达到容量和负载因子的乘积，就需要进行扩容操作。
hashCode()函数用于获取某个键对应的哈希值。在执行插入时，我们首先计算出待插入元素的哈希值idx，查看此位置是否已经有该元素。如果是，则更新其值；否则，在此位置插入新元素。如果容量超过两倍，则需要进行扩容操作。
要获取某个键对应的值，我们同样需要计算其哈希值，并遍历整个链表，根据键值判断元素是否存在。如果找到了，则返回对应的值；否则，返回-1。
在删除某个元素时，我们同样首先计算出待删除元素的哈希值，并定位到相应的链表头部。然后我们遍历这个链表，并寻找要删除的元素。在链表中，我们需要处理头部、中间和尾部三种删除情况。
由于哈希表中冲突可能会很多，因此正确地解决哈希冲突是非常关键的。本例使用了开放地址法，特别是线性探测来解决哈希冲突。
- Java版本
public class MyHashMap { // 哈希表节点 class Node { int key; // 键值 int val; // 数值 Node next; // 下一个节点的指针 public Node(int k, int v) { key = k; val = v; } } private Node[] data; // 存储哈希表节点的数据数组 private int size; // 当前数据个数 private int cap = 1000; // 数组容量 private double loadFactor; // 负载因子 // 构造函数 public MyHashMap() { data = new Node[cap]; loadFactor = 0.75; } // 获取某个数字的哈希值 private int hashCode(int key) { return key % cap; } // 插入或更新数据 public void put(int key, int value) { int idx = hashCode(key); // 获取插入位置的哈希值 // 检测是否已有该元素 Node node = data[idx]; while (node != null) { if (node.key == key) { node.val = value; return; } node = node.next; } // 如果容量满了，进行扩容 if (size >= loadFactor * cap) { Node[] old_data = data; cap *= 2; data = new Node[cap]; size = 0; for (int i = 0; i < old_data.length; ++i) { node = old_data[i]; while (node != null) { put(node.key, node.val); node = node.next; } } } // 在指定位置插入新元素 Node new_node = new Node(key, value); new_node.next = data[idx]; data[idx] = new_node; ++size; } // 获取某个键对应的值，不存在则返回-1 public int get(int key) { int idx = hashCode(key); Node node = data[idx]; while (node != null) { if (node.key == key) { return node.val; } node = node.next; } return -1; } // 删除某个元素 public void remove(int key) { int idx = hashCode(key); Node node = data[idx]; if (node == null) return; // 特殊处理头节点的情况 if (node.key == key) { data[idx] = node.next; --size; return; } // 删除中间或尾部位置上的元素 while (node.next != null) { if (node.next.key == key) { node.next = node.next.next; --size; return; } node = node.next; } } public static void main(String[] args) { MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); myHashMap.put(2, 2); System.out.println(myHashMap.get(1)); // 1 System.out.println(myHashMap.get(3)); // -1 myHashMap.put(2, 1); System.out.println(myHashMap.get(2)); // 1 myHashMap.remove(2); System.out.println(myHashMap.get(2)); // -1 } }
