• 【算法与数据结构】--高级算法和数据结构--哈希表和集合

    一、哈希表的原理

    哈希表（Hash Table）是一种常用的数据结构，其核心原理是将数据存储在数组中，并使用哈希函数来映射数据的键（Key）到数组中的特定位置，这个位置通常被称为“哈希桶”或“槽位”。哈希表允许快速的数据查找、插入和删除操作，通常在平均情况下，这些操作的时间复杂度为O(1)。以下是哈希表的基本原理：

    1. 哈希函数（Hash Function）：哈希表中的关键部分是哈希函数。哈希函数接受一个键作为输入，然后返回一个与该键关联的哈希码（Hash Code）。这个哈希码通常是一个整数值。好的哈希函数能够将不同的键映射到不同的哈希码，最大限度地减少碰撞（多个键映射到相同哈希码）的机会。
    2. 哈希桶（Hash Bucket）：哈希表通常包括一个固定数量的桶或槽位（通常是数组），每个槽位可以存储一个或多个键-值对。哈希函数将键映射到特定的槽位。
    3. 存储和检索：要存储一个键-值对，哈希函数首先计算键的哈希码，然后确定要将数据放入哪个槽位。要检索一个值，通过相同的哈希函数计算出哈希码，然后查找对应槽位，找到存储的值。
    4. 处理冲突：由于不同键可能映射到相同的槽位，哈希表必须处理碰撞。常见的处理冲突的方式包括链地址法和开放地址法。在链地址法中，每个槽位保存一个链表或其他数据结构，所有哈希到相同位置的键-值对都存储在该链表中。在开放地址法中，如果一个槽位已经被占用，哈希表会继续查找下一个可用的槽位。
    5. 哈希表的大小：哈希表的性能与槽位的数量和哈希函数的质量有关。选择合适的哈希表大小和哈希函数是关键，它们会影响到哈希表的效率和性能。

    Tip：哈希表是一种高效的数据结构，适用于需要快速查找、插入和删除数据的情况，但需要选择好的哈希函数和处理冲突的方法，以确保哈希表的性能。

    二、哈希表的应用

    1. 数据检索：哈希表用于快速的数据检索，允许在常数时间内（O(1)）查找、插入和删除数据。这在数据库管理系统、缓存系统和搜索引擎中经常用到。
    2. 哈希表查找（Hash Table Lookup）：哈希表用于存储键-值对，允许通过键快速查找对应的值。这种用途在编程中经常见到，例如，字典、映射、集合等数据结构都可以基于哈希表实现。
    3. 缓存：缓存系统通常使用哈希表来存储已检索的数据，以便快速的重新访问。这可以有效减少重复的计算和提高应用程序的性能。
    4. 词频统计：哈希表用于统计文档中单词的出现频率。通过使用单词作为键，哈希表可以快速记录每个单词的计数。
    5. 分布式系统：哈希表在分布式系统中用于数据分片、路由和负载均衡。例如，一致性哈希表用于将数据分布在多个节点之间，以实现负载均衡。
    6. 数据结构：哈希表是许多其他数据结构的基础，如集合、字典、映射、堆集、缓存和优先队列。
    7. 数据完整性：哈希表用于检查文件或数据的完整性。通过计算数据的哈希值，可以验证数据是否在传输或存储过程中被篡改。
    8. 哈希函数：哈希函数是密码学中的重要组成部分，用于密码存储、数字签名、消息验证等。好的哈希函数应该能够产生不可逆的哈希值。
    9. 分布式数据库：在分布式数据库中，哈希表常用于数据定位，以便快速查找数据的物理位置。
    10. 路由表：哈希表用于存储网络路由信息，以确定数据包的传输路径。
    11. 拼写检查和自动完成：哈希表可以用于存储单词和短语的拼写检查和自动完成建议，以改善用户搜索体验。

    三、哈希表的实现

    哈希表的实现通常基于两主要部分：哈希函数和数据结构用于存储碰撞（多个键映射到相同哈希值）的键值对。我将为你提供一个简单的哈希表实现示例，使用C#和Java分别展示。

    3.1 C# 哈希表实现
    using System;
using System.Collections.Generic;

public class MyHashTable<TKey, TValue>
{
    private const int InitialCapacity = 16;
    private LinkedList<KeyValuePair<TKey, TValue>>[] buckets;

    public MyHashTable()
    {
        buckets = new LinkedList<KeyValuePair<TKey, TValue>>[InitialCapacity];
    }

    public void Add(TKey key, TValue value)
    {
        int bucketIndex = GetBucketIndex(key);

        if (buckets[bucketIndex] == null)
        {
            buckets[bucketIndex] = new LinkedList<KeyValuePair<TKey, TValue>>();
        }

        var bucket = buckets[bucketIndex];
        foreach (var pair in bucket)
        {
            if (pair.Key.Equals(key))
            {
                throw new ArgumentException("Key already exists in the hash table.");
            }
        }

        bucket.AddLast(new KeyValuePair<TKey, TValue>(key, value));
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        int bucketIndex = GetBucketIndex(key);

        var bucket = buckets[bucketIndex];
        if (bucket != null)
        {
            foreach (var pair in bucket)
            {
                if (pair.Key.Equals(key))
                {
                    value = pair.Value;
                    return true;
                }
            }
        }

        value = default(TValue);
        return false;
    }

    private int GetBucketIndex(TKey key)
    {
        int hashCode = key.GetHashCode();
        return (hashCode & int.MaxValue) % buckets.Length;
    }
}

public class Program
{
    public static void Main()
    {
        var myHashTable = new MyHashTable<string, int>();

        myHashTable.Add("Alice", 25);
        myHashTable.Add("Bob", 30);
        myHashTable.Add("Charlie", 28);

        if (myHashTable.TryGetValue("Bob", out int age))
        {
            Console.WriteLine("Bob's age is " + age);
        }
        else
        {
            Console.WriteLine("Key not found.");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    3.2 Java 哈希表实现
    import java.util.LinkedList;

public class MyHashTable<TKey, TValue> {
    private static final int InitialCapacity = 16;
    private LinkedList<KeyValuePair<TKey, TValue>>[] buckets;

    public MyHashTable() {
        buckets = new LinkedList[InitialCapacity];
    }

    public void put(TKey key, TValue value) {
        int bucketIndex = getBucketIndex(key);

        if (buckets[bucketIndex] == null) {
            buckets[bucketIndex] = new LinkedList<>();
        }

        LinkedList<KeyValuePair<TKey, TValue>> bucket = buckets[bucketIndex];
        for (KeyValuePair<TKey, TValue> pair : bucket) {
            if (pair.key.equals(key)) {
                throw new IllegalArgumentException("Key already exists in the hash table.");
            }
        }

        bucket.add(new KeyValuePair<>(key, value));
    }

    public boolean get(TKey key, TValue[] value) {
        int bucketIndex = getBucketIndex(key);

        LinkedList<KeyValuePair<TKey, TValue>> bucket = buckets[bucketIndex];
        if (bucket != null) {
            for (KeyValuePair<TKey, TValue> pair : bucket) {
                if (pair.key.equals(key)) {
                    value[0] = pair.value;
                    return true;
                }
            }
        }

        return false;
    }

    private int getBucketIndex(TKey key) {
        int hashCode = key.hashCode();
        return (hashCode & Integer.MAX_VALUE) % buckets.length;
    }

    public static void main(String[] args) {
        MyHashTable<String, Integer> myHashTable = new MyHashTable<>();

        myHashTable.put("Alice", 25);
        myHashTable.put("Bob", 30);
        myHashTable.put("Charlie", 28);

        Integer[] age = new Integer[1];
        if (myHashTable.get("Bob", age)) {
            System.out.println("Bob's age is " + age[0]);
        } else {
            System.out.println("Key not found.");
        }
    }
}

class KeyValuePair<TKey, TValue> {
    TKey key;
    TValue value;

    KeyValuePair(TKey key, TValue value) {
        this.key = key;
        this.value = value;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    这些示例展示了如何使用链表来解决哈希碰撞问题，确保每个键值对都能正确存储和检索。哈希表的核心思想是使用哈希函数将键映射到特定的桶或索引，以便快速查找数据。注意，这些示例是非常基本的实现，真实的哈希表库提供了更多的功能和优化，以确保高效性能。

    四、集合的原理

    集合（Set）是计算机科学中的一种数据结构，它旨在存储一组互不相同的元素。集合通常基于数学集合理论的概念，因此它具有以下基本原理：

    1. 互异性：集合中的元素是互不相同的，每个元素只能在集合中出现一次。如果插入已存在的元素，它不会被重复存储。
    2. 无序性：集合中的元素没有明确定义的顺序。与列表（List）不同，集合不关心元素的位置或顺序。
    3. 查找和插入效率高：集合的实现通常使用一种高效的数据结构，如哈希表，以支持快速的查找和插入操作。这使得集合非常适合用于检查某个元素是否存在，而不需要遍历整个集合。
    4. 不允许重复元素：集合会自动防止重复元素的插入。如果你尝试插入一个已存在的元素，它会被忽略。
    5. 支持基本集合操作：集合通常支持基本的集合操作，如并集、交集和差集等，允许你执行这些操作以组合、比较或筛选集合中的元素。
    6. 迭代和遍历：你可以遍历集合中的元素，但顺序是不确定的。一些集合也支持迭代器，允许你按特定顺序访问元素。
    7. 可变和不可变集合：一些编程语言和库提供可变和不可变集合。可变集合允许在已创建的集合上执行插入、删除等操作，而不可变集合一旦创建，就不能更改。

    集合有各种不同的实现，包括哈希集合、树集、链表集合等，每种实现在不同的使用场景下都有其优势。集合是在计算机程序中广泛使用的数据结构，用于管理一组唯一元素，例如存储不重复的数据、检查元素是否存在、处理键值对、实现高效的查找操作等。

    五、集合的应用

    1. 数据库管理系统：在数据库中，集合常用于存储唯一的键或索引值，以支持高效的数据检索。例如，数据库索引通常是一个集合，用于快速查找数据库表中的数据。
    2. 字典和键值对存储：集合可用于存储键值对，这在编程中很常见。这使得程序可以用键快速查找和获取相关联的值。编程语言中的“字典”或“映射”通常就是基于集合的实现。
    3. 集合操作：集合支持一系列基本集合操作，如并集、交集、差集等。这些操作用于在集合上执行集合运算，通常用于组合、比较或筛选数据。
    4. 查找重复数据：集合用于查找重复的数据并去重，保留唯一的元素。这对于数据处理和数据清洗非常有用。
    5. 无序数据存储：集合是一种无序的数据结构，因此它们经常用于存储不需要特定排序的数据。
    6. 权限和用户管理：在许多应用中，集合用于管理用户权限和用户组。用户可以分配到不同的集合，每个集合对应一组权限。
    7. 缓存：集合用于实现缓存，以存储最近访问的数据或计算结果，以提高访问速度。
    8. 在线社交网络：社交网络中，集合可用于表示用户之间的关系，如“关注者”集合或“好友”集合。
    9. 搜索引擎索引：搜索引擎使用集合数据结构来存储索引，以支持高效的文本检索。
    10. 电子商务：电子商务网站可以使用集合来管理产品目录，购物车和订单等。
    11. 游戏开发：在游戏开发中，集合常用于管理游戏中的对象、事件和状态。
    12. 自动化测试：在自动化测试中，集合用于管理测试用例和测试数据。
    13. 日程安排和提醒：集合可以用于管理日程安排、提醒和事件。
    14. 文档检索和搜索：搜索引擎使用集合来构建文档索引，以支持快速的文本检索。
    15. 网络路由表：在网络路由中，集合用于管理路由表，以支持数据包的路由。

    这些只是集合在各种领域中的一些常见应用示例。由于其高效的数据存储和检索能力，集合在计算机科学和软件开发中具有广泛的应用。无论是管理数据、支持快速查找、去重或执行集合运算，集合都是非常重要的数据结构。

    六、集合的实现

    在C#和Java中，集合的实现通常使用类库中提供的内置集合类型。以下是在C#和Java中实现集合的示例：

    6.1 C#中的集合实现

    在C#中，你可以使用.NET Framework提供的各种集合类型。以下是一些常见的C#集合类型的示例：

    1. List（列表）：这是一个动态数组，用于存储元素。它允许在列表中添加、删除和访问元素。
    using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        List<int> numbers = new List<int>();
        numbers.Add(1);
        numbers.Add(2);
        numbers.Add(3);

        foreach (int number in numbers)
        {
            Console.WriteLine(number);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    1. Dictionary（字典）：这是一个键值对存储，允许你将值与唯一键相关联。
    using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        Dictionary<string, int> ages = new Dictionary<string, int>();
        ages["Alice"] = 30;
        ages["Bob"] = 25;
        ages["Charlie"] = 35;

        Console.WriteLine("Alice's age is " + ages["Alice"]);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    1. HashSet（哈希集）：这是一个用于存储唯一元素的集合。它基于哈希表实现。
    using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        HashSet<int> uniqueNumbers = new HashSet<int>();
        uniqueNumbers.Add(1);
        uniqueNumbers.Add(2);
        uniqueNumbers.Add(1); // 这不会重复添加

        foreach (int number in uniqueNumbers)
        {
            Console.WriteLine(number);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    6.2 Java中的集合实现

    在Java中，你可以使用Java集合框架提供的各种集合类型。以下是一些常见的Java集合类型的示例：

    1. ArrayList（数组列表）：与C#中的List类似，它是一个可变大小的数组，用于存储元素。
    import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    1. HashMap（哈希映射）：与C#中的Dictionary类似，它是一个键值对存储，用于将值与唯一键相关联。
    import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        ages.put("Charlie", 35);

        System.out.println("Alice's age is " + ages.get("Alice"));
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    1. HashSet（哈希集）：与C#中的HashSet类似，它是用于存储唯一元素的集合。
    import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> uniqueNumbers = new HashSet<>();
        uniqueNumbers.add(1);
        uniqueNumbers.add(2);
        uniqueNumbers.add(1); // 这不会重复添加

        for (int number : uniqueNumbers) {
            System.out.println(number);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    这些示例展示了如何在C#和Java中使用内置集合类型来实现集合。这些集合类型提供了高效的数据存储和检索功能，适合各种不同的应用场景。

    七、总结

    哈希表是一种数据结构，通过哈希函数将键映射到数组中的槽位，实现快速查找、插入和删除操作。哈希表的关键原理包括好的哈希函数、哈希桶、处理冲突方式，合适的大小和哈希表的性能关系密切。哈希表广泛应用于数据库管理、数据查找、缓存、词频统计、分布式系统、数据结构等领域，提供高效的数据管理和检索。集合是一种数据结构，存储互异且无序的元素，支持高效的查找、插入、集合操作等。集合在数据库、字典、数据去重、权限管理、缓存、社交网络等方面有广泛应用。在C#和Java中，可以使用内置集合类型实现哈希表和集合，提供高效的数据操作。

  • 相关阅读:
    高斯消元总结
    Tableau:详细表达式(LOD表达式)的计算过程
    什么是网络安全等级保护
    Docker下的SqlServer发布订阅启用
    【LVGL】ANIM（动画）时间线学习
    Lerna入门与实战
    HTML静态网页作业——关于我的家乡介绍安庆景点
    测绘地理信息毕业生有充足职业选择
    在3分钟内使用AI-Chat生成精美PPT（附AI工具）
    新手入门SLAM必备资料
  • 原文地址：https://blog.csdn.net/gangzhucoll/article/details/133874627