大家好，我是算法学长，一个热爱分享算法知识的开发者。算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

哈希查找

介绍

哈希查找（Hash Search），又称散列查找，是一种高效的查找算法，它用哈希函数将数据转换为数组下标，然后直接访问数组中的元素。哈希查找的核心思想是将数据元素通过哈希函数映射到哈希表中的位置，实现快速查找。

在理想情况下，哈希查找的时间复杂度为 O(1)，这就意味着无论数据规模多大，查找操作都能在常数时间内完成，这是哈希查找相比其他查找算法（如二分查找、线性查找）的最大优势。

不过使用哈希查找必须要考虑哈希冲突（不同的数据被映射到相同的位置）问题。

算法步骤

设计一个适合数据特点的哈希函数，将数据映射到哈希表的索引位置
构建哈希表，将所有元素通过哈希函数映射、存储到相应位置
解决可能出现的哈希冲突（通常采用链地址法或开放寻址法）
查找时，通过同样的哈希函数计算目标数据的哈希值
根据哈希值定位到哈希表中的位置
如果存在冲突，则按照解决冲突的方法查找目标元素

核心特性

快速访问：理想情况下查找时间复杂度为 O(1)
哈希函数：哈希查找的核心，将数据映射到数组索引的函数
哈希冲突：不同数据映射到相同位置的情况，需要特殊处理
空间换时间：通过额外的内存空间换取查找时间的提升
负载因子：表示哈希表的填充程度，影响查找效率和冲突概率
动态扩容：负载因子过高时，需要扩大哈希表并重新哈希所有元素

基础实现

下面展示哈希查找在各种主流编程语言中的实现：

Java实现

▼
java
复制代码
public class HashSearch {
    // 哈希表节点类
    static class Node {
        String key;
        int value;
        Node next;
        
        public Node(String key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    
    // 哈希表类
    static class HashTable {
        private Node[] buckets;
        private int capacity;
        private int size;
        private final float LOAD_FACTOR = 0.75f; // 负载因子阈值
        
        public HashTable(int capacity) {
            this.capacity = capacity;
            this.buckets = new Node[capacity];
            this.size = 0;
        }
        
        // 哈希函数
        private int hash(String key) {
            int hash = 0;
            for (char c : key.toCharArray()) {
                hash = (hash * 31 + c) % capacity;
            }
            return Math.abs(hash);
        }
        
        // 插入键值对
        public void put(String key, int value) {
            if ((float)size / capacity >= LOAD_FACTOR) {
                resize(2 * capacity);
            }
            
            int index = hash(key);
            Node newNode = new Node(key, value);
            
            // 如果桶为空，直接插入
            if (buckets[index] == null) {
                buckets[index] = newNode;
                size++;
                return;
            }
            
            // 处理哈希冲突，使用链地址法
            Node current = buckets[index];
            
            // 检查是否已存在相同的键
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value; // 更新值
                    return;
                }
                if (current.next == null) {
                    break;
                }
                current = current.next;
            }
            
            // 在链表末尾添加新节点
            current.next = newNode;
            size++;
        }
        
        // 查找键对应的值
        public Integer get(String key) {
            int index = hash(key);
            Node current = buckets[index];
            
            // 遍历链表查找匹配的键
            while (current != null) {
                if (current.key.equals(key)) {
                    return current.value;
                }
                current = current.next;
            }
            
            // 未找到
            return null;
        }
        
        // 删除键值对
        public boolean remove(String key) {
            int index = hash(key);
            Node current = buckets[index];
            Node prev = null;
            
            // 查找目标节点
            while (current != null) {
                if (current.key.equals(key)) {
                    break;
                }
                prev = current;
                current = current.next;
            }
            
            // 未找到目标节点
            if (current == null) {
                return false;
            }
            
            // 删除节点
            if (prev == null) {
                buckets[index] = current.next;
            } else {
                prev.next = current.next;
            }
            
            size--;
            return true;
        }
        
        // 扩容并重新哈希
        private void resize(int newCapacity) {
            Node[] oldBuckets = buckets;
            
            // 创建新的哈希表
            buckets = new Node[newCapacity];
            capacity = newCapacity;
            size = 0;
            
            // 重新哈希所有元素
            for (Node bucket : oldBuckets) {
                Node current = bucket;
                while (current != null) {
                    put(current.key, current.value);
                    current = current.next;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);
        
        // 插入数据
        hashTable.put("apple", 5);
        hashTable.put("banana", 10);
        hashTable.put("orange", 15);
        hashTable.put("grape", 20);
        
        // 查找数据
        System.out.println("apple: " + hashTable.get("apple"));
        System.out.println("banana: " + hashTable.get("banana"));
        System.out.println("orange: " + hashTable.get("orange"));
        System.out.println("grape: " + hashTable.get("grape"));
        System.out.println("watermelon: " + hashTable.get("watermelon"));
        
        // 删除数据
        hashTable.remove("orange");
        System.out.println("After removing orange: " + hashTable.get("orange"));
    }
}

JavaScript 实现

▼
javascript
复制代码
class HashTable {
    constructor(capacity = 10) {
        this.capacity = capacity;
        this.buckets = new Array(capacity).fill(null).map(() => []);
        this.size = 0;
        this.LOAD_FACTOR = 0.75;
    }
    
    // 哈希函数
    hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
        }
        return Math.abs(hash);
    }
    
    // 插入键值对
    put(key, value) {
        if (this.size / this.capacity >= this.LOAD_FACTOR) {
            this.resize(2 * this.capacity);
        }
        
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        // 检查是否已存在相同的键
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket[i].value = value; // 更新值
                return;
            }
        }
        
        // 添加新的键值对
        bucket.push({ key, value });
        this.size++;
    }
    
    // 查找键对应的值
    get(key) {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                return bucket[i].value;
            }
        }
        
        // 未找到
        return undefined;
    }
    
    // 删除键值对
    remove(key) {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket.splice(i, 1);
                this.size--;
                return true;
            }
        }
        
        return false;
    }
    
    // 扩容并重新哈希
    resize(newCapacity) {
        const oldBuckets = this.buckets;
        
        // 创建新的哈希表
        this.buckets = new Array(newCapacity).fill(null).map(() => []);
        this.capacity = newCapacity;
        this.size = 0;
        
        // 重新哈希所有元素
        for (const bucket of oldBuckets) {
            for (const node of bucket) {
                this.put(node.key, node.value);
            }
        }
    }
}

// 测试
const hashTable = new HashTable();

// 插入数据
hashTable.put("apple", 5);
hashTable.put("banana", 10);
hashTable.put("orange", 15);
hashTable.put("grape", 20);

// 查找数据
console.log("apple:", hashTable.get("apple"));
console.log("banana:", hashTable.get("banana"));
console.log("orange:", hashTable.get("orange"));
console.log("grape:", hashTable.get("grape"));
console.log("watermelon:", hashTable.get("watermelon"));

// 删除数据
hashTable.remove("orange");
console.log("After removing orange:", hashTable.get("orange"));

Python 实现

▼
python
复制代码
class HashTable:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
        self.LOAD_FACTOR = 0.75
    
    # 哈希函数
    def hash(self, key):
        hash_value = 0
        for char in key:
            hash_value = (hash_value * 31 + ord(char)) % self.capacity
        return abs(hash_value)
    
    # 插入键值对
    def put(self, key, value):
        if self.size / self.capacity >= self.LOAD_FACTOR:
            self.resize(2 * self.capacity)
        
        index = self.hash(key)
        bucket = self.buckets[index]
        
        # 检查是否已存在相同的键
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新值
                return
        
        # 添加新的键值对
        bucket.append((key, value))
        self.size += 1
    
    # 查找键对应的值
    def get(self, key):
        index = self.hash(key)
        bucket = self.buckets[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        # 未找到
        return None
    
    # 删除键值对
    def remove(self, key):
        index = self.hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        
        return False
    
    # 扩容并重新哈希
    def resize(self, new_capacity):
        old_buckets = self.buckets
        
        # 创建新的哈希表
        self.buckets = [[] for _ in range(new_capacity)]
        self.capacity = new_capacity
        self.size = 0
        
        # 重新哈希所有元素
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

# 测试
hash_table = HashTable()

# 插入数据
hash_table.put("apple", 5)
hash_table.put("banana", 10)
hash_table.put("orange", 15)
hash_table.put("grape", 20)

# 查找数据
print("apple:", hash_table.get("apple"))
print("banana:", hash_table.get("banana"))
print("orange:", hash_table.get("orange"))
print("grape:", hash_table.get("grape"))
print("watermelon:", hash_table.get("watermelon"))

# 删除数据
hash_table.remove("orange")
print("After removing orange:", hash_table.get("orange"))

Go 实现

▼
go
复制代码
package main

import (
    "fmt"
    "math"
)

// 哈希表节点
type Node struct {
    Key   string
    Value int
    Next  *Node
}

// 哈希表
type HashTable struct {
    Buckets    []*Node
    Capacity   int
    Size       int
    LoadFactor float64
}

// 创建新的哈希表
func NewHashTable(capacity int) *HashTable {
    return &HashTable{
        Buckets:    make([]*Node, capacity),
        Capacity:   capacity,
        Size:       0,
        LoadFactor: 0.75,
    }
}

// 哈希函数
func (ht *HashTable) hash(key string) int {
    h := 0
    for _, c := range key {
        h = (h*31 + int(c)) % ht.Capacity
    }
    return int(math.Abs(float64(h)))
}

// 插入键值对
func (ht *HashTable) Put(key string, value int) {
    if float64(ht.Size)/float64(ht.Capacity) >= ht.LoadFactor {
        ht.resize(2 * ht.Capacity)
    }
    
    index := ht.hash(key)
    newNode := &Node{Key: key, Value: value}
    
    // 如果桶为空，直接插入
    if ht.Buckets[index] == nil {
        ht.Buckets[index] = newNode
        ht.Size++
        return
    }
    
    // 处理哈希冲突，使用链地址法
    current := ht.Buckets[index]
    
    // 检查是否已存在相同的键
    for current != nil {
        if current.Key == key {
            current.Value = value // 更新值
            return
        }
        if current.Next == nil {
            break
        }
        current = current.Next
    }
    
    // 在链表末尾添加新节点
    current.Next = newNode
    ht.Size++
}

// 查找键对应的值
func (ht *HashTable) Get(key string) (int, bool) {
    index := ht.hash(key)
    current := ht.Buckets[index]
    
    // 遍历链表查找匹配的键
    for current != nil {
        if current.Key == key {
            return current.Value, true
        }
        current = current.Next
    }
    
    // 未找到
    return 0, false
}

// 删除键值对
func (ht *HashTable) Remove(key string) bool {
    index := ht.hash(key)
    current := ht.Buckets[index]
    var prev *Node = nil
    
    // 查找目标节点
    for current != nil {
        if current.Key == key {
            break
        }
        prev = current
        current = current.Next
    }
    
    // 未找到目标节点
    if current == nil {
        return false
    }
    
    // 删除节点
    if prev == nil {
        ht.Buckets[index] = current.Next
    } else {
        prev.Next = current.Next
    }
    
    ht.Size--
    return true
}

// 扩容并重新哈希
func (ht *HashTable) resize(newCapacity int) {
    oldBuckets := ht.Buckets
    
    // 创建新的哈希表
    ht.Buckets = make([]*Node, newCapacity)
    ht.Capacity = newCapacity
    ht.Size = 0
    
    // 重新哈希所有元素
    for _, bucket := range oldBuckets {
        current := bucket
        for current != nil {
            ht.Put(current.Key, current.Value)
            current = current.Next
        }
    }
}

func main() {
    hashTable := NewHashTable(10)
    
    // 插入数据
    hashTable.Put("apple", 5)
    hashTable.Put("banana", 10)
    hashTable.Put("orange", 15)
    hashTable.Put("grape", 20)
    
    // 查找数据
    if value, found := hashTable.Get("apple"); found {
        fmt.Println("apple:", value)
    }
    if value, found := hashTable.Get("banana"); found {
        fmt.Println("banana:", value)
    }
    if value, found := hashTable.Get("orange"); found {
        fmt.Println("orange:", value)
    }
    if value, found := hashTable.Get("grape"); found {
        fmt.Println("grape:", value)
    }
    if value, found := hashTable.Get("watermelon"); found {
        fmt.Println("watermelon:", value)
    } else {
        fmt.Println("watermelon: not found")
    }
    
    // 删除数据
    hashTable.Remove("orange")
    if value, found := hashTable.Get("orange"); found {
        fmt.Println("After removing orange:", value)
    } else {
        fmt.Println("After removing orange: not found")
    }
}

C 实现

▼
c
复制代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 哈希表节点
typedef struct Node {
    char* key;
    int value;
    struct Node* next;
} Node;

// 哈希表
typedef struct {
    Node** buckets;
    int capacity;
    int size;
    float loadFactor;
} HashTable;

// 创建新节点
Node* createNode(const char* key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 创建哈希表
HashTable* createHashTable(int capacity) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->buckets = (Node**)calloc(capacity, sizeof(Node*));
    ht->capacity = capacity;
    ht->size = 0;
    ht->loadFactor = 0.75f;
    return ht;
}

// 哈希函数
unsigned int hash(const char* key, int capacity) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash * 31 + *key) % capacity;
        key++;
    }
    return hash;
}

// 前向声明
void resize(HashTable* ht, int newCapacity);

// 插入键值对
void put(HashTable* ht, const char* key, int value) {
    if ((float)ht->size / ht->capacity >= ht->loadFactor) {
        resize(ht, 2 * ht->capacity);
    }
    
    unsigned int index = hash(key, ht->capacity);
    Node* newNode = createNode(key, value);
    
    // 如果桶为空，直接插入
    if (ht->buckets[index] == NULL) {
        ht->buckets[index] = newNode;
        ht->size++;
        return;
    }
    
    // 处理哈希冲突，使用链地址法
    Node* current = ht->buckets[index];
    
    // 检查是否已存在相同的键
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value; // 更新值
            free(newNode->key);
            free(newNode);
            return;
        }
        if (current->next == NULL) {
            break;
        }
        current = current->next;
    }
    
    // 在链表末尾添加新节点
    current->next = newNode;
    ht->size++;
}

// 查找键对应的值
bool get(HashTable* ht, const char* key, int* value) {
    unsigned int index = hash(key, ht->capacity);
    Node* current = ht->buckets[index];
    
    // 遍历链表查找匹配的键
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            *value = current->value;
            return true;
        }
        current = current->next;
    }
    
    // 未找到
    return false;
}

// 删除键值对
bool removeKey(HashTable* ht, const char* key) {
    unsigned int index = hash(key, ht->capacity);
    Node* current = ht->buckets[index];
    Node* prev = NULL;
    
    // 查找目标节点
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            break;
        }
        prev = current;
        current = current->next;
    }
    
    // 未找到目标节点
    if (current == NULL) {
        return false;
    }
    
    // 删除节点
    if (prev == NULL) {
        ht->buckets[index] = current->next;
    } else {
        prev->next = current->next;
    }
    
    free(current->key);
    free(current);
    ht->size--;
    return true;
}

// 扩容并重新哈希
void resize(HashTable* ht, int newCapacity) {
    Node** oldBuckets = ht->buckets;
    int oldCapacity = ht->capacity;
    
    // 创建新的哈希表
    ht->buckets = (Node**)calloc(newCapacity, sizeof(Node*));
    ht->capacity = newCapacity;
    ht->size = 0;
    
    // 重新哈希所有元素
    for (int i = 0; i < oldCapacity; i++) {
        Node* current = oldBuckets[i];
        while (current != NULL) {
            Node* next = current->next;
            // 重新插入节点
            put(ht, current->key, current->value);
            // 释放原节点
            free(current->key);
            free(current);
            current = next;
        }
    }
    
    free(oldBuckets);
}

// 释放哈希表内存
void freeHashTable(HashTable* ht) {
    for (int i = 0; i < ht->capacity; i++) {
        Node* current = ht->buckets[i];
        while (current != NULL) {
            Node* next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }
    free(ht->buckets);
    free(ht);
}

int main() {
    HashTable* ht = createHashTable(10);
    
    // 插入数据
    put(ht, "apple", 5);
    put(ht, "banana", 10);
    put(ht, "orange", 15);
    put(ht, "grape", 20);
    
    // 查找数据
    int value;
    if (get(ht, "apple", &value)) {
        printf("apple: %d\n", value);
    }
    if (get(ht, "banana", &value)) {
        printf("banana: %d\n", value);
    }
    if (get(ht, "orange", &value)) {
        printf("orange: %d\n", value);
    }
    if (get(ht, "grape", &value)) {
        printf("grape: %d\n", value);
    }
    if (get(ht, "watermelon", &value)) {
        printf("watermelon: %d\n", value);
    } else {
        printf("watermelon: not found\n");
    }
    
    // 删除数据
    removeKey(ht, "orange");
    if (get(ht, "orange", &value)) {
        printf("After removing orange: %d\n", value);
    } else {
        printf("After removing orange: not found\n");
    }
    
    // 释放内存
    freeHashTable(ht);
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <cmath>

class HashTable {
private:
    // 哈希表存储的是键值对列表
    std::vector<std::list<std::pair<std::string, int>>> buckets;
    int capacity;
    int size;
    float loadFactor;
    
    // 哈希函数
    int hash(const std::string& key) const {
        int hashValue = 0;
        for (char c : key) {
            hashValue = (hashValue * 31 + c) % capacity;
        }
        return std::abs(hashValue);
    }
    
    // 扩容并重新哈希
    void resize(int newCapacity) {
        std::vector<std::list<std::pair<std::string, int>>> oldBuckets = buckets;
        
        // 创建新的哈希表
        buckets.clear();
        buckets.resize(newCapacity);
        capacity = newCapacity;
        size = 0;
        
        // 重新哈希所有元素
        for (const auto& bucket : oldBuckets) {
            for (const auto& pair : bucket) {
                put(pair.first, pair.second);
            }
        }
    }
    
public:
    HashTable(int capacity = 10) : capacity(capacity), size(0), loadFactor(0.75f) {
        buckets.resize(capacity);
    }
    
    // 插入键值对
    void put(const std::string& key, int value) {
        if ((float)size / capacity >= loadFactor) {
            resize(2 * capacity);
        }
        
        int index = hash(key);
        auto& bucket = buckets[index];
        
        // 检查是否已存在相同的键
        for (auto& pair : bucket) {
            if (pair.first == key) {
                pair.second = value; // 更新值
                return;
            }
        }
        
        // 添加新的键值对
        bucket.push_back({key, value});
        size++;
    }
    
    // 查找键对应的值
    bool get(const std::string& key, int& value) const {
        int index = hash(key);
        const auto& bucket = buckets[index];
        
        for (const auto& pair : bucket) {
            if (pair.first == key) {
                value = pair.second;
                return true;
            }
        }
        
        // 未找到
        return false;
    }
    
    // 删除键值对
    bool remove(const std::string& key) {
        int index = hash(key);
        auto& bucket = buckets[index];
        
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                size--;
                return true;
            }
        }
        
        return false;
    }
};

int main() {
    HashTable hashTable;
    
    // 插入数据
    hashTable.put("apple", 5);
    hashTable.put("banana", 10);
    hashTable.put("orange", 15);
    hashTable.put("grape", 20);
    
    // 查找数据
    int value;
    if (hashTable.get("apple", value)) {
        std::cout << "apple: " << value << std::endl;
    }
    if (hashTable.get("banana", value)) {
        std::cout << "banana: " << value << std::endl;
    }
    if (hashTable.get("orange", value)) {
        std::cout << "orange: " << value << std::endl;
    }
    if (hashTable.get("grape", value)) {
        std::cout << "grape: " << value << std::endl;
    }
    if (hashTable.get("watermelon", value)) {
        std::cout << "watermelon: " << value << std::endl;
    } else {
        std::cout << "watermelon: not found" << std::endl;
    }
    
    // 删除数据
    hashTable.remove("orange");
    if (hashTable.get("orange", value)) {
        std::cout << "After removing orange: " << value << std::endl;
    } else {
        std::cout << "After removing orange: not found" << std::endl;
    }
    
    return 0;
}

哈希冲突解决方法

哈希查找的核心问题是如何处理哈希冲突。下面是两种主要的解决方案：

链地址法（Separate Chaining）

▼
java
复制代码
public void chainInsert(String key, int value) {
    int index = hash(key);
    Node newNode = new Node(key, value);
    
    // 如果桶为空，直接插入
    if (buckets[index] == null) {
        buckets[index] = newNode;
        return;
    }
    
    // 否则遍历链表
    Node current = buckets[index];
    while (current.next != null) {
        // 如果找到相同的键，更新值
        if (current.key.equals(key)) {
            current.value = value;
            return;
        }
        current = current.next;
    }
    
    // 在链表末尾添加新节点
    if (current.key.equals(key)) {
        current.value = value;
    } else {
        current.next = newNode;
    }
}

开放寻址法（Open Addressing）

▼
java
复制代码
public class OpenAddressingHashTable {
    private String[] keys;
    private Integer[] values;
    private int capacity;
    private int size;
    
    public OpenAddressingHashTable(int capacity) {
        this.capacity = capacity;
        this.keys = new String[capacity];
        this.values = new Integer[capacity];
        this.size = 0;
    }
    
    private int hash(String key) {
        int hash = 0;
        for (char c : key.toCharArray()) {
            hash = (hash * 31 + c) % capacity;
        }
        return Math.abs(hash);
    }
    
    // 线性探测插入
    public void put(String key, int value) {
        if (size >= capacity * 0.75) {
            resize(2 * capacity);
        }
        
        int index = hash(key);
        
        // 线性探测
        while (keys[index] != null) {
            // 如果找到相同的键，更新值
            if (keys[index].equals(key)) {
                values[index] = value;
                return;
            }
            
            // 线性探测下一个位置
            index = (index + 1) % capacity;
        }
        
        // 找到空位，插入键值对
        keys[index] = key;
        values[index] = value;
        size++;
    }
    
    // 线性探测查找
    public Integer get(String key) {
        int index = hash(key);
        
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                return values[index];
            }
            
            index = (index + 1) % capacity;
        }
        
        return null;
    }
    
    // 线性探测删除（标记删除）
    public boolean remove(String key) {
        int index = hash(key);
        
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                // 标记删除
                keys[index] = "DELETED";
                values[index] = null;
                size--;
                return true;
            }
            
            index = (index + 1) % capacity;
        }
        
        return false;
    }
    
    // 扩容
    private void resize(int newCapacity) {
        String[] oldKeys = keys;
        Integer[] oldValues = values;
        
        keys = new String[newCapacity];
        values = new Integer[newCapacity];
        capacity = newCapacity;
        size = 0;
        
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && !oldKeys[i].equals("DELETED")) {
                put(oldKeys[i], oldValues[i]);
            }
        }
    }
}

优缺点

优点

查找、插入和删除操作的平均时间复杂度为 O(1)
适用于快速查找
不要求数据有序，更灵活
支持动态数据集，高效地添加和删除元素
通过合适的哈希函数和解决冲突策略，能实现非常优秀的性能

缺点

哈希冲突会降低查找效率，最坏情况下时间复杂度可能退化到 O(n)
需要额外的空间存储哈希表
不支持范围查询，不适合按顺序遍历场景
负载因子过高会导致性能下降，过低会浪费空间

应用场景

哈希查找适用于以下场景：

需要快速查找、插入和删除操作的数据结构，如字典或映射
实现缓存系统，比如LRU缓存、内存缓存等
数据库索引，特别是等值查询
符号表实现，如编译器和解释器中的变量表
去重操作，判断元素是否已存在
网页爬虫的URL去重

扩展

一致性哈希

一致性哈希是分布式系统中的重要概念，目的是尽可能少地重新分配数据：

▼
java
复制代码
public class ConsistentHash {
    private final int numberOfReplicas; // 虚拟节点数量
    private final SortedMap<Integer, String> circle = new TreeMap<>();
    
    public ConsistentHash(int numberOfReplicas, Collection<String> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (String node : nodes) {
            addNode(node);
        }
    }
    
    // 添加节点
    public void addNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String virtualNode = node + "#" + i;
            int hash = getHash(virtualNode);
            circle.put(hash, node);
        }
    }
    
    // 移除节点
    public void removeNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String virtualNode = node + "#" + i;
            int hash = getHash(virtualNode);
            circle.remove(hash);
        }
    }
    
    // 获取数据应该存储的节点
    public String getNode(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        
        int hash = getHash(key);
        
        // 如果没有大于等于该hash值的节点，则返回第一个节点
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        
        return circle.get(hash);
    }
    
    // 哈希函数
    private int getHash(String key) {
        return Math.abs(key.hashCode()) % 359;
    }
}

布隆过滤器

布隆过滤器是一种空间效率高的概率型数据结构，判断一个元素是否在集合中：

▼
java
复制代码
public class BloomFilter {
    private BitSet bitSet;
    private int bitSetSize;
    private int numHashFunctions;
    
    public BloomFilter(int expectedInsertions, double falsePositiveProbability) {
        // 计算最佳bit数组大小
        this.bitSetSize = (int) Math.ceil(-(expectedInsertions * Math.log(falsePositiveProbability)) / (Math.log(2) * Math.log(2)));
        
        // 计算最佳哈希函数数量
        this.numHashFunctions = (int) Math.ceil((bitSetSize / expectedInsertions) * Math.log(2));
        
        this.bitSet = new BitSet(bitSetSize);
    }
    
    // 添加元素
    public void add(String element) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = getHash(element, i);
            bitSet.set(hash);
        }
    }
    
    // 检查元素是否可能在集合中
    public boolean mightContain(String element) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = getHash(element, i);
            if (!bitSet.get(hash)) {
                return false; // 肯定不在集合中
            }
        }
        return true; // 可能在集合中
    }
    
    // 生成多个哈希值
    private int getHash(String element, int index) {
        int hash1 = element.hashCode();
        int hash2 = hash1 >>> 16;
        return Math.abs((hash1 + index * hash2) % bitSetSize);
    }
}

测验

什么是哈希查找？它的平均时间复杂度是多少？
什么是哈希冲突？列举两种常见的解决方法。
负载因子对哈希表性能有什么影响？
哈希函数的设计原则有哪些？
开放寻址法中的线性探测、二次探测和双重哈希有什么区别？

测验答案

一种通过哈希函数将数据转换为数组下标，然后直接访问数组中元素的查找算法，平均时间复杂度为 O(1)。

哈希冲突是指不同的数据通过哈希函数得到相同的哈希值。常见的解决方法有：（1）链地址法：在冲突位置建立链表；（2）开放寻址法：在原始位置基础上按照某种方式寻找下一个可用位置。

负载因子表示哈希表的填充程度。负载因子过高会增加哈希冲突概率，降低查找效率；负载因子过低会浪费空间。哈希表通常在负载因子达到某个阈值（比如0.75）时进行扩容。

（1）计算简单高效；（2）尽可能均匀分布，减少冲突；（3）具有雪崩效应，输入微小变化导致输出显著不同；（4）确定性，相同输入产生相同输出。

线性探测：冲突时按固定步长（一般是 1）向后查找空位；二次探测：冲突时按二次方向后查找；双重哈希：冲突时使用第二个哈希函数计算步长。二次探测和双重哈希都可以减轻线性探测的聚集问题。

一文带你学会"哈希查找"