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

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

哈希查找的工作原理：

1. 哈希函数：通过哈希函数将键转换为哈希表中的索引。
2. 存储数据：将数据存储在哈希表的相应位置。
3. 查找数据：通过键计算哈希值，直接访问数据所在的哈希表位置。
4. 处理冲突：当两个不同的键产生相同的哈希值时（称为哈希冲突），需要采用某种策略来解决。常见的冲突解决策略包括链地址法（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)); // 返回 1lru.put(3, 3); // 该操作会使得关键字 2 作废System.out.println(lru.get(2)); // 返回 -1 (未找到)System.out.println(lru.get(3)); // 返回 3lru.put(4, 4); // 该操作会使得关键字 1 作废System.out.println(lru.get(1)); // 返回 -1 (未找到)System.out.println(lru.get(3)); // 返回 3System.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);}
}

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