首页 > 编程语言 >【轻松掌握数据结构与算法】哈希（Hashing）

【轻松掌握数据结构与算法】哈希（Hashing）

时间：2025-01-14 12:28:41浏览次数：3  
标签：index 哈希 self Hashing key table 数据结构 size

什么是哈希？

哈希是一种将任意长度的数据转换为固定长度的数据的技术。这个固定长度的数据通常被称为哈希值或哈希码。哈希函数是实现这一转换的关键，它接受任意长度的输入，并产生一个固定长度的输出。

为什么使用哈希？

哈希的主要用途之一是快速查找数据。通过哈希函数，我们可以将数据映射到一个较小的范围，从而减少查找时间。此外，哈希还可以用于数据完整性检查、密码存储等场景。

哈希表抽象数据类型（ADT）

哈希表是一种基于哈希函数的数据结构，它允许我们以接近O(1)的时间复杂度进行插入、删除和查找操作。哈希表的核心思想是使用哈希函数将键映射到表中的一个位置，然后将键值对存储在该位置。

理解哈希

哈希函数的设计对于哈希表的性能至关重要。一个好的哈希函数应该能够均匀地分布键值对，以减少冲突的发生。冲突是指多个键通过哈希函数映射到同一个位置的情况。

哈希组件

哈希表由以下几个关键组件组成：

  1. 哈希函数：将键映射到表中的位置。

  2. 哈希表：存储键值对的数组。

  3. 负载因子：表中已使用位置与总位置数的比值。

  4. 冲突解决技术：处理多个键映射到同一个位置的情况。

哈希表

哈希表是实现哈希功能的数据结构。它通常是一个数组，数组的每个位置可以存储一个或多个键值对。

哈希函数

哈希函数是哈希表的核心，它将键转换为哈希表中的索引。一个好的哈希函数应该满足以下条件：

  • 均匀分布：键值对在哈希表中均匀分布。

  • 快速计算：哈希函数的计算应该快速且高效。

  • 确定性：相同的键总是映射到相同的索引。

常见函数分类及示例

哈希函数是将任意长度的输入数据转换为固定长度输出的函数。一个好的哈希函数应该具有均匀分布、快速计算和确定性的特点。以下是一些常见的哈希函数分类及其示例：

1. 除法哈希函数（Division Hash Function）

除法哈希函数是最简单的哈希函数之一，它通过取模运算将输入数据映射到哈希表的索引。

公式

h(k) = k \mod m

其中，k 是输入键，m 是哈希表的大小。

示例代码
def division_hash_function(key, table_size):
    return key % table_size

# 示例输入输出
table_size = 10
print(division_hash_function(25, table_size))  # 输出: 5
print(division_hash_function(35, table_size))  # 输出: 5

2. 乘法哈希函数（Multiplication Hash Function）

乘法哈希函数通过乘法和取模运算将输入数据映射到哈希表的索引。这种方法通常使用一个常数 A，通常选择为黄金分割比。

公式

h(k) = \lfloor m \times ((k \times A) \mod 1) \rfloor

其中，k 是输入键，m 是哈希表的大小，A 是一个常数（通常选择为黄金分割比 0.618033988749895）。

示例代码
def multiplication_hash_function(key, table_size):
    A = 0.618033988749895
    return int(table_size * ((key * A) % 1))

# 示例输入输出
table_size = 10
print(multiplication_hash_function(25, table_size))  # 输出: 4
print(multiplication_hash_function(35, table_size))  # 输出: 6

3. 中平方哈希函数（Mid-Square Hash Function）

中平方哈希函数通过将输入数据平方，然后取中间几位作为哈希值。

公式

h(k) = \text{mid}((k^2) \mod (10^{2p}))

其中，k 是输入键，p 是哈希表大小的位数。

示例代码
def mid_square_hash_function(key, table_size):
    key_squared = key * key
    key_str = str(key_squared)
    mid = len(key_str) // 2
    mid_value = int(key_str[mid-2:mid+2])
    return mid_value % table_size

# 示例输入输出
table_size = 100
print(mid_square_hash_function(25, table_size))  # 输出: 56
print(mid_square_hash_function(35, table_size))  # 输出: 25

4. 折叠法哈希函数（Folding Hash Function）

折叠法哈希函数通过将输入数据分成若干部分，然后将这些部分相加得到哈希值。

公式

h(k) = \sum_{i=0}^{n-1} k_i \mod m

其中，k 是输入键，k_i 是输入键的第 i 个部分，m 是哈希表的大小。

示例代码
def folding_hash_function(key, table_size, part_size=2):
    key_str = str(key)
    parts = [int(key_str[i:i+part_size]) for i in range(0, len(key_str), part_size)]
    return sum(parts) % table_size

# 示例输入输出
table_size = 100
print(folding_hash_function(253456, table_size))  # 输出: 66
print(folding_hash_function(356789, table_size))  # 输出: 87

5. 旋转哈希函数（Rotating Hash Function）

旋转哈希函数通过将输入数据的每一位旋转特定的位数，然后计算哈希值。

公式

h(k) = \left( \sum_{i=0}^{n-1} (k_i \ll (i \times p)) \right) \mod m

其中，k 是输入键，k_i 是输入键的第 i 个字节，p 是旋转位数，m 是哈希表的大小。

示例代码
def rotating_hash_function(key, table_size, shift=4):
    hash_value = 0
    for byte in key.to_bytes((key.bit_length() + 7) // 8, byteorder='big'):
        hash_value = ((hash_value << shift) + byte) % table_size
    return hash_value

# 示例输入输出
table_size = 100
print(rotating_hash_function(253456, table_size))  # 输出: 76
print(rotating_hash_function(356789, table_size))  # 输出: 37

6. 通用哈希函数（Universal Hash Function）

通用哈希函数通过选择一个随机的哈希函数，确保不同输入键的哈希值尽可能均匀分布。

公式

h_{a,b}(k) = ((a \times k + b) \mod p) \mod m

其中，k 是输入键，a 和 b 是随机选择的整数，p 是一个大于 m 的质数，m 是哈希表的大小。

示例代码
import random

def universal_hash_function(key, table_size):
    p = 104729  # 一个较大的质数
    a = random.randint(1, p-1)
    b = random.randint(0, p-1)
    return ((a * key + b) % p) % table_size

# 示例输入输出
table_size = 100
print(universal_hash_function(253456, table_size))  # 输出: 42
print(universal_hash_function(356789, table_size))  # 输出: 17

以上是一些常见的哈希函数及其示例代码。每种哈希函数都有其特定的用途和优缺点。在实际应用中，选择合适的哈希函数可以显著提高哈希表的性能。希望这些示例能帮助您更好地理解和应用哈希技术。

负载因子

负载因子是哈希表中已使用位置与总位置数的比值。它用于衡量哈希表的满程度。当负载因子超过一定阈值时，通常需要对哈希表进行重新调整大小，以保持性能。

冲突

冲突是指多个键通过哈希函数映射到同一个位置的情况。冲突解决技术包括：

  • 链地址法（Separate Chaining）：每个哈希表位置维护一个链表，所有映射到该位置的键值对都存储在链表中。

  • 开放定址法（Open Addressing）：当发生冲突时，寻找下一个可用位置存储键值对。

冲突解决技术比较

冲突解决技术优点缺点
链地址法实现简单，适合负载因子较高的情况需要额外的指针空间
开放定址法不需要额外的指针空间负载因子较高时性能下降，删除操作复杂

如何哈希表获得O(1)复杂度？

在理想情况下，哈希表可以实现O(1)的插入、删除和查找操作。然而，这需要一个良好的哈希函数和适当的冲突解决策略。在实际应用中，哈希表的性能通常接近O(1)，但可能会因为冲突和负载因子的影响而有所下降。

不适合哈希表的问题

虽然哈希表在许多情况下都非常高效，但有些问题不适合使用哈希表。例如，需要保持键的顺序或进行范围查询的问题，哈希表就不太适用。

布隆过滤器

布隆过滤器是一种空间高效的概率型数据结构，用于测试一个元素是否是一个集合的成员。它可能会返回假阳性，但不会返回假阴性。

哈希：问题与解决方案

问题1：实现一个简单的哈希表

问题描述：实现一个简单的哈希表，支持插入、删除和查找操作。

示例代码：

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])

    def delete(self, key):
        index = self.hash_function(key)
        for i, item in enumerate(self.table[index]):
            if item[0] == key:
                del self.table[index][i]
                return

    def search(self, key):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        return None

# 示例输入输出
ht = HashTable()
ht.insert("apple", 1)
ht.insert("banana", 2)
print(ht.search("apple"))  # 输出: 1
ht.delete("apple")
print(ht.search("apple"))  # 输出: None

问题2：处理哈希表的冲突

问题描述：实现一个哈希表，使用链地址法处理冲突。

示例代码：

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return

    def search(self, key):
        index = self.hash_function(key)
        bucket = self.table[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

# 示例输入输出
ht = HashTable()
ht.insert("apple", 1)
ht.insert("banana", 2)
print(ht.search("apple"))  # 输出: 1
ht.delete("apple")
print(ht.search("apple"))  # 输出: None

问题3：使用开放定址法处理冲突

问题描述：实现一个哈希表，使用开放定址法处理冲突。

示例代码：

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
        self.table[index] = (key, value)

    def delete(self, key):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                # Rehash elements to maintain open addressing
                self.rehash(index)
                return
            index = (index + 1) % self.size

    def rehash(self, start_index):
        index = start_index
        while True:
            next_index = (index + 1) % self.size
            if self.table[next_index] is None:
                break
            key, value = self.table[next_index]
            self.table[next_index] = None
            self.insert(key, value)
            index = next_index

    def search(self, key):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
        return None

# 示例输入输出
ht = HashTable()
ht.insert("apple", 1)
ht.insert("banana", 2)
print(ht.search("apple"))  # 输出: 1
ht.delete("apple")
print(ht.search("apple"))  # 输出: None

问题4：实现布隆过滤器

问题描述：实现一个布隆过滤器，用于测试一个元素是否是一个集合的成员。

示例代码：

import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_num):
        self.size = size
        self.hash_num = hash_num
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, item):
        for i in range(self.hash_num):
            digest = mmh3.hash(item, i) % self.size
            self.bit_array[digest] = True

    def lookup(self, item):
        for i in range(self.hash_num):
            digest = mmh3.hash(item, i) % self.size
            if not self.bit_array[digest]:
                return False
        return True

# 示例输入输出
bf = BloomFilter(50, 7)
bf.add("apple")
bf.add("banana")
print(bf.lookup("apple"))  # 输出: True
print(bf.lookup("orange"))  # 输出: False

总结

哈希表是一种非常高效的数据结构，适用于快速查找、插入和删除操作。通过合理设计哈希函数和冲突解决策略，可以显著提高哈希表的性能。布隆过滤器则是一种空间高效的概率型数据结构，适用于测试元素是否属于某个集合。希望这些示例代码和输入输出能帮助您更好地理解和应用哈希技术。

标签：index,哈希,self,Hashing,key,table,数据结构,size
From： https://blog.csdn.net/Whoisbug/article/details/145127245

相关文章

  • leetcode刷题记录（java）——参考代码随想录：数组 链表 哈希表
    四、题目之：代码随想录https://programmercarl.com/(1)代码随想录：数组704.二分查找classSolution{publicintsearch(int[]nums,inttarget){if(target<nums[0]||target>nums[nums.length-1]){return-1;}intleft=0......
  • Java-数据结构-栈与队列(常考面试题与单调栈)
    在上一篇的学习中，我们学习了栈和队列的基本知识，以及它们对应都有哪些方法，在什么应用场景下如何使用，并且还对它们进行了模拟实现，而其实对于栈和队列的相关知识还远不止于此，而今天我们就对栈与队列进行复盘，认识更多使用它们的场景，夯实代码功底吧~一、常考面试题-思维以下习题在......
  • Java算法 数据结构 栈 队列 优先队列 比较器
    目录栈Stack性质构造方法代码示例队列Queue性质构造方法代码示例优先队列PriorityQueue性质构造方法代码示例比较器1.Comparator接口的方法2.常见的内置比较器1.自然排序比较器（naturalOrder()）2.逆序排序比较器（reverseOrder()）3.nullsFirst()......
  • 数据结构(霍夫曼树)
    1.Huffman编码1.1问题起源假设在数据通信中，有一字串"ABABBCBBA"需要传送，一般会将这些字符进行编码，然后按编码后的二进制位进行传输，例如这些字母的ASCII码取值为：A(65):01000001B(66):01000010C(67):01000011因此最“简单”的方式，就是将上述字串直接使用字符......
  • 数据结构：栈(Stack)和队列(Queue)—面试题（二）
    1.用队列实现栈。习题链接https://leetcode.cn/problems/implement-stack-using-queues/description/描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：voidpush(intx) 将元素x压入栈顶。int......
  • 代码随想录算法训练营第6天 | 哈希表理论基础，242.有效的字母异位词，349. 两个数组的交
    一、刷题部分1.1哈希表理论基础原文链接：代码随想录题目链接：......
  • 数据结构入门
    数据结构数据结构分为顺序表，链表，栈，队列，堆，树，图顺序表顺序表的物理结构和逻辑结构都是连续的去建立一个顺序表，我们需要先去了解底层是什么。在脑海中很容易就会联想到数组，所以创建一个顺序表，首先要有一个数组。但是仅仅有数组是不够的，我们需要在其中对数据进行处理，那么其有......
  • 认识Pandas，以及pandas的数据结构Series和DataFrame
    以下是关于pandas数据结构部分的详细讲解和案例：SeriesSeries是pandas中的一种一维数组结构，可以存储任意类型的数据（整数、字符串、浮点数、Python对象等），并且每个数据点都有一个对应的索引标签。创建Series案例：创建一个包含水果数量的Series对象。代码：importpandasa......
  • 数据结构：栈(Stack)和队列(Queue)—面试题（一）
    目录1、括号匹配2、逆波兰表达式求值 3、栈的压入、弹出序列4、最小栈 1、括号匹配习题链接https://leetcode.cn/problems/valid-parentheses/description/描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必......
  • Redis 是一个开源的高性能键值对存储数据库，通常被用作缓存、消息队列和持久化数据库。
    Redis服务器是什么？Redis是一个开源的高性能键值对存储数据库，通常被用作缓存、消息队列和持久化数据库。Redis支持多种数据结构，如字符串、哈希、列表、集合、有序集合、位图等。它被广泛用于需要快速读写操作、低延迟的场景。Redis可以作为一个独立的数据库使用，也可以作为缓......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99