理解常用算法和数据结构是编程的重要基础，动态数组和哈希表是其中两个非常重要的容器。以下详细解释每一块内容，包括其设计原理、涉及的知识点以及代码示例。
一、动态数组
动态数组是一种可以动态调整大小的数组，它克服了普通数组固定长度的缺点。
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) |
| 扩容 | 按固定倍率扩容 | 按负载因子扩容 |
| 空间利用率 | 高 | 低（存在一定冗余） |
| 查找效率 | 慢（线性查找） | 快 |
四、应用场景
- 动态数组：
- 常用于实现列表、栈和队列。
- 适合需要频繁按索引访问的场景。
- 哈希表：
- 用于实现键值对存储，如字典、缓存、符号表。
- 适合需要快速查找和插入的场景。
通过掌握动态数组和哈希表的原理和实现，可以应对大部分数据存储与检索需求。学习中建议亲手实现并优化这些数据结构，以加深理解和实践能力。