Java哈希查找(含面试大厂题和源码)

🕗 发布于 2024-04-16 17:58 哈希算法 java 面试

哈希查找（Hash Search）是一种基于哈希表（Hash Table）的数据查找方法。哈希表通过使用哈希函数将键（Key）映射到表中的位置来存储数据，从而实现快速的数据访问。哈希查找的效率通常取决于哈希函数的设计、哈希表的大小以及处理哈希冲突的策略。

哈希查找的工作原理：

哈希函数：通过哈希函数将键转换为哈希表中的索引。
存储数据：将数据存储在哈希表的相应位置。
查找数据：通过键计算哈希值，直接访问数据所在的哈希表位置。
处理冲突：当两个不同的键产生相同的哈希值时（称为哈希冲突），需要采用某种策略来解决。常见的冲突解决策略包括链地址法（Chaining）和开放寻址法（Open Addressing）。

哈希查找的优缺点：

优点：

平均情况下，哈希查找可以实现接近 O(1) 的时间复杂度。
哈希表可以高效地支持大量的数据插入、查找和删除操作。

缺点：

哈希表的性能依赖于哈希函数的设计和冲突解决策略。
哈希表可能需要额外的存储空间来处理冲突。
哈希查找不保留元素的顺序。

哈希查找的Java实现：

import java.util.HashMap;
import java.util.Map;

public class HashSearch {
    private Map<Integer, String> hashTable;

    public HashSearch() {
        hashTable = new HashMap<>();
    }

    public void insert(int key, String value) {
        hashTable.put(key, value);
    }

    public String search(int key) {
        return hashTable.get(key);
    }

    public static void main(String[] args) {
        HashSearch search = new HashSearch();
        search.insert(1, "apple");
        search.insert(2, "banana");
        search.insert(3, "cherry");
        String result = search.search(2);
        System.out.println("Value for key 2: " + result);
    }
}

在面试中，了解哈希查找的原理和实现是非常重要的，尤其是当面试官询问关于数据结构和算法的问题时。通过实现哈希查找，可以展示你对基本数据结构和算法的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试！哈希查找是大厂面试中常见的题目类型，尤其是在处理大量数据和需要高效查找的场景中。以下是三道可能出现在大厂面试中的与哈希查找相关的编程题目，以及相应的Java源码实现。

题目 1：设计一个 LRU 缓存

描述：
设计一个 LRU（Least Recently Used）缓存，它应该支持以下操作：获取数据 get 和写入数据 put。

示例：

输入: 
  ["LRUCache", "put", "put", "get", "put", "get", "get"]
  [ [2], [1, 1], [2, 2], [1], [3, 3], [2], [4]
  输出: [null, null, null, 1, null, 2, 3]

Java 源码：

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache;
    private final DoublyLinkedList lru;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new DoublyLinkedList();
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            lru.moveToHead(key);
            return cache.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.put(key, value);
            lru.moveToHead(key);
        } else {
            if (cache.size() >= capacity) {
                int last = lru.removeTail();
                cache.remove(last);
            }
            cache.put(key, value);
            lruaddToHead(key);
        }
    }

    private void lruaddToHead(int key) {
        Node newNode = new Node(key);
        lru.addFirst(newNode);
    }

    private void lru.moveToHead(int key) {
        Node node = lru.find(key);
        if (node != null) {
            lru.remove(node);
            lruaddToHead(key);
        }
    }

    private void lru removeTail() {
        if (!lru.isEmpty()) {
            lru.removeLast();
        }
    }

    private class DoublyLinkedList {
        private Node head, tail;

        DoublyLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        void addFirst(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        void removeLast() {
            if (tail.prev != head) {
                Node last = tail.prev;
                remove(last);
            }
        }

        Node find(int key) {
            Node current = head.next;
            while (current != tail) {
                if (current.key == key) {
                    return current;
                }
                current = current.next;
            }
            return null;
        }
    }

    private class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1)); // 返回 1
        lru.put(3, 3); // 该操作会使得关键字 2 作废
        System.out.println(lru.get(2)); // 返回 -1 (未找到)
        System.out.println(lru.get(3)); // 返回 3
        lru.put(4, 4); // 该操作会使得关键字 1 作废
        System.out.println(lru.get(1)); // 返回 -1 (未找到)
        System.out.println(lru.get(3)); // 返回 3
        System.out.println(lru.get(4)); // 返回 4
    }
}

题目 2：字符串哈希映射

描述：
给定一个字符串，将所有出现的大写字母映射到一个新字符串中，映射规则为 ‘A’ -> ‘a’，‘B’ -> ‘b’，…，‘Z’ -> ‘z’。

示例：

输入: "LEETCODEISHIRING"
输出: "ldecodishngi"

Java 源码：

public class MapStringToHash {
    public String stringHashMapping(String s) {
        StringBuilder result = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isUpperCase(ch)) {
                result.append((char) (ch + 32));
            } else {
                result.append(ch);
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        MapStringToHash solution = new MapStringToHash();
        String input = "LEETCODEISHIRING";
        String output = solution.stringHashMapping(input);
        System.out.println("Mapped string: " + output);
    }
}

题目 3：两个字符串的哈希映射

描述：
给定两个字符串，计算它们在哈希表中的相似度。如果一个字符串的字符可以通过另一个字符串中的字符进行替换得到，那么这两个字符串是相似的。

示例：

输入: s1 = "great", s2 = "raste"
输出: true

Java 源码：

import java.util.HashSet;
import java.util.Set;

public class HashMappingTwoStrings {
    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        for (int i = 0; i < s1.length(); i++) {
            set1.add(s1.charAt(i));
            set2.add(s2.charAt(i));
        }
        return set1.equals(set2);
    }

    public static void main(String[] args) {
        HashMappingTwoStrings solution = new HashMappingTwoStrings();
        String s1 = "great";
        String s2 = "raste";
        boolean result = solution.areAlmostEqual(s1, s2);
        System.out.println("Strings are almost equal: " + result);
    }
}

这些题目和源码展示了哈希查找在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！

原文地址：https://blog.csdn.net/2302_80314137/article/details/137776946

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Go微服务: go-micro集成链路追踪jaeger
下一篇：如何防御局域网的网络攻击

【脑机接口】脑机接口性能的电压波形的尖峰分类和阈值比较
目标。对于皮质内脑机接口(bmi)，动作电位电压波形通常被分类以分离出单个神经元。如果这些神经元包含独立调节这一过程可以提高BMI的表现。然而，sorting行动电位(“尖峰”)需要高采样率，并且计算
阅读更多2024-09-20
与谷歌旗下自动驾驶公司扩大合作后，Uber股票值得买入吗？
在第二季度强劲的业绩和战略合作伙伴关系的推动下，Uber的股价最近出现了反弹，这表明该公司的股价仍有上涨空间，尤其是Uber在自动驾驶领域还在继续创新，以及还在持续的扩大其广告业务，目前该业务已经可以
阅读更多2024-09-20
IntelliJ IDEA 创建 Java 项目指南
通过以上步骤，我们成功地在 IntelliJ IDEA 中创建了一个新的 Java 项目，并编写和运行了第一个 Java 程序。如果想为你的代码添加测试，可以右键点击类名，选择 `Create New
阅读更多2024-09-20
jenkins声明式流水线语法详解
最基本的语法包含。
阅读更多2024-09-20
【原创】java+springboot+mysql高校社团网系统设计与实现
使用java+springboot+mysql开发的高校社团网，系统包含管理员、学生角色，功能如下：管理员：登录系统；首页；用户管理；社团分类管理；社团信息管理（社团审核）；系统留言；系统公告；友链管
阅读更多2024-09-20
Unity 设计模式之结构型模式 -【适配器模式】【桥接模式】【组合模式】
设计模式是指在软件开发中为解决常见问题而总结出的一套可复用的解决方案。这些模式是经过长期实践证明有效的编程经验总结，并可以在不同的项目中复用。设计模式并不是代码片段，而是对常见问题的抽象解决方案，它提
阅读更多2024-09-20
萌啦数据行业数据在哪看，萌啦ozon行业数据怎么看
在跨境电商的浪潮中，数据已成为商家决策的重要基石。萌啦Ozon数据行业分析板块，作为连接商家与市场动态的桥梁，为商家提供了丰富的行业洞察与精准的市场指导。本文将带您深入探索萌啦Ozon数据行业分析板块
阅读更多2024-09-20
班主任群发成绩教程，宝藏工具来减负
家长们呀，都特别关心自己孩子的成绩，考试一结束就像潮水般涌来询问成绩。老师也是人啊，忙完这些工作，都没有自己的时间了。各种表格要填写，学生的信息表、考勤表、成绩统计表等等，每一项都容不得半点马虎。而且
阅读更多2024-09-20
微服务架构中的负载均衡与服务注册中心(Nacos)
通过合理使用负载均衡和注册中心，我们可以构建一个更加健壮、可扩展的微服务架构。这不仅提高了系统的可用性，还大大增强了运维的灵活性。在实际业务中，要根据具体的场景选择合适的策略，并持续优化以应对不断变化
阅读更多2024-09-20
基于Java的题库管理系统设计与实现（springboot vue）
摘要现今教育教学领域对于高效、便捷的题库管理系统的需求日益增长。本文以Java为基础，采用SpringBoot和Vue构建前后端分离的技术架构，结合MySQL数据库，设计与实现了一套题库管理系统。该系
阅读更多2024-09-20

Java哈希查找(含面试大厂题和源码)

哈希查找的工作原理：

哈希查找的优缺点：

哈希查找的Java实现：

题目 1：设计一个 LRU 缓存

题目 2：字符串哈希映射

题目 3：两个字符串的哈希映射

相关文章