数据结构与算法面试题：实现一个哈希表，并考虑哈希冲突的解决方案。

冷不防 2024-03-16 17:05 6阅读 0赞

## 数据结构与算法面试题：实现一个哈希表，并考虑哈希冲突的解决方案。 ##

简介：实现一个哈希表，并考虑哈希冲突的解决方案。

### 算法思路 ###

哈希表（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
        }
    }