理解常用算法和数据结构是编程的重要基础，动态数组和哈希表是其中两个非常重要的容器。以下详细解释每一块内容，包括其设计原理、涉及的知识点以及代码示例。
一、动态数组
动态数组是一种可以动态调整大小的数组，它克服了普通数组固定长度的缺点。
1. 动态数组的设计原理
- 存储结构：
- 动态数组使用连续的内存块存储数据，与普通数组相似。
- 扩容机制：
- 当存储空间不足时，动态数组会分配更大的内存空间（通常为当前大小的 2 倍），并将旧数据复制到新内存中。
- 时间复杂度：
- 插入元素：平均时间复杂度为 O(1)O(1)，最坏情况（触发扩容）为 O(n)O(n)。
- 查找元素：时间复杂度为 O(1)O(1)（通过索引访问）。
- 删除元素：时间复杂度为 O(n)O(n)（可能需要移动后续元素）。
2. 代码实现动态数组
C++ 示例
实现一个简单的动态数组类。
#include <iostream>
#include <stdexcept>
class DynamicArray {
private:
int* data;
int capacity;
int size;
void resize(int newCapacity) {
int* newData = new int[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
delete[] data;
data = newData;
capacity = newCapacity;
}
public:
DynamicArray() : data(new int[2]), capacity(2), size(0) {}
~DynamicArray() {
delete[] data;
}
void add(int value) {
if (size == capacity) {
resize(capacity * 2);
}
data[size++] = value;
}
void removeAt(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
}
int get(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
return data[index];
}
int getSize() const {
return size;
}
};
二、哈希表
哈希表是一种基于哈希函数实现的键值对存储的数据结构，具有快速插入、删除和查找的特性。
1. 哈希表的设计原理
- 哈希函数：
- 将键映射到数组索引。哈希函数应具有良好的分布性，以减少冲突。
- 冲突处理：
- 开放地址法：当冲突发生时，寻找下一个空闲位置。
- 链地址法：使用链表或其他结构存储冲突的元素。
- 动态扩容：
- 当负载因子（填充率）达到一定阈值时，哈希表会重新分配更大的存储空间并重新哈希所有键值对。
2. 哈希表的优缺点
- 优点：
- 插入、删除和查找操作的平均时间复杂度为 O(1)O(1)。
- 缺点：
- 最坏情况下（哈希冲突严重），时间复杂度退化为 O(n)O(n)。
- 需要更多的内存以避免冲突。
3. 代码实现哈希表
C++ 示例
实现一个简单的链地址法哈希表。
#include <iostream>
#include <list>
#include <vector>
#include <string>
class HashTable {
private:
std::vector<std::list<std::pair<std::string, int>>> table;
int capacity;
int hashFunction(const std::string& key) const {
int hash = 0;
for (char ch : key) {
hash = (hash * 31 + ch) % capacity;
}
return hash;
}
public:
HashTable(int cap) : capacity(cap), table(cap) {}
void insert(const std::string& key, int value) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.first == key) {
pair.second = value;
return;
}
}
table[index].emplace_back(key, value);
}
bool find(const std::string& key, int& value) const {
int index = hashFunction(key);
for (const auto& pair : table[index]) {
if (pair.first == key) {
value = pair.second;
return true;
}
}
return false;
}
void remove(const std::string& key) {
int index = hashFunction(key);
table[index].remove_if([&](const std::pair<std::string, int>& pair) {
return pair.first == key;
});
}
};
三、动态数组与哈希表的对比
| 特性 | 动态数组 | 哈希表 |
|---|---|---|
| 数据存储 | 连续内存块 | 哈希函数映射位置 |
| 时间复杂度 | 插入 O(1)O(1) | 插入/查找 O(1)O(1) |
| 扩容 | 按固定倍率扩容 | 按负载因子扩容 |
| 空间利用率 | 高 | 低（存在一定冗余） |
| 查找效率 | 慢（线性查找） | 快 |
四、应用场景
- 动态数组：
- 常用于实现列表、栈和队列。
- 适合需要频繁按索引访问的场景。
- 哈希表：
- 用于实现键值对存储，如字典、缓存、符号表。
- 适合需要快速查找和插入的场景。
通过掌握动态数组和哈希表的原理和实现，可以应对大部分数据存储与检索需求。学习中建议亲手实现并优化这些数据结构，以加深理解和实践能力。