---

版权声明

• 本文原创作者：谷哥的小弟
• 作者博客地址：http://blog.csdn.net/lfdfhl

---

哈希表概述

哈希表（Hash Table）是一种常用的数据结构，用于实现键值对的映射关系。它通过哈希函数将键映射到一个特定的索引位置，然后在该位置存储相应的值。这样可以实现快速的插入、删除和查找操作，使得哈希表在很多场景下具有高效的性能。

哈希表的主要组成部分和工作原理如下：

• 1、哈希函数（Hash Function）： 这是哈希表的核心。哈希函数接受一个键作为输入，并输出一个固定大小的哈希值。这个哈希值通常是一个整数，它将键映射到哈希表中的一个索引位置。一个好的哈希函数应该尽量避免冲突，即不同的键映射到相同的索引位置。
  当我们使用哈希表时，我们首先需要选择一个合适的哈希函数。一个好的哈希函数应该具备以下特点：
  确定性： 对于相同的输入，哈希函数应始终产生相同的输出。
  高效性： 计算哈希值的过程应该是高效的，不论输入的大小如何。
  均匀性： 哈希函数应该尽可能均匀地分布键，以减少冲突的可能性。

• 2、数组（Array）： 哈希表内部通常使用一个数组来存储键值对。每个索引位置对应一个桶（Bucket），每个桶可以存储一个或多个键值对。

• 3、冲突处理： 由于哈希函数的输出空间可能小于键的实际空间，不同的键可能被映射到相同的索引位置，这就是冲突。哈希表需要解决冲突的方法，常见的有两种：链表法（Separate Chaining）： 每个桶使用一个链表来存储具有相同哈希值的键值对。开放地址法（Open Addressing）： 当发生冲突时，线性地探查下一个空闲的桶，或者通过其他探查方法找到下一个可用的位置。

• 4、装载因子（Load Factor）： 为了避免哈希表变得过满，我们引入了装载因子（Load Factor），它是哈希表中已存储键值对的数量与桶的总数之比。当装载因子超过某个阈值时，我们可以选择调整哈希表的大小，例如，通过重新哈希，增加数组的大小，从而减小装载因子。也就是说：装载因子表示哈希表中已存储键值对的数量与桶的总数之比。装载因子越大，冲突可能越多，性能可能下降。为了保持性能，通常需要在装载因子达到某个阈值时，对哈希表进行调整（例如，重新哈希，增加桶的数量）。

• 5、查找、插入和删除： 通过哈希函数计算键的哈希值，找到对应的索引位置，然后执行相应的操作。由于哈希表的平均时间复杂度是常数级别的，这些操作通常非常高效。

总体而言，哈希表是一种强大的数据结构，适用于需要快速查找、插入和删除的场景。在实际应用中，选择合适的哈希函数和解决冲突的方法对于哈希表的性能至关重要。

哈希表常见操作

当使用哈希表时，通常涉及以下几种常见操作：插入（Insertion）、查找（Search）、删除（Deletion）。在哈希表中，通常没有专门的“修改”一说，因为哈希表的设计更加注重于快速的插入、查找和删除操作。这些操作的详细介绍如下：

插入（Insertion）

首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上没有其他键值对，直接将键值对存储在该位置；如果发生冲突，根据解决冲突的方法（如链表法或开放地址法），找到下一个可用的位置并存储。

查找（Search）

首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上有键值对，则根据解决冲突的方法在链表或探查路径上查找键，找到则返回相应的值；如果没有找到，说明键不存在于哈希表中。

删除（Deletion）

首先，计算键的哈希值，通过哈希函数找到对应的索引位置。如果该位置上有键值对，则根据解决冲突的方法在链表或探查路径上查找键。如果找到，删除该键值对；如果没有找到，说明键不存在于哈希表中。

哈希表常见操作的代码实现

在此，分别用C语言、Java语言、Python语言实现哈希表的插入（Insertion）、查找（Search）、删除（Deletion）。

C语言版

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义哈希表中每个节点的结构
typedef struct Node {
    char *key;
    int value;
    struct Node *next;  // 链表用于处理冲突
} Node;

// 定义哈希表的结构
typedef struct HashTable {
    int size;
    Node **table;  // 数组用于存储链表的头节点
} HashTable;

// 哈希函数，简单地使用字符串的ASCII码之和模哈希表的大小
int hash(char *key, int size) {
    int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return sum % size;
}

// 初始化哈希表
HashTable *initHashTable(int size) {
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->size = size;
    
    // 为哈希表的每个桶分配内存
    hashTable->table = (Node **)malloc(sizeof(Node *) * size);
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = NULL;
    }
    
    return hashTable;
}

// 插入操作
void insert(HashTable *hashTable, char *key, int value) {
    // 计算哈希值
    int index = hash(key, hashTable->size);
    
    // 创建新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = strdup(key);  // 复制字符串
    newNode->value = value;
    newNode->next = NULL;
    
    // 如果该位置为空，直接插入
    if (hashTable->table[index] == NULL) {
        hashTable->table[index] = newNode;
    } else {
        // 否则，将新节点插入链表的头部
        newNode->next = hashTable->table[index];
        hashTable->table[index] = newNode;
    }
}

// 查找操作
int search(HashTable *hashTable, char *key) {
    // 计算哈希值
    int index = hash(key, hashTable->size);
    
    // 在链表中查找键值对
    Node *current = hashTable->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;  // 找到键，返回对应的值
        }
        current = current->next;
    }
    
    return -1;  // 未找到键
}

// 删除操作
void delete(HashTable *hashTable, char *key) {
    // 计算哈希值
    int index = hash(key, hashTable->size);
    
    // 在链表中查找键值对
    Node *current = hashTable->table[index];
    Node *prev = NULL;
    
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            // 找到键，删除节点
            if (prev == NULL) {
                // 如果是链表的头节点
                hashTable->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            
            // 释放内存
            free(current->key);
            free(current);
            return;
        }
        
        prev = current;
        current = current->next;
    }
}

// 释放哈希表的内存
void destroyHashTable(HashTable *hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        Node *current = hashTable->table[i];
        while (current != NULL) {
            Node *next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }
    free(hashTable->table);
    free(hashTable);
}

int main() {
    // 初始化哈希表
    HashTable *hashTable = initHashTable(10);

    // 插入键值对
    insert(hashTable, "apple", 5);
    insert(hashTable, "banana", 8);
    insert(hashTable, "orange", 12);

    // 查找键值对
    printf("Value for 'apple': %d\n", search(hashTable, "apple"));
    printf("Value for 'banana': %d\n", search(hashTable, "banana"));
    printf("Value for 'orange': %d\n", search(hashTable, "orange"));
    printf("Value for 'grape': %d\n", search(hashTable, "grape"));  // 不存在的键

    // 删除键值对
    delete(hashTable, "banana");

    // 再次查找键值对
    printf("Value for 'banana' after deletion: %d\n", search(hashTable, "banana"));

    // 释放哈希表的内存
    destroyHashTable(hashTable);

    return 0;
}

Java语言版

import java.util.LinkedList;

// 定义哈希表的键值对节点
class HashNode {
    String key;
    int value;

    public HashNode(String key, int value) {
        this.key = key;
        this.value = value;
    }
}

// 定义哈希表
class HashTable {
    private static final int DEFAULT_SIZE = 10;
    private LinkedList<HashNode>[] table;

    public HashTable() {
        // 初始化哈希表数组，每个桶用链表存储
        table = new LinkedList[DEFAULT_SIZE];
        for (int i = 0; i < DEFAULT_SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 哈希函数，简单地使用字符串的hashCode并取余
    private int hash(String key) {
        return key.hashCode() % DEFAULT_SIZE;
    }

    // 插入操作
    public void insert(String key, int value) {
        int index = hash(key);
        LinkedList<HashNode> list = table[index];

        // 检查是否已存在相同的键，如果是则更新值
        for (HashNode node : list) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
        }

        // 否则，将新键值对加入链表
        list.add(new HashNode(key, value));
    }

    // 查找操作
    public int search(String key) {
        int index = hash(key);
        LinkedList<HashNode> list = table[index];

        // 在链表中查找键值对
        for (HashNode node : list) {
            if (node.key.equals(key)) {
                return node.value;  // 找到键，返回对应的值
            }
        }

        return -1;  // 未找到键
    }

    // 删除操作
    public void delete(String key) {
        int index = hash(key);
        LinkedList<HashNode> list = table[index];

        // 在链表中查找键值对并删除
        for (HashNode node : list) {
            if (node.key.equals(key)) {
                list.remove(node);
                return;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // 初始化哈希表
        HashTable hashTable = new HashTable();

        // 插入键值对
        hashTable.insert("apple", 5);
        hashTable.insert("banana", 8);
        hashTable.insert("orange", 12);

        // 查找键值对
        System.out.println("Value for 'apple': " + hashTable.search("apple"));
        System.out.println("Value for 'banana': " + hashTable.search("banana"));
        System.out.println("Value for 'orange': " + hashTable.search("orange"));
        System.out.println("Value for 'grape': " + hashTable.search("grape"));  // 不存在的键

        // 删除键值对
        hashTable.delete("banana");

        // 再次查找键值对
        System.out.println("Value for 'banana' after deletion: " + hashTable.search("banana"));
    }
}

Python语言版

class HashNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value

class HashTable:
    def __init__(self, size=10):
        # 初始化哈希表，每个桶用链表存储
        self.size = size
        self.table = [[] for _ in range(size)]

    # 哈希函数，简单地使用字符串的哈希值并取余
    def _hash(self, key):
        return hash(key) % self.size

    # 插入操作
    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.table[index]

        # 检查是否已存在相同的键，如果是则更新值
        for node in bucket:
            if node.key == key:
                node.value = value
                return

        # 否则，将新键值对加入链表
        bucket.append(HashNode(key, value))

    # 查找操作
    def search(self, key):
        index = self._hash(key)
        bucket = self.table[index]

        # 在链表中查找键值对
        for node in bucket:
            if node.key == key:
                return node.value  # 找到键，返回对应的值

        return -1  # 未找到键

    # 删除操作
    def delete(self, key):
        index = self._hash(key)
        bucket = self.table[index]

        # 在链表中查找键值对并删除
        for node in bucket:
            if node.key == key:
                bucket.remove(node)
                return

if __name__ == "__main__":
    # 初始化哈希表
    hash_table = HashTable()

    # 插入键值对
    hash_table.insert("apple", 5)
    hash_table.insert("banana", 8)
    hash_table.insert("orange", 12)

    # 查找键值对
    print("Value for 'apple':", hash_table.search("apple"))
    print("Value for 'banana':", hash_table.search("banana"))
    print("Value for 'orange':", hash_table.search("orange"))
    print("Value for 'grape':", hash_table.search("grape"))  # 不存在的键

    # 删除键值对
    hash_table.delete("banana")

    # 再次查找键值对
    print("Value for 'banana' after deletion:", hash_table.search("banana"))

性能比较与小结

以上使用了三种不同编程语言实现哈希表的插入（Insertion）、查找（Search）、删除（Deletion）的相同点与不同点并分析它们的执行效率。

相同点

• 基本思想相同： 无论是用 C、Java 还是 Python 实现，它们都采用了哈希表这一数据结构，并使用了相似的基本思想，即通过哈希函数将键映射到哈希表中的位置，并处理冲突。

• 处理冲突方式相似： 三种实现都使用了链表法来处理冲突，即在哈希表的每个桶中使用链表来存储相同哈希值的键值对。这是一种简单而常见的冲突解决方式。

• 包含插入、查找、删除操作： 无论使用哪种编程语言，这三种实现都包含了插入、查找和删除这三种基本操作，这是哈希表的核心功能。

不同点

• 语法和代码结构

C 语言使用了显式的内存管理，包括 malloc 和 free，而且数组索引从 0 开始。C 代码通常更接近底层，需要程序员手动管理内存。

Java 使用了面向对象的风格，对内存管理有自动的垃圾回收机制。它的语法结构更加高级，使用了类和面向对象的概念。
Python 具有简洁的语法和动态类型，对于链表的操作更加方便，同时也不需要显式地处理内存。

• 哈希函数实现

C 语言的哈希函数使用了简单的 ASCII 码之和取余的方式。
Java 使用了字符串的 hashCode 方法，并取余哈希表大小。
Python 使用了内置的 hash 函数，并取余哈希表大小。

• 数据结构的表示

C 使用了数组和指针表示哈希表，链表的节点也是手动分配的内存。
Java 使用了类表示哈希表和链表，利用 Java 的面向对象特性。
Python 使用了类似于 Java 的面向对象表示法，但在语法上更为简洁。