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

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

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

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

算法思路

哈希表(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
    }
}
相关文章
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
57 0
数据结构与算法学习十五:哈希表
|
4月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
23天前
|
机器学习/深度学习 人工智能 监控
智慧交通AI算法解决方案
智慧交通AI算法方案针对交通拥堵、违法取证难等问题,通过AI技术实现交通管理的智能化。平台层整合多种AI能力,提供实时监控、违法识别等功能;展现层与应用层则通过一张图、路口态势研判等工具,提升交通管理效率。方案优势包括先进的算法、系统集成性和数据融合性,应用场景涵盖车辆检测、道路环境检测和道路行人检测等。
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
35 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
3月前
|
存储 Java Serverless
【数据结构】哈希表&二叉搜索树详解
本文详细介绍了二叉搜索树和哈希表这两种数据结构。二叉搜索树是一种特殊二叉树,具有左子树节点值小于根节点、右子树节点值大于根节点的特点,并且不允许键值重复。文章给出了插入、删除和搜索等方法的具体实现。哈希表则通过哈希函数将键名映射为数组下标,实现快速查找,其插入、删除和查找操作时间复杂度理想情况下为O(1)。文中还讨论了哈希函数的设计原则、哈希冲突的解决方法及哈希表的实现细节。
62 8
【数据结构】哈希表&二叉搜索树详解
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
84 2
|
2月前
|
存储 缓存 Java
【数据结构】哈希表
【数据结构】哈希表
48 1