哈希表代码

### 哈希表数据结构的代码实现 以下是基于不同编程语言的哈希表实现示例： #### Python 实现 Python 中可以通过字典 `dict` 来模拟哈希表的行为，也可以手动构建一个简单的哈希表。 ```python class HashTable: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(self.size)] def hash_function(self, key): return abs(hash(key)) % self.size def insert(self, key, value): index = self.hash_function(key) bucket = self.table[index] for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) def search(self, key): index = self.hash_function(key) bucket = self.table[index] for k, v in bucket: if k == key: return v return None def delete(self, key): index = self.hash_function(key) bucket = self.table[index] for i, (k, v) in enumerate(bucket): if k == key: del bucket[i] return True return False ``` 此代码展示了如何创建一个基本的哈希表并支持插入、删除和查询操作[^1]。 --- #### Java 实现 Java 提供了内置的 `HashMap` 类型，但如果想自己实现一个简单版本的哈希表，则可以按照如下方式完成： ```java import java.util.LinkedList; public class SimpleHashTable<K, V> { private LinkedList<Entry<K, V>>[] table; private int capacity; public SimpleHashTable(int initialCapacity) { this.capacity = initialCapacity; this.table = new LinkedList[capacity]; } private int hash(K key) { return Math.abs(key.hashCode()) % capacity; } public void put(K key, V value) { int index = hash(key); if (table[index] == null) { table[index] = new LinkedList<>(); } for (Entry<K, V> entry : table[index]) { if (entry.key.equals(key)) { entry.value = value; return; } } table[index].add(new Entry<>(key, value)); } public V get(K key) { int index = hash(key); if (table[index] != null) { for (Entry<K, V> entry : table[index]) { if (entry.key.equals(key)) { return entry.value; } } } return null; } public boolean remove(K key) { int index = hash(key); if (table[index] != null) { for (Entry<K, V> entry : table[index]) { if (entry.key.equals(key)) { table[index].remove(entry); return true; } } } return false; } private static class Entry<K, V> { K key; V value; Entry(K key, V value) { this.key = key; this.value = value; } } } ``` 上述代码定义了一个通用类型的哈希表类，并提供了基础的操作功能[^2]。 --- #### C++ 实现 C++ 的标准库中有 `unordered_map` 可用于快速实现哈希表的功能。如果要手动实现一个简易版的哈希表，可参考以下代码： ```cpp #include <iostream> #include <list> template<typename KeyType, typename ValueType> class HashTable { private: std::list<std::pair<KeyType, ValueType>>* table; int size; int hashFunction(const KeyType& key) const { return std::abs(std::hash<KeyType>()(key)) % size; } public: HashTable(int s) : size(s) { table = new std::list<std::pair<KeyType, ValueType>>[size]; } ~HashTable() { delete[] table; } void insert(const KeyType& key, const ValueType& value) { int index = hashFunction(key); auto &bucket = table[index]; for(auto &kv : bucket){ if(kv.first == key){ kv.second = value; return; } } bucket.emplace_back(key, value); } ValueType* find(const KeyType& key) { int index = hashFunction(key); auto &bucket = table[index]; for(auto &kv : bucket){ if(kv.first == key){ return &(kv.second); } } return nullptr; } bool erase(const KeyType& key) { int index = hashFunction(key); auto &bucket = table[index]; for(auto it = bucket.begin(); it != bucket.end(); ++it){ if(it->first == key){ bucket.erase(it); return true; } } return false; } }; ``` 这段代码展示了一种链地址法解决哈希冲突的方式[^3]。 --- ### 关于哈希表的关键概念说明 哈希表是一种高效的数据结构，其核心在于通过哈希函数将键映射到特定位置上以便快速访问。然而，在实际应用中可能会发生 **哈希冲突**（即两个不同的键被映射到了同一个索引）。常见的解决方案包括开放寻址法和链地址法等[^4]。 ---